邻接矩阵表示的图的基本操作的实现.docx

邻接矩阵表示的图的基本操作的实现/采用邻接矩阵完成无权无向及有向图的建立、输出、深度遍历、广度遍历操作#include #include #define OK 1#define ERROR -1typedef int Status;typedef int ElemType; /此例中设元素为单值元素，类型为整型#define MAX_VERTEX_NUM 20 /最大顶点个数typedef int ElemType; /图顶点数据类型typedef int QueueElemType;/队列结点数据类型/链表结点类型定义typedef struct QnodeQueueElemType data;struct Qnode *next;QNode;/队列类型定义：typedef struct LinkqueueQNode *front,*rear;LinkQueue;/图的数据类型定义typedef struct MgraphElemType vectorMAX_VERTEX_NUM; /顶点向量int adjMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵int vexnum; /图中当前顶点数int arcnum; /图中当前边数 MGraph;/队列初始化Status InitLinkQueue(LinkQueue *Q)QNode *p;p=(QNode*)malloc(sizeof(QNode);/开辟头结点空间if(p!=NULL)p-next=NULL;Q-front=Q-rear=p;return OK;elsereturn ERROR;/链式队列的入队操作，在已知队列的队尾插入一个元素e，修改队尾指针rear。Status InsertLinkQueue(LinkQueue *Q,ElemType e)QNode *p;p=(QNode*)malloc(sizeof(QNode);if(p=NULL)return ERROR;/申请新结点空间失败，返回错误标志elsep-data=e;/存入新结点数据p-next=NULL;Q-rear-next=p;/新结点插入到队尾Q-rear=p;/新插入结点成为新的队尾return OK;/链式队列的出队操作，取第一个数据结点的数据后删除该结点Status DeleteLinkQueue(LinkQueue *Q,ElemType *e)QNode *p;if(Q-front=Q-rear)/可改为：if(Q-front-next=NULL)return ERROR;/队空elsep=Q-front-next;/取队首结点*e=p-data;Q-front-next=p-next;/修改队首指针if(p=Q-rear)/条件成立说明只有一个数据结点Q-rear=Q-front;/当队列只有一个数据结点时应防止丢失队尾指针free(p);Q-rear-next=NULL;return OK;/判断队列是否为空Status IsEmptyLinkQueue(LinkQueue *Q)if(Q-front=Q-rear)return OK;elsereturn ERROR;/释放队列void DestroyLinkQueue(LinkQueue *Q)QNode *p,*q;p=Q-front;/指向链表第一个结点，即整个链表的第一个结点while(p!=NULL)q=p-next;/保存链表后半段首地址以防丢失free(p);p=q;/*以下为图的操作*/顶点在顶点向量中的定位，找到返回OK，否则返回ERROR/G为的数据结构，v为待查顶点，n用于返回找到的顶点下标Status LocateVex(MGraph G,ElemType v,int *n)int i;for(i=0;(iG.vexnum)&(G.vectori!=v);i+);*n=i;if(ivexnum),&(G-arcnum);fflush(stdin);printf(请输入%d个顶点信息：n,G-vexnum);for(i=0;ivexnum;i+) /输入顶点向量scanf(%d,&(G-vectori);printf(顶点向量如下：n); /输出顶点向量for(i=0;ivexnum;i+)printf(%4d,G-vectori);printf(n无向图还是有向图，0-无向图 其它-有向图：);scanf(%d,&sfyxt);for(i=0;ivexnum;i+) /邻接矩阵初始化for(j=0;jvexnum;j+)G-adjij=0;printf(n请输入无权图的边(共%d条)n,G-arcnum);printf(格式为：vi vj，vi及vj表示结点内容，注意有向图结点输入的前后次序：n);for(k=0;karcnum;k+) /输入无权图的边 fflush(stdin);printf(No.%2d/%d：,k+1,G-arcnum);scanf(%d%d,&v1,&v2);LocateVex(*G,v1,&i);LocateVex(*G,v2,&j);G-adjij=1;if(sfyxt=0)/无向图则同时产生两条边的信息G-adjji=G-adjij; /输出无向图的邻接矩阵void PrintGraph(MGraph G)int i,j;printf(图信息如下：n);printf(%4s, );for(i=0;iG.vexnum;i+)printf(%4d,G.vectori);printf(n);for(i=0;iG.vexnum;i+)printf(%4d,G.vectori);for(j=0;jG.vexnum;j+)printf(%4d,G.adjij);printf(n); /查找顶点v的第一个邻接点，v为当前顶点下标int FirstAdjVex(MGraph G,int v)int j,p=-1,found=1;for(j=0;(jG.vexnum)&(found=1);j+)if(G.adjvj=1)p=j;found=0;return p;/查找顶点v的下一个邻接点，w为当前邻接点下标int NextAdjVex(MGraph G,int v,int w)int j,p=-1,found=1;for(j=w+1;(j=0;w=NextAdjVex(G,v,w) if(visitedw=0)Dfs(G,w);void DfsTraverse(MGraph G)int v;for(v=0;vG.vexnum;v+)visitedv=0;for(v=0;vG.vexnum;v+)if(visitedv=0)Dfs(G,v);/广度优先遍历void BfsTraverse(MGraph G)int v,u,w;LinkQueue Q;for(v=0;vG.vexnum;v+)visitedv=0;InitLinkQueue(&Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(visitedw=0)visitedw=1;printf(%4d,G.vectorw);InsertLinkQueue(&Q,w);DestroyLinkQueue(&Q);/主函数void main()int xz=1;MGraph G;while(xz!=0)printf(1输入图信息n);printf(2输出图信息n);printf(3图的深度优先遍历n);printf(4图的广度优先遍历n);printf(0退出n请选择：);fflush(stdin);scanf(%d,&xz);switch(xz)case 1:CreateGraph