图的深度优先搜索遍历图
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Node
{
//v 代表编号
//w 代表权值
int v,w;
Node(int _v,int _w):v(_v),w(_w){}
};
//图的存储结构
vector<Node> imap[10005];
bool vis[10005] = {false};//初始情况各个顶点都没有被访问
int n;//顶点数目
//u 当前顶点的标号 depth为深度
void DFS(int u,int depth){
vis[u] = true;//设置u已经被访问
// 遍历imap[i]
for(int i = 0;i < imap[u].size();i++){
Node iv = imap[u][i];
if(vis[iv.v] == false){
printf(" -> %d",iv.v);
DFS(iv.v,depth + 1);//访问iv.v
}
}
}
void DFSTrave() {
//for针对连通分量
for(int i = 0;i < n;i++){
if(vis[i] == false)
DFS(i,1);
}
}
int main(int argc, char const *argv[]) {
printf("please input the vectex number:");
scanf("%d",&n);
//先输入v再输入w 输入w = -1代表i的邻接表输入结束,如果v & w = -1说明输入结束
for(int i = 0;i < n;i++) {
int iv,iw;
while (1) {
scanf("%d%d",&iv,&iw);
//当w = -1时i的邻接表输入结束
if(iw == -1)break;
imap[i].push_back(Node(iv,iw));
}
}
// for(int i = 0;i < imap.size();i++){
// for(int j = 0;j < imap[i].size();j++){
// printf("%d %d | ",imap[i][j].v,imap[i][j].w);
// }
// printf("\n");
// }
printf("DFS:\n");
printf("0");
DFSTrave();
printf("\n");
return 0;
}
虽然构建邻接表时加入了权值但是代码中并没有实际应用
输入对应的图