图的邻接多重表 是 无向图的 另一种表示法。其与 邻接表 的差别 仅仅 在于 ，，邻接表 用 两个 顶点 来表示 一条边，而 邻接多重表 用一个 顶点来表示一条边。这样使得 邻接多重表 在 某些操作 要 来的 方便。例如 将 搜索过的边 做记号 或者 删除 一条边。
下面是邻接多重表的结构：
下面的 6条边 用 6个弧 节点表示，用12个指针指向，每个弧节点被 指向2次。这样使得我们 在 释放内存的时候 需要格外小心。
下面上代码：
更改了 查找 下一个 邻接点 nextAdj 的错误代码，少加了一句 ，网盘 代码 没有 修改。请注意。
char iName = g.adjMuList[next->iIndex].vexName;char jName = g.adjMuList[next->jIndex].vexName;if (iName == vex2 || jName == vex2){next = next->iIndex == location ? next->iNext : next->jNext;break;}next = next->iIndex == location ? next->iNext : next->jNext;
源码工程文件网盘地址：点击打开链接
// AMLGraph.cpp : 定义控制台应用程序的入口点。//无向图的邻接多重表#include "stdafx.h"#include <cstdlib>#define MAX_VEX_NUM 20enum E_State{E_State_Error = 0,E_State_Ok = 1,};enum E_VisitIf{unvisited = 0,visited = 1,};struct ArcNode{E_VisitIf mark;int iIndex,jIndex;//顶点i,j在图中的位置ArcNode * iNext;//与i顶点点相关的下一个弧ArcNode * jNext;//与j顶点点相关的下一个弧};struct VNode{char vexName;ArcNode * head;//头指针};struct AMLGraph{VNode adjMuList[MAX_VEX_NUM];//顶点数组int vexNum,arcNum;};//获取弧 的 头节点ArcNode * getHeadNode(){ArcNode * pNode = (ArcNode *)malloc(sizeof(ArcNode));if (pNode){pNode->iIndex = pNode->jIndex = -1;pNode->iNext = pNode->jNext = NULL;pNode->mark = unvisited;}return pNode;}ArcNode * getArcNode(int iIndex,int jIndex){ArcNode * pNode = getHeadNode();if (pNode){pNode->iIndex = iIndex;pNode->jIndex = jIndex;}return pNode;}int vexLocation(AMLGraph g,char vex){for (int i = 0; i < g.vexNum; i++){if (g.adjMuList[i].vexName == vex){return i;}}return -1;}void createGrahp(AMLGraph * g){printf("输入图的顶点数 和 边（弧）数\n");scanf("%d%d%*c",&g->vexNum,&g->arcNum);//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < g->vexNum; i++){char name;scanf("%c",&name);g->adjMuList[i].vexName = name;g->adjMuList[i].head = getHeadNode();//建立 头节点，并让头指针指向头节点}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < g->arcNum; i++){char vex1,vex2;scanf("%c%c%*c",&vex1,&vex2);int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * pNode = getArcNode(location1,location2);pNode->iNext = g->adjMuList[location1].head->iNext;g->adjMuList[location1].head->iNext = pNode;pNode->jNext = g->adjMuList[location2].head->iNext;g->adjMuList[location2].head->iNext = pNode;} }void destoryGraph(AMLGraph * g){for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){ArcNode * freeNode = next;next = next->iIndex == i ? next->iNext : next->jNext;if (freeNode->iIndex == i){////只释放 iIndex 等于 i的节点,要不会多次释放free(freeNode);}}free(g->adjMuList[i].head);g->adjMuList[i].head = NULL;g->adjMuList[i].vexName = ' ';g->vexNum = g->arcNum = 0;}}//顶点vex1 和顶点vex2 是否相邻bool graphIsAdj(AMLGraph g,char vex1,char vex2){int location = vexLocation(g,vex1);ArcNode * next = g.adjMuList[location].head->iNext;while (next != NULL){if (g.adjMuList[next->iIndex].vexName == vex2 || g.adjMuList[next->jIndex].vexName == vex2){return true;}next = next->iIndex == location ? next->iNext : next->jNext;}return false;}int graphDegree(AMLGraph g,char vex){int degree = 0;int location = vexLocation(g,vex);ArcNode * next = g.adjMuList[location].head->iNext;//计算所有出度while (next != NULL){degree++;next = next->iIndex == location ? next->iNext : next->jNext;}return degree;}char firstAdj(AMLGraph g,char vex){int location = vexLocation(g,vex);ArcNode * next = g.adjMuList[location].head->iNext;if (next != NULL){int index = next->iIndex == location ? next->jIndex : next->iIndex;return g.adjMuList[index].vexName;}return ' ';}char nextAdj(AMLGraph g,char vex1,char vex2){int location = vexLocation(g,vex1);ArcNode * next = g.adjMuList[location].head->iNext;while (next != NULL){//查找到 vex2char iName = g.adjMuList[next->iIndex].vexName;char jName = g.adjMuList[next->jIndex].vexName;if (iName == vex2 || jName == vex2){next = next->iIndex == location ? next->iNext : next->jNext;break;}next = next->iIndex == location ? next->iNext : next->jNext;}if (next != NULL){int index = next->iIndex == location ? next->jIndex : next->iIndex;return g.adjMuList[index].vexName;}return ' ';}//插入边（弧）void insertArc(AMLGraph * g,char vex1,char vex2){int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * node = getArcNode(location1,location2);node->iNext = g->adjMuList[location1].head->iNext;g->adjMuList[location1].head->iNext = node;node->jNext = g->adjMuList[location2].head->iNext;g->adjMuList[location2].head->iNext = node;g->arcNum ++;}//删除边（弧）void deleteArc(AMLGraph * g,char vex1,char vex2){g->arcNum–;int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * next = g->adjMuList[location1].head->iNext;ArcNode * pre = g->adjMuList[location1].head;while (next != NULL){if (next->iIndex == location2){if (pre == g->adjMuList[location1].head || pre->iIndex == location1){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->jNext;}else{pre->jNext = next->jNext;}break;}else if(next->jIndex == location2){if (pre == g->adjMuList[location1].head || pre->iIndex == location1){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->iNext;}else{pre->jNext = next->iNext;}break;}pre = next;next = next->iIndex == location1 ? next->iNext : next->jNext;}next = g->adjMuList[location2].head->iNext;pre = g->adjMuList[location2].head;while (next != NULL){if (next->iIndex == location1){if (pre == g->adjMuList[location2].head || pre->iIndex == location2){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->jNext;}else{pre->jNext = next->jNext;}free(next);break;}else if(next->jIndex == location1){if (pre == g->adjMuList[location2].head || pre->iIndex == location2){//删除的是第一个节点.或者 前驱的index = location1pre->iNext = next->iNext;}else{pre->jNext = next->iNext;}free(next);break;}pre = next;next = next->iIndex == location2 ? next->iNext : next->jNext;}}//插入顶点void insertVex(AMLGraph * g, char vex){if (g->vexNum < MAX_VEX_NUM){g->adjMuList[g->vexNum].vexName = vex;g->adjMuList[g->vexNum].head = getHeadNode();g->vexNum++;}}//删除顶点void deleteVex(AMLGraph * g,char vex){int location = vexLocation(*g,vex);//删除顶点 同样需要 遍历整个 图 查找 与 vex 相关的弧节点for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){if (next->iIndex == location || next->jIndex == location){ArcNode * delNode = next;next = next->iIndex == location ? next->iNext : next->jNext;char delData1 = g->adjMuList[delNode->iIndex].vexName;char delData2 = g->adjMuList[delNode->jIndex].vexName;deleteArc(g,delData1,delData2);}else{next = next->iIndex == location ? next->iNext : next->jNext;}}}//更改因删除顶点 而导致的元素位置变化..for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->adjMuList[i].head->iNext;while (next != NULL){if (next->iIndex == i){if(next->iIndex > location){next->iIndex –;}if(next->jIndex > location){next->jIndex –;}}next = next->iIndex == location ? next->iNext : next->jNext;}}free(g->adjMuList[location].head);//释放头节点//vex下面的 顶点上移for (int i = location + 1; i < g->vexNum; i++){g->adjMuList[i-1] = g->adjMuList[i];}g->vexNum –;}void printGrahp(AMLGraph g){for (int i = 0; i < g.vexNum; i++){printf("%c的 邻接点有：",g.adjMuList[i].vexName);ArcNode * next = g.adjMuList[i].head->iNext;//删除所有弧尾while (next != NULL){int index = next->iIndex == i ? next->jIndex : next->iIndex;printf("%c",g.adjMuList[index].vexName);next = next->iIndex == i ? next->iNext : next->jNext;}printf("\n");}}//邻接多重表int _tmain(int argc, _TCHAR* argv[]){AMLGraph g;createGrahp(&g);printGrahp(g);printf("图的顶点数：%d,边（弧）树为：%d\n",g.vexNum,g.arcNum);char * isAdj = graphIsAdj(g,'b','d')? "相邻" : "不相邻";int degree = graphDegree(g,'d');char first = firstAdj(g,'c');char next = nextAdj(g,'d','c');printf("c的第一个邻接点是%c,d的c邻接点的下一个邻接点是：%c\n",first,next);printf("b 和 d %s,d的度为：%d\n",isAdj,degree);insertVex(&g,'f');printf("插入f顶点之后图结构如下：\n");printGrahp(g);insertArc(&g,'e','f');printf("插入(e,f) 之后图结构如下：\n");printGrahp(g);deleteArc(&g,'d','c');printf("删除(d,c)之后图结构如下：\n");printGrahp(g);deleteVex(&g,'c');printf("删除顶点c之后图结构如下：\n");printGrahp(g);printf("图的顶点数：%d,边（弧）数为：%d\n",g.vexNum,g.arcNum);destoryGraph(&g);return 0;}
运行截图：
当你困难失望的时候，最重要的是事瞧得起你自己；
