图的遍历.txt

图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础

#define MAX 20
#include<stdio.h>
#include <stdlib.h>
typedef struct QNode
{
int data;
struct QNode *next;
}QNode;
typedef struct 
{
QNode *front;
QNode *rear;
}Queue;//定义一个队列
typedef struct ArcNode 
{
int adjvex;//邻接点顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode//头结点
{
char data;
ArcNode *firstarc;//邻接链表头指针
}VNode;
typedef struct
{
VNode adjlist[MAX];
int v,a;//图的顶点数和边数
}algraph;
int InitQueue(Queue *s)//构造一个空的对列
{
s->front=s->rear=(QNode*)malloc(sizeof(QNode));
if(!s->front)
return(0);
s->front->next=NULL;
return 1;
} 
Enqueue (Queue *s,int e)//入队列 
{
QNode *p;
p=(QNode*)malloc (sizeof(QNode));
if (!p)return(0);
p->data=e;
p->next=NULL;
s->rear->next=p;
s->rear=p;
return 1;
}
DEQueue (Queue *q, int *e)//出队列
{
QNode *p;
if (q->front==q->rear)return 1;//表示这是空对列
p=q->front->next;
*e=p->data;//附值
q->front->next=p->next;
if (q->rear==p)q->rear=q->front;
free(p);
return 1;
}
int emptyQueue(Queue *q)//判断队列是否为空
{
if(q->front==q->rear)
return 1;
else
return 0;
}
void Buildalgraph(algraph *s)//构建图
{
int i,m,n;
ArcNode *p; 
printf("请输入图的顶点数和边数:");
scanf("%d%d",&s->v,&s->a);
getchar();
printf("请输入%d个顶点的信息:",s->v);//注意输入的时候空格隔开每个顶点之间
for(i=0;i<s->v;i++)
{
scanf("%s",&s->adjlist[i].data); /*读入顶点信息*/
s->adjlist[i].firstarc=NULL; /*边表置为空表*/
}
for(i=0;i<s->a;i++)
{
printf("输入第%d条边(起点序号，终点序号):",i+1); 
scanf("%d%d",&m,&n);//输入无序对 顶点编号0开始
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=n;
p->nextarc=s->adjlist[m].firstarc;
s->adjlist[m].firstarc=p;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=m;
p->nextarc=s->adjlist[n].firstarc;
s->adjlist[n].firstarc=p;
}
}
void print(algraph s)//输出邻接表的和结构
{
ArcNode *p;
int i;
for(i=0;i<s.v;i++)
{
printf("%d",i);
printf("%c",s.adjlist[i].data);
p=s.adjlist[i].firstarc;
while(p)
{
printf("-->%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
int visited[MAX];//用来表示是否访问过
void dfs(algraph s,int i)/*以vi为出发点对邻接表表示的图g进行深度优先遍历*/
{
ArcNode *p;
printf("访问顶点 : %c \n",s.adjlist[i].data);/*访问顶点i*/
visited[i]=1;
p=s.adjlist[i].firstarc;
while (p) /*从p的邻接点出发进行深度优先搜索*/
{ if (!visited[p->adjvex])
dfs(s,p->adjvex);
p=p->nextarc;//找指向下一条弧的指针
}
}
void dfstraverse(algraph s)
{ 
int i;
for (i=0;i<s.v;i++)
visited[i]=0; /*初始化标志数组*/
for (i=0;i<s.v;i++)
if (!visited[i]) /*vi未访问过*/
dfs(s,i);//函数的递归的使用 
}
int visit[MAX];//用来表示是否访问过
void bfs(algraph s)//广度优先遍历函数
{
int i,k;
Queue q;
ArcNode *p;
for(i=0;i<s.v;i++);
visit[i]=0;
InitQueue(&q);
for(i=0;i<s.v;i++)
if (!visit[i])
{
printf("访问顶点:%c \n",s.adjlist[i].data);
visit[i]=1;
Enqueue(&q,i);
while (!emptyQueue(&q))
{
DEQueue(&q,&k);
p=s.adjlist[k].firstarc;
while (p) 
{ 
if (!visited[p->adjvex])
{ 
printf("访问顶点:%c \n",s.adjlist[p->adjvex].data);
visited[p->adjvex]=1;
Enqueue(&q,p->adjvex);
}
p=p->nextarc;
}
}
}
}
void main()
{
algraph s;
Buildalgraph(&s);
print(s);
printf("深度优先遍历:\n");
dfstraverse(s);
printf("广度优先遍历:\n");
bfs(s);
}