C语言数据结构之图的遍历实例详解

#include <stdio.h> #include <stdlib.h> #define MAX 20  typedef struct ArcNode{   int adjvex;   struct ArcNode *nextarc; }ArcNode;  typedef struct{   char data;   ArcNode *firstarc; }AdjList[MAX];  typedef struct{   AdjList vertices;   int vexnum;   int arcnum; }ALGraph;  typedef struct{   int *base;   int front,rear; }CqQueue;  void InitQueue(CqQueue &Q) {//初始化一个队列   Q.base=(int*)malloc(MAX*sizeof(int));   Q.front=Q.rear=0; }  int QueueEmpty(CqQueue Q) {//判断队列是否为空   if(Q.rear==Q.front)     return 1;   return 0; }  void EnQueue(CqQueue &Q,int e) {//入队操作   if((Q.rear+1)%MAX==Q.front)     return;   Q.base[Q.rear]=e;   Q.rear=(Q.rear+1)%MAX; }  void DeQueue(CqQueue &Q,int &e) {//出队操作   if(Q.rear==Q.front)     return;   e=Q.base[Q.front];   Q.front=(Q.front+1)%MAX; }  int LocateVex(ALGraph G,char v) {//查找顶点v在图G中的位置   for(int i=0;i<G.vexnum;i++)     if(G.vertices[i].data==v)       return i;   return -1;     for(int i=0;i<G.vexnum;i++)     if(G.vexs[i]==v)       return i;   return -1; }  void CreateAdjList(ALGraph &G) {//建立无向图的邻接表   int v,i,j,k;   char v1,v2;   ArcNode *p,*s;   printf("输入无向图的顶点数和边数：/n");   scanf("%d%d",&G.vexnum,&G.arcnum);   getchar();   printf("输入图的顶点信息：/n");   for(v=0;v<G.vexnum;v++){     scanf("%c",&G.vertices[v].data);getchar();     G.vertices[v].firstarc=NULL;   }      printf("输入无向图的边：/n");   for(k=0;k<G.vexnum;k++){     scanf("%c%c",&v1,&v2);     getchar();     i=LocateVex(G,v1);     j=LocateVex(G,v2);     s=(ArcNode*)malloc(sizeof(ArcNode));     s->adjvex=j;     s->nextarc=NULL;     if(!G.vertices[i].firstarc)       G.vertices[i].firstarc=s;     else{       p=G.vertices[i].firstarc;       while(p->nextarc)         p=p->nextarc;       p->nextarc=s;     }     s=(ArcNode*)malloc(sizeof(ArcNode));     s->adjvex=i;     s->nextarc=NULL;     if(!G.vertices[j].firstarc)       G.vertices[j].firstarc=s;     else{       p=G.vertices[j].firstarc;       while(p->nextarc)         p=p->nextarc;       p->nextarc=s;     }   } }  int visited[MAX];  void DFS(ALGraph G,int v) {//从顶点v开始对图G进行深度优先搜索   ArcNode *p;   printf("%3c",G.vertices[v].data);   visited[v]=1;   for(p=G.vertices[v].firstarc;p;p=p->nextarc)     if(!visited[p->adjvex])       DFS(G,p->adjvex); }  void DFSTraverse(ALGraph G) {//对用邻接表存储的无向图G进行深度优先遍历   int v;   for(v=0;v<G.vexnum;v++)     visited[v]=0;   for(v=0;v<G.vexnum;v++)     if(!visited[v])       DFS(G,v); }  void BFSTraverse(ALGraph G) {//对用邻接表存储的无向图G进行深度优先遍历   int u,v;   CqQueue Q;   ArcNode *p;   for(v=0;v<G.vexnum;v++)     visited[v]=0;   InitQueue(Q);   for(v=0;v<G.vexnum;v++)     if(!visited[v]){       printf("%3c",G.vertices[v].data);       visited[v]=1;       EnQueue(Q,v);       while(!QueueEmpty(Q)){         DeQueue(Q,u);         for(p=G.vertices[u].firstarc;p;p=p->nextarc)           if(!visited[p->adjvex]){             printf("%3c",G.vertices[p->adjvex].data);             visited[p->adjvex]=1;             EnQueue(Q,p->adjvex);           }       }     } }  int main(){   ALGraph G;   printf("建立无向图的邻接表：/n");   CreateAdjList(G);   printf("无向图的深度优先遍历序列如下：/n");   DFSTraverse(G);   printf("/n/n无向图的广度优先遍历序列如下：/n");   BFSTraverse(G);   printf("/n");   return 0; }