关于深度优先遍历图的非递归算法的一个讨论 |
您所在的位置：网站首页 › 深度优先搜索遍历连通图的递归算法 › 关于深度优先遍历图的非递归算法的一个讨论 |
关于深度优先遍历图的非递归算法的一个讨论
|
参考： http://www.cnblogs.com/kubixuesheng/p/4399705.html http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html
图的深度优先遍历递归算法大概如下：  
1 //访问标志数组
2 int visited[MAX] = {0};
3
4 //用邻接表方式实现深度优先搜索(递归方式）
5 //v 传入的是第一个需要访问的顶点
6 void DFS(MGraph G, int v)
7 {
8 //图的顶点的搜索指针
9 ArcNode *p;
10 //置已访问标记
11 visited[v] = 1;
12 //输出被访问顶点的编号
13 printf("%d ", v);
14 //p指向顶点v的第一条弧的弧头结点
15 p = G.vertices[v].firstarc;
16 while (p != NULL)
17 {
18 //若p->adjvex顶点未访问,递归访问它
19 if (visited[p->adjvex] == 0)
20 {
21 DFS(G, p->adjvex);
22 }
23 //p指向顶点v的下一条弧的弧头结点
24 p = p->nextarc;
25 }
26 }
View Code
图的广度优先遍历算法大概如下：
1 #include
2 #include
3 using namespace std;
4
5 const int MAX = 10;
6 //辅助队列的初始化，置空的辅助队列Q，类似二叉树的层序遍历过程
7 queue q;
8 //访问标记数组
9 bool visited[MAX];
10 //图的广度优先搜索算法
11 void BFSTraverse(Graph G, void (*visit)(int v))
12 {
13 int v = 0;
14 //初始化访问标记的数组
15 for (v = 0; v < G.vexnum; v++)
16 {
17 visited[v] = false;
18 }
19 //依次遍历整个图的结点
20 for (v = 0; v < G.vexnum; v++)
21 {
22 //如果v尚未访问，则访问 v
23 if (!visited[v])
24 {
25 //把 v 顶点对应的数组下标处的元素置为真，代表已经访问了
26 visited[v] = true;
27 //然后v入队列，利用了队列的先进先出的性质
28 q.push(v);
29 //访问 v，打印处理
30 cout = 0; w = NextAdjVex(G,u,w))
39 {
40 //w为u的尚未访问的邻接顶点
41 if (!visited[w])
42 {
43 visited[w] = true;
44 //然后 w 入队列，利用了队列的先进先出的性质
45 q.push(w);
46 //访问 w，打印处理
47 cout 0)
107 {
108 MGraph G;
109 G.n=n;
110 G.e=e;
111 creatMGraph(G);
112 DFS(G,0);
113 printf("\n");
114 // DFS1(G,0);
115 // printf("\n");
116 // BFS(G,0);
117 // printf("\n");
118 }
119 return 0;
120 }
View Code
在网络上查了很多资料，又去看了好几本教材，发现这些地方对图的深度优先遍历算法的讲解，基本都是用递归算法实现的。对非递归算法实现描述不是很多。上面第三段代码实现了非递归深搜算法。
在寻找资料过程中，也在思考如何实现，大概设计了如下两种算法： 算法一：（这个是一个错误的思路） 1 st.push(v1)//出发点入栈 2 while(!st.empty()) 3 { 4 temp=st.top(); st.pop();//临时备份栈顶节点到temp，删除栈顶节点 5 printf(temp);//访问temp（原先的栈顶节点） 6 根据temp寻找所有未曾访问的相邻节点，并把这些节点入栈 7 }算法二： 1 printf(v1);//访问出发节点 2 st.push(v1);//出发点入栈 3 while(!st.empty()) 4 { 5 temp=st.top();//读取栈顶节点到temp 6 循环遍历temp的所有相邻节点： 7 ｛ 8 如果（发现一个未曾访问的相邻节点w）： 9 ｛ 10 printf(w);//访问节点w 11 st.push(w);//把w入栈 12 退出循环 13 ｝ 14 ｝ 15 if(temp没有未曾访问的相邻节点) 16 st.pop();//删除栈顶节点 17 }这两种算法，假如仅仅是对树进行深搜，应该是没有错的。但是对图进行深搜，算法一确实不正确的。看下面这个例子：
对这个图从V0出发做深搜，假如按照算法一操作，假设节点入栈顺序为：V0，V1，V3，…… 其中v1和V3入栈时，V0已经出栈。但是取出栈顶V3做访问操作，然后再把V3的相邻未曾访问节点入栈，则会使得V1再一次 入栈。所以算法一不正确。
|
【本文地址】
今日新闻 |
推荐新闻 |