发布时间 : 星期四 文章数据结构实验指导书更新完毕开始阅读
实验四、图的遍历操作
一、
目的
掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。 二、 作。 三、
DFS和BFS 的基本思想
深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，??依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。
广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后
访问与Vo相邻的所有未被访问过的顶点V1，V2，??，Vt；再依次访问与V1，V2，??，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。
四、
示例程序
1． 邻接矩阵作为存储结构的程序示例 #include\#include\
#define MaxVertexNum 100 //定义最大顶点数 typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) {
int i,j,k; char a;
printf(\ scanf(\输入顶点数和边数 scanf(\ printf(\ for(i=0;i
13
要求
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操
scanf(\
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;i
for(j=0;j
G->edges[i][j]=0; //初始化邻接矩阵
printf(\
for(k=0;k
//=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j;
printf(\访问顶点Vi visited[i]=TRUE; //置已访问标志 for(j=0;j
void DFS(MGraph *G) { int i;
for(i=0;i
//===========BFS：广度优先遍历======= void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
14
scanf(\输入边（Vi，Vj）的顶点序号 G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
for(i=0;i
for(i=0;i
cq[i]=-1; //队列初始化 printf(\访问源点Vk visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行 i=cq[f]; f=f+1; //Vf出队
for(j=0;j
r=r+1; cq[r]=j; //访问过Vj入队
}
}
}
//==========main===== void main() {
int i; MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间 CreatMGraph(G); //建立邻接矩阵 printf(\
DFS(G); //深度优先遍历 printf(\
printf(\
BFS(G,3); //以序号为3的顶点开始广度优先遍历 printf(\}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9 V0 Input Vertex string: 01234567 Input edges,Creat Adjacency Matrix V1 V2 0 1 V3 0 2 V4 V5 V6 1 3 1 4 2 5
V7
图G的示例 15
2 6 3 7 4 7 5 6
Print Graph DFS: 01374256 Print Graph BFS: 31704256
2． 邻接链表作为存储结构程序示例 #include\#include\
#define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode;
typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数 } ALGraph; //图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G) {
int i,j,k; char a;
EdgeNode *s; //定义边表结点
printf(\ scanf(\读入顶点数和边数 scanf(\
printf(\ for(i=0;i
scanf(\
G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL; //边表置为空表
}
printf(\
16