图论-图的遍历

遍历是很多图论算法的基础，所谓图的遍历（ graph traversal），也称为搜索（ search），就是从图中某个顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次。遍历可以采取两种方法进行：

深度优先搜索（ DFS： depth first search）；

广度优先搜索（ BFS： breadth first search）。

现在，提供几种图的遍历的方法。（注意有些代码不能实现有向图）

算是遍历的模（ｍｕ）板吧！

提供图：

对应的测试数据：

8 9
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 7

友情提示：注意比较一下几种方法输出的不同之处

1.深搜：

　　和深搜差不多，在深搜的基础上稍作处理即可；并且注意在访问过的上的标记；

代码实现：

用邻接矩阵：

 1 #include<iostream>
 2 using namespace std;
 3 #define N 2010
 4 int n,m;
 5 int map[N][N],vis[N];
 6 void dfs(int w)
 7 {
 8     vis[w]=1;
 9     cout<<w<<" ";
10     for(int i=1;i<=n;++i)
11     {
12         if(!vis[i]&&map[w][i])
13         {
14             dfs(i);
15             
16         }
17     }
18 }
19 int main()
20 {
21     cin>>n>>m;
22     for(int i=1;i<=m;++i)
23     {
24         int x,y;
25         cin>>x>>y;
26         map[x][y]=1;
27         map[y][x]=1;
28     }
29     dfs(1);
30     return 0;
31 }

邻接链表：

 1 #include<iostream>
 2 using namespace std;
 3 #define N 2010
 4 int n,m;
 5 int map[N][N],vis[N];
 6 void dfs(int w)
 7 {
 8     vis[w]=1;
 9     cout<<w<<" ";
10     for(int i=1;i<=map[w][0];++i)
11     {
12         if(!vis[map[w][i]])
13         {
14             dfs(map[w][i]);
15         }
16     }
17 }
18 int main()
19 {
20     cin>>n>>m;
21     for(int i=1;i<=m;++i)
22     {
23         int x,y;
24         cin>>x>>y;
25         map[x][++map[x][0]]=y;
26         map[y][++map[y][0]]=x;
27     }
28     dfs(1);
29     return 0;
30 }

2.广搜的方法

　　与广搜差不多，在广搜的基础上稍作调整即可；

代码实现：

邻接矩阵

 1 #include<iostream>
 2 using namespace std;
 3 #define N 2010
 4 int n,m;
 5 int team[N],map[N][N];
 6 bool vis[N];
 7 int head,tail;
 8 void bfs(int w)
 9 {
10     vis[w]=1;
11     team[tail++]=w;
12     cout<<w;
13     while(head<tail)
14     {
15         int d=team[head];
16         head++;
17         for(int i=1;i<=n;++i)
18             if(!vis[i]&&map[d][i])
19             {
20                 cout<<" "<<i;
21                 team[tail++]=i;
22                 vis[i]=1;
23             }
24     }
25 }
26 int main()
27 {
28     cin>>n>>m;
29     for(int i=1;i<=m;++i)
30     {
31         int x,y;
32         cin>>x>>y;
33         map[x][y]=1;
34         map[y][x]=1;
35     }
36     bfs(1);//从1开始遍历 
37     return 0;
38 }

邻接链表

 1 #include<iostream>
 2 using namespace std;
 3 #define N 2010
 4 int map[N][N];  
 5 bool vis[N];  //标记是否访问过 
 6 int team[N];  //队列 
 7 int n,m,head,tail; 
 8 void bfs(int w)
 9 {
10     vis[w]=1;
11     cout<<w;
12     team[tail++]=w;
13     while(head<tail)
14     {
15         int d=team[head];
16         head++;
17         for(int i=1;i<=map[d][0];++i)
18         {
19             if(!vis[map[d][i]])
20             {
21                 cout<<" "<<map[d][i]; 
22                 team[tail++]=map[d][i];
23                 vis[map[d][i]]=1;
24             }
25         }
26     }
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1;i<=m;++i)
32     {
33         int x,y;
34         cin>>x>>y;
35         map[x][++map[x][0]]=y;
36         map[y][++map[y][0]]=x;
37     }
38     bfs(1);  //从1开始访问 
39     return 0;
40 }