发布时间 : 星期四 文章数据结构课程设计-图的遍历和构建更新完毕开始阅读2964e7a0f524ccbff1218486
visited3[i]=1，未被访问时visited1[i]=0或visited3[i]=0。先访问初始点Vi，并标志其已被访问。若是邻接矩阵表示时将定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。
深度优先遍历的相关代码在下面的源代码中给出。
4.2.2 广度优先遍历图
要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组visited2[n]（邻接矩阵表示）和visited4[n]（邻接表表示）和以标记结点是否被访问。同样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次执行时k的值为i，即front=(front+1)%maxsize。然后取Vk邻接表的表头指针int k=p[front]; enode* p=a[k]。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。访问完后，将p指向p->next。这样就可以访问所有结点，完成图的广度优先遍历。
广度优先遍历的相关代码在下面的源代码中给出。
4.3 main函数
在main函数中运用了菜单。用主菜单来控制是选择邻接矩阵的存储表示还是邻接表的存储表示，用子菜单来控制选择深度优先遍历还是广度优先遍历。
9
4.4 图的大致流程表
图的存储与遍历 邻接矩阵表示法 邻接表表示法 各顶点的度 各顶点的度 深度优先遍历 广度优先遍历 深度优先遍历 广度优先遍历
第五章 源代码
程序 图的存储与遍历
#include
char vexs[max]; int arcs[max][max];
int vexsnum,arcsnum; /* 顶点个数及边的个数 */ }graph;
void creatgraph(graph *G) /* 建立邻接矩阵的无向图 */ {
int i,j,k,sum;
10
printf(\请输入顶点个数及边的个数：\\n\scanf(\printf(\请读入顶点信息，建立顶点表：\\n\getchar();
for(i=0;i
G->vexs[i]=getchar();
for(i=0;i
for(j=0;j
G->arcs[i][j]=0; /* 邻接矩阵初始化 */
printf(\请输入相邻接的两边的顶点信息：\\n\for(k=0;k
scanf(\G->arcs[i][j]=1; G->arcs[j][i]=1;
} /* 读入边（Vi,Vj） */ printf(\输出的邻接矩阵为：\\n\for(i=0;i
printf(\
for(j=0;j
printf(\
} /* 邻接矩阵的输出 */ printf(\输出邻接矩阵Vi顶点的度为：\\n\for(i=0;i
sum=0;
for(j=0;j
sum++;
11
}
printf(\的度为：%d\\n\
} /* 各顶点的度 */
#define n 4 #define m 5 typedef char vextype; typedef struct node {
int adjvex; /* 邻接点域 */ struct node *next; /* 链域 */ }enode; /* 边表结点 */ typedef struct {
vextype vertex; /* 顶点信息 */ enode *link; /* 边表头指针 */ }vnode; /* 顶点表结点 */ vnode a[n];
void creatlist() /* 建立无向图的邻接表 */ {
int i,j,k,sum; enode *s;
printf(\请读入顶点信息，建立顶点表：\\n\ getchar(); for(i=0;i a[i].vertex=getchar(); a[i].link=NULL; /* 边表头指针初始化 */ }