邻接矩阵和递归DFS

阅读量: 255 编辑

使用邻接矩阵数据结构,通过递归算法实现图的深度优先遍历(DFS)

【输入样例】

7
0 1 1 0 0 0 0
0 0 1 1 1 0 0
1 1 0 0 0 1 0
0 1 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 1
0 0 0 0 1 1 0

【输出样例】

A B C F G E D

【参考程序】

//爱码岛编程
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
int adj[MAXN][MAXN];
int visited[MAXN];

int n;

void visit(int w){
	visited[w] = 1;
    cout << char(w + 'A') << " ";
}

// 连通性
void dfs(int w) {
    if (visited[w]) {
        return;
    }
    visit(w);
	
    int j = 0;
    for (; j < n; j++) {
        if (adj[w][j] == 1 && !visited[j]) {
            dfs(j);
            break;
        }
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> adj[i][j];
        }
    }
	
	cout << endl;
	
    for (int i = 0; i < n; i++) {
        if (!visited[i])
            dfs(i);
    }

    return 0;
}

爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司