当前位置：文档之家 › 图的深度遍历与广度遍历

图的深度遍历与广度遍历

  • 格式：docx
  • 大小：31.88 KB
  • 文档页数：5

图的深度遍历和广度遍历程序源代码如下：
#include"stdio.h"
#include"stdlib.h"
#define MAXQSIZE 100
#define MVNum 100
int visited[100];
typedef struct
{
char *base;
int front;
int rear;
}SqQueue;
int InitQueue(SqQueue &Q) //初始化队列
{
Q.base=new char[MAXQSIZE];
if(!Q.base)
exit(-1); //存储失败
Q.front=Q.rear=0; //队列为空
return 1;
}
int QueueEmpty(SqQueue &Q) //判断队非空
{
if(Q.front==Q.rear)
return 0;
return 1;
}
int EnQueue(SqQueue &Q,char e) //入队
{
if((Q.rear+1)%MAXQSIZE==Q.front) //队满
return 0;
Q.base[Q.rear]=e; //新元素插入队尾
Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1
return 1;
}
int DeQueue(SqQueue &Q,char &e) //出队
{
if(Q.front==Q.rear)
return 0; //队空
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return 1;
}
int GetHead(SqQueue Q) //取队头元素{
if(Q.front!=Q.rear)
return Q.base[Q.front];
}
typedef struct //定义图
{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G,char u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i])
return i;
return -1;
}
int CreateUDN(AMGraph &G) //创建图{
int i,j,k;
char v1,v2;
printf("输入顶点个数和边的个数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
getchar();
printf("请输入图:\n");
for(i=0;i<G.vexnum;++i)
scanf("%c",&G.vexs[i]);
getchar();
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=0;
for(k=0;k<G.arcnum;++k)
{
scanf("%c%c",&v1,&v2);
getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=1;
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}
void DFS(AMGraph G,int v) //深度遍历图{
int w;
printf("%c",G.vexs[v]);
visited[v]=1;
for(w=0;w<G.vexnum;w++)
if((G.arcs[v][w]!=0)&&(!visited[w]))
DFS(G,w);
}
void DFSTraverse(AMGraph G)
{
int v;
for(v=0;v<G.vexnum;++v)
visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(!visited[v])
DFS(G,v);
}
void BFS(AMGraph G,int v) //广度遍历
{
int w;
SqQueue Q;
printf("%c",G.vexs[v]); //访问第v个顶点
visited[v]=1;
InitQueue(Q); //初始化队列，置空
EnQueue(Q,v); //v进队
char u=GetHead(Q);
while(!QueueEmpty(Q)) //队列非空
{
DeQueue(Q,u); //队头元素出队,置为u
for(w=0;w<G.vexs[v];w++)
if(visited[w])
{
scanf("%d",&w);
visited[w]=1;
EnQueue(Q,w); //w进队
}
}
}
void BFSTraverse(AMGraph G)
{
int v;
for(v=0;v<G.vexnum;++v)
visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(!visited[v])
BFS(G,v);
}
main()
{
AMGraph G;
CreateUDN(G);
printf("深度遍历结果:\n");
DFSTraverse(G);
printf("\n广度遍历结果:\n");
BFSTraverse(G);
printf("\n");
}
深度遍历结果：abdecfg 广度遍历结果：abcdefg。

合集下载

第15讲图的遍历

第15讲图的遍历


V6
V8
V8
V7
V5 深度优先生成树
V8 V1
V2
V3
V4 V5 V6 V7
V8 广度优先生成树
27
例A
B
CD E
F
GH
I
K
J
L
M
A
D
G
LCF
KI E
H M
JB
深度优先生成森林
28
二、图的连通性问题
▪1、生成树和生成森林
▪ 说明
G
▪ 一个图可以有许多棵不同的生成树
KI
▪ 所有生成树具有以下共同特点：
g.NextAdjVex(v, w))
{
if (g.GetTag(w) == UNVISITED)
{
g.SetTag(w, VISITED);
g.GetElem(w, e);
Visit(e);
q.InQueue(w);
}
}}}
24
一、图的遍历 两种遍历的比较
V0
V1 V4
V0
V1 V4
V3
V2 V5
16
一、图的遍历
广度优先遍历序列?入队序列?出队序列?
V1
V2
V3
V1
V4
V5 V6
V7
V8
遍历序列： V1
17
一、图的遍历
广度优先遍历序列?入队序列?出队序列?
V1
V2
V3
V2 V3
V4
V5 V6
V7
V8
遍历序列： V1 V2 V3
18
一、图的遍历
广度优先遍历序列?入队序列?出队序列?
V1
V2
第7章图的深度和广度优先搜索遍历算法

第7章图的深度和广度优先搜索遍历算法

