使用邻接矩阵数据结构,借助栈(Stack),实现图的深度优先遍历(DFS)
![](/static/upload/1614326819455008.png)
【输入样例】
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;
}