关于“图的深度优先遍历”调试问题

什么是图的深度优先遍历？什么是图的广度优先遍历？~

深度优先，就是先遍历它的一个邻节点，这个节点的邻节点。。。然后才遍历其他的邻节点

广度优先，就是先把它所有的邻节点都遍历完以后，再遍历它每个邻节点的邻节点


深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

广度优先遍历(Breadth-FirstTraversal)

1、广度优先遍历的递归定义
设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。

2、广度优先搜索过程
在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。

第五个不是。

aefdbc
a->e->f->d到了d没了，
这个时候往后退到f
遇到c必须是c了。
b只能通过e得到。e显然在f退完了。

/*我将你的程序调试一下,现在搞定了
程序当中你的错误是出在那个void trave(adjlist g,int n)函数当中,
因为你在这个函数当中的第二行声明了一个函数叫做void dfs();而错误
就是出在这个地方,你给的错误的意思是:dfs函数不接受3个参数,
很显然你声明的void dfs()没有3个参数,所以编译时报错了,即使你
在下面给个一个带有3个参数的dfs定义,但是已经太晚了.
故,你要先声明一个带有三个参数的dfs函数
像这样:void dfs(adjlist g,int k,int visited[]);

再改你的一个说法的错误:你说是调试时错误,这句话也是不准确的
应该说是在编译时出错,因为此时程序还没有正式开始运行,也就是
还没有到调试这一步程序就已经有语法上的错误了.

这个是大错误,经过我的解释,我想你应该已经了解了
你这个程序还有几个小错误:
我运行了一下发现了算发上有一点小错误(我猜测这只是你打字时的笔误,而
不是理解上的错误)
错误一:在你的main函数中有一个循环:

for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
}
这个是初始化数组的循环，但是g中的vertex成员变量未被初始化,我将其改为
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
g[k].vertex=k; //这个是我增加的一行
}
因为你的vertex要初始化，要不然，你的dfs函数里面的第四句话
cout<<g[k].vertex;
就会随意打印出一些错误的，未经过初始化的数字出来，因为你没有在任何地方对g[k].vertex赋值

好了这个是第一个错误
下面再看
第二个错误:
在你的main函数中的
for(;;)循环里面有一段

p=(arcnode *)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[i].firstarc;
g[i].firstarc=p;

我将你的g[i].firstarc改为g[j].firstarc，向j这个顶点中加入j到i这条边的信息.
根据你的算法用的应该是邻接表存储无向图的，如果不改为g[j]的话，你就向g[i]中一次插入两个边信息了,分别为从i到j这条边和从j到i这条边，而且程序运行也得不到正确结果的。那有什么意义呢？

好了错误讲完了，希望楼主彻底理解。
我将你的代码修改了一下并给出了一个我测试并且编译通过，运行正确的代码。
你可以直接拷贝运行，如果有什么不懂的话发我邮箱: ddrmsdos@163.com
*/
#include <iostream>
using namespace std;
#define maxnode 40

typedef struct st_arc
{
int adivex; //存放依附于该边的另一顶点在一维数组中的序号
int weigh; //存放和帽哂泄氐男畔ⅲ�缛ㄖ档?
struct st_arc *nextarc; //依附于该顶点的下一个边结点的指针
}arcnode; //链式结构存储边信息

typedef struct
{
int vertex; //存放与顶点有关的信息
struct st_arc *firstarc; //指针域，存放与该顶点相邻接的所有顶点组成的单链表的头指针
}vernode; //存储顶点信息