7.3 图的遍历
和树的遍历类似，我们希望从图中某顶点出发对图中每个顶点访问一次，而且只访问 一次，这一过程称为图的遍历(traversing graph)。 本节介绍两种遍历图的规则：深度优先搜索和广度优先搜索。 这两种方法既适用于无向图，也适用于有向图。
7.3.1 深度优先搜索遍历 一．思路： 从图中某一点（如A）开始，先访问这一点，然后任选它的一个邻点（如V0） 访问，访问完该点后，再任选这个点V0的一个邻点 （ 如 W ）访问，如此向 纵深方向访问。直到某个点没有其他未访问的邻点为止，则返回到前一个点。 再任选它的另一个未访问过的邻点 （ 如X ）继续重复上述过程的访问，直到全 部点访问完为止。 图(a)的遍历的结果:V1V2V4V8V5V3V6V7 或V1V3V7V6V2V5V8V4
p
v0 w x v 1
V
0
v 2
V
0
typedef struct {VEXNODE adjlist［MAXLEN］; // 邻接链表表头向量 int vexnum, arcnum; // 顶点数和边数 int kind; // 图的类型 }ADJGRAPH;
W W
X
X
7.3.2 广度优先搜索遍历 一.思路：
V
0
A V
0
W W
XXΒιβλιοθήκη 二．深度优先搜索算法的文字描述： 算法中设一数组visited，表示顶点是否访问过的标志。数组长度为 图的顶点数，初值均置为0，表示顶点均未被访问，当Vi被访问过，即 将visitsd对应分量置为1。将该数组设为全局变量。 { 确定从G中某一顶点V0出发，访问V0； visited［V0］ = 1； 找出G中V0的第一个邻接顶点->w； while (w存在) do { if visited［w］ == 0 继续进行深度优先搜索； 找出G中V0的下一个邻接顶点->w；} }
数据结构 第七章-图2

数据结构 第七章-图2


{DeQueue(Q,u); /*队头元素出队,并赋值给u*/
/*访问u所有未被访问的邻接点*/
for(w=0; w<G.vexnum; w++;)
if (G.arcs[u,w].adj && !visited[w])
{ visited[w]=1; Visit(w); EnQueue(Q,w); }
void DFS(Graph G, int v)
7.3 图的遍历
visited 0 0 10 20 30 40
……
{/* 从第v个顶点出发，递归地深度优先遍历图G*/
/* v是顶点在一维数组中的位置，假设G是非空图*/
visited[v] =1;
Visit(v); /*访问第v个顶点*/
for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) )
效率。
2
7.3 图的遍历
7.3 图的遍历：从图的某顶点出发，访问图中所有顶点， 并且每个顶点仅访问一次。
图结构的遍历复杂性：
（1）在图结构中，没有一个“自然”的首结点，图中的任 意一个顶点都可以作为第一个被访问的结点
（2）在非连通图中，从一个顶点出发，只能访问它所在的 连通分量上的所有顶点，因此，还需考虑如何选取下一个出 发点以访问图中的其余连通分量
} }/*DFSAL*/
8
7.3 图的遍历
在遍历时，对图中每个顶点至多调用一次DFS函数，因为 一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。 因此，遍历图的过程实质上是对每个顶点查找其邻接点的过 程。其耗费的时间则取决于所采用的存储结构。
用邻接矩阵做图的存储结构时，查找各个顶点的邻接点所 需的时间为O(n2)，其中n为图中顶点数。当以邻接矩阵做存 储结构时，深度优先搜索遍历图的时间复杂度为O(n2+n)。
深度遍历和广度遍历例题

深度遍历和广度遍历例题

深度遍历和广度遍历例题深度遍历（Depth First Search, DFS）和广度遍历（Breadth First Search, BFS）是图遍历的两种常用方法。

在本文中，将介绍深度遍历和广度遍历的定义、原理、应用以及两种方法的例题。

一、深度遍历（DFS）深度遍历使用堆栈（Stack）实现，其基本思想是先访问根节点，然后再递归地访问其相邻节点，直到所有节点都被访问。

深度遍历能够搜索到最深层次的节点，但可能会陷入死循环。

1. 深度遍历的应用场景：深度遍历常用于解决图的连通性问题、拓扑排序、求解图中的环等。

另外，也可以应用于解决迷宫问题、数独等。

2. 深度遍历的基本过程：（1）首先访问初始节点，并标记为已访问。

（2）递归地访问初始节点的相邻节点，对于每一个相邻节点，若未被访问，则进行递归访问。

（3）重复步骤（2），直到所有节点都被访问。

3. 深度遍历的例题：假设有以下有向图：A -> B，A -> C，B -> D，B -> E，C -> F，D -> G，E -> H，F -> G，G -> E，H -> E现在要求从节点A开始进行深度遍历，从A到E的路径请写出所有可能的路径。

答案：A -> B -> D -> G -> E，A -> B -> E，A -> C -> F -> G -> E，A -> C -> F -> G -> E，A -> B -> D -> G -> E -> H -> E，A -> C -> F -> G -> E -> H -> E二、广度遍历（BFS）广度遍历使用队列（Queue）实现，其基本思想是先访问根节点，然后再按照层次逐层访问其相邻节点，直到所有节点都被访问。