数据结构实验指导书

int i, v; EDGENODE *p;

LINKQUEUE que, *q;

q = &que;

initlinkqueue(q);

for(i = 0; i < adjg.vexnum; i++)

visited[i] = 0; /*visited数组初始化，均置0*/ visited[vi-1] = 1; /*从编号为vi的顶点出发，visited数组对应置1*/ printf(\输出vi顶点*/ enlinkqueue(q,vi); /*vi顶点入队列*/

while(!emptylinkqueue(q)) /*队列不空，继续进行遍历*/ {v = dellinkqueue(q); /*取队头元素放入v变量中*/ v --;

p = adjg.adjlist[v].link;

while(p != NULL) /*对应单链表不空，进行广度遍历*/ {if(visited[p->adjvex] == 0) {visited[p->adjvex] = 1;

printf(\

enlinkqueue(q, (p->adjvex)+1);} /*遍历到的结点编号入队列*/ p = p->next;} } }

main() { ADJGRAPH ag; int j;

printf(\连通图的广度遍历\\n\

ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/ printf(\输入广度遍历起始顶点(1 -- %d) : \ scanf(\

printf(\广度遍历结果序列 : \

bfs(ag,j); /*连通图的广度遍历算法*/ printf(\}

深度优先遍历程序清单：

#include #include \#include

int visited[MAXLEN];

29

ADJGRAPH creat_adjgraph() {

EDGENODE *p; int i, s, d; ADJGRAPH adjg;

adjg.kind = 2;

printf(\输入顶点数和边数(用逗号隔开) : \scanf(\

adjg.vexnum = s; /*存放顶点数在adjg.vexnum中 */ adjg.arcnum = d; /*存放边点数在adjg.arcnum中*/ printf(\

for(i = 0; i < adjg.vexnum; i++) /*输入顶点的值*/ {printf(\输入顶点 %d 的值 : \ scanf(\ fflush(stdin);

adjg.adjlist[i].link = NULL;} printf(\

for(i = 0; i < adjg.arcnum; i++)

{printf(\输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): \

scanf(\&s, &d); /*输入边的起始顶点和终止顶点*/ fflush(stdin);

while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum) { printf(\输入错，重新输入: \ scanf(\ s --; d --;

p = malloc(sizeof(EDGENODE)); /*建立一个和边相关的结点*/ p->adjvex = d;

p->next = adjg.adjlist[s].link; /*挂到对应的单链表上*/ adjg.adjlist[s].link = p;

p = malloc(sizeof(EDGENODE)); /*建立另一个和边相关的结点*/ p->adjvex = s;

p->next = adjg.adjlist[d].link; /*挂到对应的单链表上*/ adjg.adjlist[d].link = p;} return adjg; }

void dfs(ADJGRAPH adjg, int v){

/*连通图的深度遍历算法：从v顶点出发*/ EDGENODE *p;

visited[v - 1] = 1; /*从编号为v的顶点出发，visited数组对应置1*/

30

v --;

printf(\输出v顶点*/

p = adjg.adjlist[v].link; /*取单链表的第一个结点*/ while(p != NULL) /*对应单链表不空，进行遍历*/ { if(visited[p->adjvex] == 0) /*如果有未被访问过的结点*/ dfs(adjg, (p->adjvex)+1); /*递归调用深度遍历算法*/

p = p->next;} /*取单链表的下一个结点*/ }

main() {

ADJGRAPH ag; int i;

printf(\连通图的深度遍历\\n\

ag = creat_adjgraph(); /*建立连通图的邻接链表结构*/ for(i = 0; i < ag.vexnum; i++) /*visited数组初始化，均置0*/ visited[i] = 0;

printf(\输入深度遍历起始顶点(1 -- %d) : \ scanf(\

printf(\深度遍结果序列 : \

dfs(ag,i); /*连通图的深度遍历算法*/ printf(\}

31