实事上，这些遍历问题只是老生常谈的bfs和dfs过程，学习图的时候前面的图的定义和存储都没有讲解，但定义那些初试就学过，这里更注重讲解图的存储，再顺带把其遍历解决。
图的存储有邻接矩阵和邻接表这几种方式，邻接矩阵是个二维数组，邻接表是一个点集加链表的形式，这里我们想用vector来实现邻接表。
为什么vector可以实现邻接表，注意邻接表是点集加链表，为什么加链表是因为链表长度不一定需要确定，恰好vector也是一个可变数组，所以可以定义node后，用vector<node>Adj[N]实现邻接表。特别当题目不涉及权重，只管连通信息时，直接用vector<int>Adj[N]即可模拟邻接表
之后就是基于邻接表的两种遍历
#include<iostream> #include<vector> #include<queue> using namespace std; struct node{ int vex; int weight; }; vector <node>Adj[1000];//定义邻接表 int n;//结点数 bool vis[1000]; void dfs(int u) { vis[u]=true; printf("%d",u); for(int i=0;i<Adj[u].size();i++) { int k=Adj[u][i].vex; if(!vis[k]) dfs(k); } } void dfstrave() //深度遍历图G { for(int i=1;i<=n;i++) vis[i]=false; for(int i=1;i<=n;i++){ if(!vis[i]) dfs(i); } } void bfs(int u) { queue<int>q; q.push(u); int temp; while(!q.empty()){ temp=q.front();q.pop(); vis[temp]=true; printf("%d",temp); for(int i=0;i<Adj[temp].size();i++){ int k=Adj[u][i].vex; if(!vis[k]) q.push(k); } } } void bfstrave() //广度遍历图G { for(int i=1;i<=n;i++) vis[i]=false; for(int i=1;i<=n;i++){ if(!vis[i]) dfs(i); } } int main(){ return 0; }
如果要解决连通分量个数问题在遍历是加入一个数据看调用了几次bfs或dfs即可。