//注意：在这里声明dfs函数
typedef vernode adjlist[maxnode];
void dfs(adjlist g,int k,int visited[]);
void trave(adjlist g,int n) //当图采用邻接表作存储结构时，深度优先遍历该图
{
int i,visited[maxnode]; //数组visited标志图中的定点是否已被访问
// void dfs(); 函数dfs在trave前面声明了
for(i=0;i<n;i++)
visited[i]=0; //数组初始化
for(i=0;i<n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}

void dfs(adjlist g,int k,int visited[]) //从顶点k出发，深度优先遍历图g
{
arcnode *p;
int w;
visited[k]=1;
cout<<g[k].vertex;
p=g[k].firstarc;
while(p!=NULL)
{
w=p->adivex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}

void main()
{
int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
cout<<"Input node: ";
cin>>n;
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
//注意这个地方，我加入了下面这一行
g[k].vertex=k;
}
for(;;)
{
cout<<"Insert edge i-j: ";
cin>>i>>j;
if(i==-1&&j==-1)
break;
q=(arcnode *)malloc(sizeof(arcnode));
q->adivex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[j].firstarc; //

//注意这个地方我将i改为j了
g[j].firstarc=p;

}
cout<<"dfs: ";
trave(g,n);
cout<<endl;
}

/*我将你的程序调试一下,现在搞定了
程序当中你的错误是出在那个void
trave(adjlist
g,int
n)函数当中,
因为你在这个函数当中的第二行声明了一个函数叫做void
dfs();而错误
就是出在这个地方,你给的错误的意思是:dfs函数不接受3个参数,
很显然你声明的void
dfs()没有3个参数,所以编译时报错了,即使你
在下面给个一个带有3个参数的dfs定义,但是已经太晚了.
故,你要先声明一个带有三个参数的dfs函数
像这样:void
dfs(adjlist
g,int
k,int
visited[]);
再改你的一个说法的错误:你说是调试时错误,这句话也是不准确的
应该说是在编译时出错,因为此时程序还没有正式开始运行,也就是
还没有到调试这一步程序就已经有语法上的错误了.
这个是大错误,经过我的解释,我想你应该已经了解了
你这个程序还有几个小错误:
我运行了一下发现了算发上有一点小错误(我猜测这只是你打字时的笔误,而
不是理解上的错误)
错误一:在你的main函数中有一个循环:
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
}
这个是初始化数组的循环，但是g中的vertex成员变量未被初始化,我将其改为
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
g[k].vertex=k;
//这个是我增加的一行
}
因为你的vertex要初始化，要不然，你的dfs函数里面的第四句话
cout<<g[k].vertex;
就会随意打印出一些错误的，未经过初始化的数字出来，因为你没有在任何地方对g[k].vertex赋值
好了这个是第一个错误
下面再看
第二个错误:
在你的main函数中的
for(;;)循环里面有一段
p=(arcnode
*)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[i].firstarc;
g[i].firstarc=p;
我将你的g[i].firstarc改为g[j].firstarc，向j这个顶点中加入j到i这条边的信息.
根据你的算法用的应该是邻接表存储无向图的，如果不改为g[j]的话，你就向g[i]中一次插入两个边信息了,分别为从i到j这条边和从j到i这条边，而且程序运行也得不到正确结果的。那有什么意义呢?
好了错误讲完了，希望楼主彻底理解。
我将你的代码修改了一下并给出了一个我测试并且编译通过，运行正确的代码。
你可以直接拷贝运行，如果有什么不懂的话发我邮箱:
ddrmsdos@163.com
*/
#include
<iostream>
using
namespace
std;
#define
maxnode
40
typedef
struct
st_arc
{
int
adivex;
//存放依附于该边的另一顶点在一维数组中的序号
int
weigh;
//存放和帽哂泄氐男畔ⅲ?缛ㄖ档?
struct
st_arc
*nextarc;
//依附于该顶点的下一个边结点的指针
}arcnode;
//链式结构存储边信息
typedef
struct
{
int
vertex;
//存放与顶点有关的信息
struct
st_arc
*firstarc;
//指针域，存放与该顶点相邻接的所有顶点组成的单链表的头指针
}vernode;
//存储顶点信息
//注意:在这里声明dfs函数
typedef
vernode
adjlist[maxnode];
void
dfs(adjlist
g,int
k,int
visited[]);
void
trave(adjlist
g,int
n)
//当图采用邻接表作存储结构时，深度优先遍历该图
{
int
i,visited[maxnode];
//数组visited标志图中的定点是否已被访问
//
void
dfs();
函数dfs在trave前面声明了
for(i=0;i<n;i++)
visited[i]=0;
//数组初始化
for(i=0;i<n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
void
dfs(adjlist
g,int
k,int
visited[])
//从顶点k出发，深度优先遍历图g
{
arcnode
*p;
int
w;
visited[k]=1;
cout<<g[k].vertex;
p=g[k].firstarc;
while(p!=NULL)
{
w=p->adivex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}
void
main()
{
int
i,j,n,k,v;
arcnode
*p,*q;
adjlist
g;
cout<<"Input
node:
";
cin>>n;
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
//注意这个地方，我加入了下面这一行
g[k].vertex=k;
}
for(;;)
{
cout<<"Insert
edge
i-j:
";
cin>>i>>j;
if(i==-1&&j==-1)
break;
q=(arcnode
*)malloc(sizeof(arcnode));
q->adivex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode
*)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[j].firstarc;
//
//注意这个地方我将i改为j了
g[j].firstarc=p;
}
cout<<"dfs:
";
trave(g,n);
cout<<endl;
}

---

丹阳市18039509876： 关于“图的深度优先遍历”调试问题 - ？
闵牧骨化： /*我将你的程序调试一下,现在搞定了 程序当中你的错误是出在那个void trave(adjlist g,int n)函数当中,因为你在这个函数当中的第二行声明了一个函数叫做void dfs();而错误 就是出在这个地方,你给的错误的意思是:dfs函数不接受3个参数...

丹阳市18039509876： 问一个关于图的深度优先遍历算法实现的问题 - ？
闵牧骨化： 不知道你看的是什么书,代码也只能猜测一下://遍历vertex void MGraph::DFSTraverse(int v) { // 输出当前vertex, 并设为已遍历cout<<vertex[v];visited[v]=1;// 对所有vertex进行测试for(j=0;j<vertexNum;j++) // 如果vertex[j] 和当前的vertex有边相连,并且没有访问过,递归遍历vertex[j]if(arc[v][j]==1&&visited[j]==0)DFSTraverse(j); }从递归关系来看,就是从一个vertex,找和它有边相连的vertex进行遍历,因此,是深度优先遍历.

丹阳市18039509876： 图的深度优先遍历序列什么唯一? - ？
闵牧骨化： 图的深度优先遍历序列不唯一的 .如下面这个图 深度优先遍历可以是ABEFCD ,也可以是ADCBFE. 假设给定图G的初态是所有顶点均未曾访问过.在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,...

丹阳市18039509876： 调用一次深度优先遍历可以访问到图中的所有顶点如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶... - ？
闵牧骨化：[答案] 无向的连通图就是或者有向的强连通图通过任意一个顶点都能够(直接或者通过其他顶点间接地)访问到其他所有顶点,自然一次深度优先遍历就可以访问到所有顶点 无向非连通图一次遍历只能访问到起点所在的连通分量,一个非连通无向图中有几...

丹阳市18039509876： 求c语言图的深度优先遍历算法 - ？
闵牧骨化： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...

丹阳市18039509876： 大哥们帮我看看图的深度优先遍历的问题 - ？
闵牧骨化： main()函数中最有一个 printf(＂\n＂)忘了加分号 ,算法思想有问题,在创建邻接表时,作为无向图,输入(i,j)顶点对时,j结点的link也应该指向i结点.在深度优先遍历时,判断条件p!=NULL)||(top>-1)也不合适,这样的话如果第一个输入的点没有边就直接退出了(并没有遍历整个图),建议改变思路.

丹阳市18039509876： c语言图的深度优先遍历问题 - ？
闵牧骨化： 帮你修改了一下,但是还是报错,是程序逻辑有问题,你看看吧 #include<stdio.h> #include<stdlib.h> //#define INFINITY -10; #define MAX_VERTEX_NUM 20 #define VType int #define VertexType int //此程序面向无向图 //typedef enum {DG, DN, ...

丹阳市18039509876： 对连通图进行一次先深遍历可访问图的全部顶点,对吗? - ？
闵牧骨化： 图的遍历从图中某一顶点出发,按某种搜索方法访遍其余顶点,且使每一顶点仅被访问一次.这一过程称为图的遍历. 遍历图的基本搜索方法有两种:深度优先搜索DFS(Depth First Search)和广度优先搜索BFS(Broad First Search).这两种...

丹阳市18039509876： 图的深度优先遍历序列什么唯一? - ？
闵牧骨化：[答案] 图的深度优先遍历序列不唯一的 如下面这个图 深度优先遍历可以是ABEFCD ,也可以是ADCBFE

丹阳市18039509876： 图的深度优先遍历的结果是不固定吗? - ？
闵牧骨化： 图的遍历概念 1、图的遍历和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问.它是许多图的算法的基础.深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法.它们对无向...