邻接矩阵和栈实现DFS

经典算法

邻接矩阵和栈实现DFS

阅读量: 131 编辑

使用邻接矩阵数据结构，借助栈（Stack），实现图的深度优先遍历（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 C F G E B D

【参考程序】

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

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

int n;
stack<int> st;

void visit(int w){
	cout << char(w + 'A') << " ";
}

void dfs(int w){
	st.push(w);
	visited[w] = 1;
	
	while(!st.empty()){
		w = st.top();
		st.pop();
		//访问 
		visit(w);
		for(int j = 0; j < n; j++){
			if(adj[w][j] == 1 && !visited[j]){
				st.push(j);
				visited[j] = 1;
			}
		} 
	}
}

int main() {

	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> adj[i][j];
		}
	}
	
	dfs(0);
	
    return 0;
}