采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作.doc

/* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */#include stdio.h#include string.h#define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;#define INFINITY INT_MAX /*最大值“无穷”*/#define MAX_VERTEX_NUM 20 /*最大顶点个数*/typedef int Boolean;typedef char VertexType20;typedef int VRType;/*以下为队列的操作*/*队列的类型定义*/typedef int QElemType;typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;/*初始化队列*/Status InitQueue(LinkQueue *Q) (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode); if (!(*Q).front) exit(OVERFLOW); (*Q).front-next=NULL; return OK; /*判断队列是否为空*/Status QueueEmpty (LinkQueue Q) if (Q.front=Q.rear) return TRUE; else return FALSE; /*入队列*/Status EnQueue(LinkQueue *Q, QElemType e) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if (!p) exit(OVERFLOW); p-data=e; p-next=NULL; (*Q).rear-next=p; (*Q).rear=p; return OK; /*出队列*/Status DeQueue(LinkQueue *Q, QElemType *e) QueuePtr p; if (*Q).front=(*Q).rear) return ERROR; p=(*Q).front-next; *e=p-data; (*Q).front-next=p-next; if (*Q).rear=p) (*Q).rear=(*Q).front; free(p); return OK; /*以下为图的操作*/*图的类型定义*/typedef struct ArcCell VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/ ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图中当前顶点数和边数*/ MGraph;/*建立无向图的邻接矩阵*/void CreateGraph(MGraph *G) int i,j,k; VertexType v1,v2; printf(nInput MG vexnum,arcnum:); scanf(%d,%d,&(*G).vexnum,&(*G).arcnum); printf(Input %d vexs:,(*G).vexnum); for(i=0;i(*G).vexnum;i+) /*输入顶点向量*/ scanf(%s,(*G).vexsi); printf(vexs listn); for(i=0;ivexnum;i+) /*输出顶点向量*/ puts(G-vexsi); for(i=0;i(*G).vexnum;i+) /*邻接矩阵初始化*/ for(j=0;j(*G).vexnum;j+)(*G).arcsij.adj=0; printf(nInput %d arcs(vi vj):n,(*G).arcnum); for(k=0;k(*G).arcnum;k+) /*输入无权图的边*/ scanf(%s%s,v1,v2); i=LocateVex(*G,v1); j=LocateVex(*G,v2); (*G).arcsij.adj=1; (*G).arcsji=(*G).arcsij; /* 顶点在顶点向量中的定位*/int LocateVex(MGraph G,VertexType v) int i; for(i=0;iG.vexnum;i+) if (strcmp(v,G.vexsi)=0) break; return i;/* 查找第1个邻接点 */int FirstAdjVex(MGraph G,int v) int j,p=-1; for(j=0;jG.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p;/* 查找下一个邻接点 */int NextAdjVex(MGraph G,int v,int w) int j,p=-1; for(j=w+1;jG.vexnum;j+) if (G.arcsvj.adj=1) p=j; break; return p;/*按邻接矩阵方式输出无向图*/void PrintGraph(MGraph G) int i,j; printf(nMGraph:n); for(i=0; iG.vexnum; i+) printf(%10s,G.vexsi); for(j=0; j=0; w=NextAdjVex(G,v,w) if(!visitedw) Dfs(G,w);void DfsTraverse(MGraph G) int v; for (v=0; vG.vexnum; v+) visitedv=FALSE; for(v=0; vG.vexnum; v+) if (!visitedv) Dfs(G,v);/* 广度遍历 */void BfsTraverse(MGraph G) int v,u,w; LinkQueue Q; for(v=0; vG.vexnum; v+) visitedv=FALSE; InitQueue(&Q); for(v=0; v=0; w=NextAdjVex(G,u,w) if (!visitedw) visitedw=TRUE; printf(%s,G.vexsw); EnQueue(&Q,