分析并上机调试以下程序：
1.图的深度优先搜索遍历
/*程序6-4:*/
#include<malloc.h>
#include<stdio.h>
#define MAX_VEX 50
typedef structarcnode /*定义表结点*/
{
int vextex;
struct arcnode *next;
}ARCNODE;
typedef structvexnode /*定义头结点*/
{
int data;
ARCNODE* firstarc;
}VEXNODE;
VEXNODEadjlist[MAX_VEX]; /*定义表头向量adjlist*/
intcreatadjlist() /*建立邻接表*/
{
ARCNODE*ptr;
int arcnum,vexnum,k,v1,v2;
printf("input vexnum,arcnum:\n");
scanf("%d,%d",&vexnum,&arcnum); /*输入图的顶点数和边数（弧数）*/
for(k=0;k<vexnum;k++)
adjlist[k].firstarc=NULL; /*为邻接链表的adjlist数组各元素的链域赋初值*/
for(k=0;k<arcnum;k++) /*为adjlist数组的各元素分别建立各自的链表*/
{
printf("v1,v2=");
scanf("%d,%d",&v1,&v2);
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*给结点V1 的相邻结点V2 分配内存空间*/
ptr->vextex=v2;
ptr->next=adjlist[v1].firstarc;
adjlist[v1].firstarc=ptr; /*将相邻结点V2 插入表头结点V1 之后*/
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*对于有向图此后的四行语句要删除*/
ptr->vextex=v1; /*给结点V2 的相邻结点V1 分配内存空间*/
ptr->next=adjlist[v2].firstarc;
adjlist[v2].firstarc=ptr; /*将相邻结点V1 插入表头结点V2 之后*/
}
return(vexnum);
}
void dfs(v) /*从某顶点V出发按深度优先搜索进行图的遍历*/
int v;
{
int w;
ARCNODE *p;
p=adjlist[v].firstarc;
printf("%d\n",v); /*输出访问的顶点*/
adjlist[v].data=1; /*顶点标志域置1，表明已访问过*/
while(p!=NULL)
{
w=p->vextex; /*取出顶点V的某相邻顶点的序号*/
if(adjlist[w].data==0)
dfs(w);
/*如果该顶点未被访问过则递归调用，从该顶点出发，沿着它的各相邻顶点向下搜索*/
p=p->next;
}
}
main()
{
int n;
/*ARCNODE *p;*/
n=creatadjlist(adjlist); /*建立邻接表并返回顶点的个数*/
printf("dfs output:");
dfs(0); /*从顶点0出发，按深度优先搜索进行图的遍历*/
}
程序运行结果：
/*对于图6.21中的A图，运行时输入数据及运行结果显示如下：*/
input vexnum，arcnum:
4，5（回车）
v1，v2=0，1（回车）
v1，v2=0，2（回车）
v1，v2=1，2（回车）
v1，v2=1，3（回车）
v1，v2=2，3（回车）
dfs output：0 2 3 1
2.图的深度优先搜索遍历
/*程序6-5：*/
#include<malloc.h>
#include<stdio.h>
#define MAX_VEX 50
typedef structarcnode /*定义表结点*/
{
int vextex;
struct arcnode *next;
}ARCNODE;
typedef structvexnode /*定义头结点*/
{
int data;
ARCNODE *firstarc;
}VEXNODE;
VEXNODEadjlist[MAX_VEX]; /*定义表头向量adjlist*/
intcreatadjlist() /*建立邻接表*/
{
ARCNODE *ptr;
int arcnum,vexnum,k,v1,v2;
printf("\n input vexnum,arcnum: ");
scanf("%d,%d",&vexnum,&arcnum); /*输入图的顶点数和边数（弧数）*/
for(k=0;k<vexnum;k++)
adjlist[k].firstarc=NULL; /*为邻接链表的adjlist数组各元素的链域赋初值*/
for(k=0;k<arcnum;k++) /*为adjlist数组的各元素分别建立各自的链表*/
{
printf("v1,v2=");
scanf("%d,%d",&v1,&v2);
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*给结点V1 的相邻结点V2 分配内存空间*/
ptr->vextex=v2;
ptr->next=adjlist[v1].firstarc;
adjlist[v1].firstarc=ptr; /*将相邻结点V2 插入表头结点V1 之后*/
ptr=(ARCNODE*)malloc(sizeof(ARCNODE));
/*对于有向图此后的四行语句要删除*/
ptr->vextex=v1; /*给结点V2 的相邻结点V1 分配内存空间*/
ptr->next=adjlist[v2].firstarc;
adjlist[v2].firstarc=ptr; /*将相邻结点V1 插入表头结点V2 之后*/
}
return(vexnum);
}
void bfs(v) /*从某顶点V出发按广度优先搜索进行图的遍历*/
int v;
{
int queue[MAX_VEX];
int front=0,rear=1;
/*int w;*/
ARCNODE*p;
printf("bfs output:");
p=adjlist[v].firstarc;
printf("%d\n",v); /*访问初始顶点*/
adjlist[v].data=1;
queue[rear]=v; /*初始顶点入队列*/
while(front!=rear) /*队列不为空时循环*/
{
front=(front+1)%MAX_VEX;
v=queue[front]; /*按访问次序依次出队列*/
p=adjlist[v].firstarc; /*找V的邻接点*/
while(p!=NULL)
{
if(adjlist[p->vextex].data==0)
{
adjlist[p->vextex].data=1;
printf("%d\n",p->vextex); /*访问该点并使之入队列*/
rear=(rear+1)%MAX_VEX;
queue[rear]=p->vextex;
}
p=p->next; /*找V的下一个邻接点*/
}
}
}
main()
{
int n;
/*ARCNODE *p;*/
n=creatadjlist(); /*建立邻接表并返回顶点的个数*/
bfs(0); /*从顶点0出发，按广度优先搜索进行图的遍历*/
}
程序运行结果：
/*对于图6.23中的A图，运行时输入数据及运行结果显示如下：*/
input vexnum，arcnum:4，5（回车）
v1，v2=0，1（回车）
v1，v2=0，2（回车）
v1，v2=1，2（回车）
v1，v2=1，3（回车）
v1，v2=2，3（回车）
bfs output:0 2 1 3
