《邻接表表示的图的基本操作的实现.docx》由会员分享，可在线阅读，更多相关《邻接表表示的图的基本操作的实现.docx（10页珍藏版）》请在金锄头文库上搜索。
1、邻接表表示的图的基本操作的实现/采用邻接表完成无权无向及有向图的建立、输出、深度遍历、广度遍历操作#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;
2、struct Qnode *next;QNode;/队列类型定义：typedef struct LinkqueueQNode *front,*rear;LinkQueue;/图的数据类型定义typedef struct Tablenode/表结点结构int adjVex;/邻接点域，存放与vi相邻接的顶点vj的序号jstruct Tablenode *next;/指针域，将邻接表的所有表结点链在一起float weight;/对于带权图，表示权值，对于无权图则可省略此数据域TableNode;typedef struct Headnode/头结点结构ElemType vertex;/顶点域ve
3、rtex，存放顶点vi的信息struct Tablenode *firstEdge;/vi的邻接表的头指针HeadNode;typedef struct Mgraphstruct Headnode vectorMAX_VERTEX_NUM; /顶点向量int vexnum; /图中当前顶点数 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;elseretu
4、rn 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 Dele
5、teLinkQueue(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(
6、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
7、*n)int i;for(i=0;(iG.vexnum)&(G.vectori.vertex!=v);i+);*n=i;if(ivexnum);printf(请输入%d个顶点信息：n,G-vexnum);for(i=0;ivexnum;i+) /输入顶点向量scanf(%d,&(G-vectori.vertex);printf(顶点向量如下：n); /输出顶点向量for(i=0;ivexnum;i+)printf(%4d,G-vectori.vertex);printf(n请逐个输入无权图各顶点的邻接点(输入不存在的邻接点则表示结束)：n);for(k=0;kvexnum;k+) /输入无权图
8、的邻接点 printf(请输入顶点%d的邻接点：,G-vectork.vertex);G-vectork.firstEdge=(TableNode *)malloc(sizeof(TableNode);q=G-vectork.firstEdge;fflush(stdin);doscanf(%d,&v);sfjx=LocateVex(*G,v,&i);if(sfjx=OK)p=(TableNode *)malloc(sizeof(TableNode);if(p!=NULL)p-adjVex=i;q-next=p;q=p;while(sfjx=OK);q-next=NULL; /输出无向图的邻接表
9、void PrintGraph(MGraph G)int i;TableNode *p;printf(图信息如下：n);for(i=0;inext;while(p!=NULL)printf(%4d,p-adjVex);p=p-next;printf(n);/查找顶点v的第一个邻接点，v为当前顶点下标int FirstAdjVex(MGraph G,int v)int p=-1;TableNode *q;q=G.vectorv.firstEdge-next;if(q!=NULL)p=q-adjVex;return p;/查找顶点v的下一个邻接点，w为当前邻接点下标int NextAdjVex(M
10、Graph G,int v,int w)int p=-1;TableNode *q;q=G.vectorv.firstEdge-next;while(q!=NULL)&(q-adjVex!=w)q=q-next;if(q!=NULL)q=q-next;if(q!=NULL)p=q-adjVex;return p;/深度优先遍历char visitedMAX_VERTEX_NUM;/访问标志数组void Dfs(MGraph G,int v)int w;visitedv=1;printf(%4d,G.vectorv);for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex
11、(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
