图的DFS和BFS遍历

#include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; const int MAXV = 1000;//最大顶点数 const int INF = 1000000000;//设INF为一个很大的数 /* DFS伪代码： DFS(u)//访问顶点u { vis[u] = true;//设置u已被访问 for(从u出发能到达的所有顶点v)//枚举从u出发可以到达的所有顶点v if vis[v] == false //如果v未被访问 DFS(v);//递归访问v } DFSTrave(G)//遍历图G { for(G的所有顶点u)//对G的所有顶点u if vis[u] == false //如果u未被访问 DFS(u); //访问u所在的连通块 } */ //邻接矩阵版 int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数 bool vis[MAXV] = { false };//如果顶点i已被访问，则vis[i]==true。初值为false void DFS(int u, int depth)//u为当前访问的顶点标号，depth为深度 { vis[u] = true;//设置u已被访问 //如果需要对u进行一些操作，可以在这里进行 //下面对所有从u出发能到达的分支顶点进行枚举 for (int v = 0; v < n; v++)//对每个顶点v { if (vis[v] == false && G[u][v] != INF)//如果v未被访问，且u可到达v { DFS(v, depth + 1);//访问v，深度加1 } } } void DFSTrave()//遍历图G { for (int u = 0; u < n; u++)//对每个顶点u { if (vis[u] == false)//如果u未被访问 { DFS(u, 1);//访问u和u所在的连通块，1表示初始为第一层 } } } //邻接表版 vector<int> Adj[MAXV];//图G的邻接表 int n;//n为顶点数，MAXV为最大顶点数 bool vis[MAXV] = { false }; //如果顶点i已被访问，则vis[i]==true。初值为false void DFS(int u, int depth)//u为当前访问的顶点标号，depth为深度 { vis[u] = true;//设置u已被访问 /*如果需要对u进行一些操作，可以在此处进行*/ for (int i = 0; i < Adj[u].size(); i++)//对从u出发可以到达的所有顶点v { int v = Adj[u][i]; if (vis[v] == false)//如果v未被访问 { DFS(v, depth + 1);//访问v，深度加1 } } } void DFSTrave()//遍历图G { for(int u = 0; u < n; u++)//对每个顶点 { if (vis[u] == false)//如果u未被访问 { DFS(u, 1);//访问u和u所在的连通块，1表示初始为第一层 } } } /* BFS伪代码： BFS(u)//遍历u所在的连通块 { queue q;//定义队列q 将u入队； inq[u] = true; //设置u已被加入过队列 while(q非空)//只要队列非空 { 取出q的队首元素u进行访问; for(从u出发可达的所有顶点v)//枚举从u能直接到达的顶点v if(inq[v] == false)//如果v未曾加入过队列 { 将v入队; inq[v] = true;//设置v已被加入过队列 } } } BFSTrave(G)//遍历图G { for(G的所有顶点u)//枚举G的所有顶点u if(inq[u] == false)//如果u未曾加入过队列 { BFS(u);//遍历u所在的连通块 } } */ //邻接矩阵版 int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数 bool inq[MAXV] = { false };//若顶点i曾入过队列，则inq[i]==true。初值为false void BFS(int u)//遍历u所在的连通块 { queue<int> q;//定义队列q q.push(u);//将初始点u入队 inq[u] = true;//设置u已被加入过队列 while (!q.empty())//只要队列非空 { int u = q.front();//取出队首元素 q.pop();//将队首元素出队 for (int v = 0; v < n; v++) {//如果u的邻接点v未曾加入过队列 if (inq[v] == false && G[u][v] != INF) { q.push(v);//将v入队 inq[v] = true;//标记v为已被加入过队列 } } } } void BFSTrave()//遍历图G { for (int u = 0; u < n; u++)//枚举所有顶点 { if (inq[u] == false)//如果u未曾加入过队列 { BFS(u);//遍历u所在的连通块 } } } //邻接表版 vector<int> Adj[MAXV];//图G，Adj[u]存放从顶点u出发可以到达的所有顶点 int n;//n为顶点数，MAXV为最大顶点数 bool inq[MAXV] = { false };//若顶点i曾入过队列，则inq[i]==true。初值为false void BFS(int u)//遍历单个连通块 { queue<int> q;//定义队列q q.push(u);//将初始点u入队 inq[u] = true;//设置u已被加入过队列 while (!q.empty())//只要队列非空 { int u = q.front();//取出队首元素 q.pop();//将队首元素出队 for (int i = 0; i < Adj[u].size(); i++)//枚举从u出发能到达的所有顶点 { int v = Adj[u][i]; if (inq[v] == false)//如果v未曾加入过队列 { q.push(v);//将v入队 inq[v] = true;//标记v为已被加入过队列 } } } } void BFSTrave()//遍历图G { for (int u = 0; u < n; u++)//枚举所有顶点 { if (inq[u] == false)//如果u未曾加入过队列 { BFS(u);//遍历u所在的连通块 } } } //以下为bfs遍历图求出每个顶点的层号 struct Node { int v;//顶点编号 int layer;//顶点序号 }; const int N = 1000; vector<Node> Adj[N]; void BFS(int s)//s为起始顶点编号 { queue<Node> q;//BFS队列 Node start;//起始顶点 start.v = s;//起始顶点编号 start.layer = 0;//起始顶点层号为0 q.push(start);//将起始顶点压入队列 inq[start.v] = true;//起始顶点的编号设为已被加入过队列 while (!q.empty()) { Node topNode = q.front();//取出队首顶点 q.pop();//队首顶点出队 int u = topNode.v;//队首顶点的编号 for (int i = 0; i < Adj[u].size(); i++) { Node next; next.v= Adj[u][i];//从u出发能到达的顶点next next.layer = topNode.layer + 1;//next层号等于当前顶点层号加1 //如果next的编号未被加入过队列 if (inq[next.v] == false) { q.push(next);//将next入队 inq[next.v] = true;//next的编号设为已被加入过队列 } } } } /* 本人总结为： dfs = 未被访问 + 可达 + 递归(实质栈) bfs = 未曾入过队列 + 可达 + 队列 以上只针对一个连通块，若要对图遍历 则利用for循环对每个未曾被访问的结 点进行dfs或bfs即可。 */