图的存储结构：邻接多重表
产生条件：
邻接多重表的定义：
邻接多重表的代码定义：
删除：
性能分析：
十字链表与邻接多重表的对比

产生条件：
当用邻接矩阵法存储时：空间复杂度为O(|V|^2),太大

当用邻接表法存储时：一条边会重复存储两次，产生冗余
邻接多重表的定义：


顶点表节点：
1、data：顶点数据域
2、firstedge:边表节点的头指针

边表节点：
1、ivex:该边的第一个端点
2、ilink:与该端点相邻的下一个边表节点的指针
3、jvex:该边的第二个端点
4、jlink:与该端点相邻的下一个边表节点的指针
5、info:权值
6、mark:标记

邻接多重表的代码定义：
#define MaxVertexTypeNum 100
typedef char VertexType;		
typedef int EdgeType;	

typedef struct ArcNode{					//边表节点 
	int ivex,jvex;						//边的俩个节点			
	struct ArcNode *ilink , *jhink;		//维护俩个节点的边表 
	//InfoType info; 					//权值 
	//bool mark;						//标记位 
}ArcNode;								//边表节点的类型 

typedef struct VNode{					//顶点表节点 
	VertexType data;					//顶点的数据 
	ArcNode *firstedge;					//边表的头指针 
}VNode;									// 邻接表类型 

typedef struct{							//十字链表 
	VNode adjmulist[MaxVertexTypeNum];	//所有结点的数据 
	int vexnum,arcnum;					//节点数和边数 
}ALGraph;								//十字链表的类型 

删除：
删除边AB：




删除节点E：


性能分析：
空间复杂度：O(|v| + |E|)
十字链表与邻接多重表的对比
十字链表： 用于有向图，解决了无法快速找到一个顶点入边的问题

邻接多重表： 用于无向图，解决了重复存储同一条边2次的问题

邻接多重表
上一节总结了有向图的另外一种链式存储结构—十字链表，该节继续总结无向图的另一种链式存储结构。
基本概念
邻接表虽然已经能够很好地表示无向图了，但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点，这给针对图的边的操作（标记或删除）带来不便利。邻接多重表因此而演变过来的。
邻接多重表中，无向图中的每一个顶点分配一个顶点结点，所有顶点结点构成一个顶点数组adjmultiList[num]。另外每条边也分配一个边结点。
顶点结构如下所示：

其中data用来记录顶点的信息，firstEdge用来表示依附于该顶点的第一条边。
顶点数组如下所示：
边结点结构如下所示：
其中mark表示标志位，用于标记该边是否已经被访问过；iVex和jVex表示该边的两个顶点在顶点数组adjmultiList[num]中的位置；iLink和jLink分别表示指向依附于顶点iVex和jVex下一条边的指针。
从上面的顶点和边的结构来看，邻接多重表和邻接表的主要区别在于：邻接多重表中的边结点同时被链入对应边顶点的链表内（2条）；邻接表中的边用两个表结点表示。另外，邻接多重表中的边结点就表示一条边，比较容易理解。
举个例子。某无向图如下图所示：

当采用邻接表表示该无向图时，其邻接表入下图所示：
如上图所示，图中黄色标记的结点表示A-D之间的边，在邻接表中一条边需要两个结点表示。因此如果对于边的操作（标记或者删除）则需要访问两条链表。
当采用邻接多重表表示该无向图时，其邻接多重表入下图所示：

如上图所示，结点A-D 之间的边，在邻接多重表中只需要一个边结点既可以表示。另外，在该结构中，每个边结点被链入了两个不同的链表。其中A-D之间的边被链入了红色和绿色标记的链表中。如果需要访问一条边，则可以从该边的两个顶点结点中的任何一个出发，遍历依附于该顶点的边构成的链表即可。如果需要删除一条边，则只需要删除一个边结点，但是需要修改这条边依附的两个顶点所对应的链表。另外，需要注意的是，在无向图中，边结点中的iVex和jVex链域与该边所依附的顶点无关，即iVex=0，jVex=3和iVex=3，jVex=0这都表示同一条边A-D，因此这给链表的指针修改带来一定的麻烦。
基本操作
1、建立无向图的邻接多重表
输入ABCDE五个顶点V={A,B,C,D,E}，然后输入边E={(A,B),(B,C),(B,E),(C,D),(C,E),(D,A)}，建立如下无向图：

代码如下：
Status createAMLGraph(AMLGraph &G, int vexNum){
	G.vexNum = vexNum;
	G.edgeNum = 0;
	for(int i = 0; i< G.vexNum; i++){
		cin>>G.adjmultiList[i].data;
		G.adjmultiList[i].firstEdge = NULL;
	}

	cout<<"Try to input arcs info"<<endl;
	while(1){
		char SWITCH;
		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
		
		cin>>SWITCH;
		if(SWITCH == 'y'){
			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;

			vertexNode node1, node2;
			cin>>node1.data>>node2.data;
			insertEdge(G, node1, node2);
			G.edgeNum++;
		}
		else
			break;
	}
	return 1;
}
2、打印无向图的邻接多重表

代码如下：
Status printAMLGraph(AMLGraph &G){
	for(int i = 0; i<G.vexNum; i++){
		cout<<i<<" "<<G.adjmultiList[i].data;
		edgeNode *edge = G.adjmultiList[i].firstEdge;

		while(edge){
			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
			if(edge->iVex == i){
				edge = edge->iLink;
			}
			else{
				edge = edge->jLink;
			}
		}
		cout<<"-->NULL"<<endl;
	}
	return 1;
}
3、向无向图中添加顶点
向无向图中添加结点F。

代码如下：
Status insertNode(AMLGraph &G, vertexNode node){
	G.adjmultiList[G.vexNum].data = node.data;
	G.adjmultiList[G.vexNum].firstEdge = NULL;
	G.vexNum++;
	return 1;
}
4、向无向图中添加边
向无向图中添加边A-C。

代码如下：
void insertEdgeAction(AMLGraph &G, int index1, int index2){
	edgeNode *p, *q;
	edgeNode *edge = new edgeNode[1];
	
	edge->iVex = index1;
	edge->jVex = index2;

	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
	if(!p){
		G.adjmultiList[index1].firstEdge = edge;
		edge->iLink = NULL;
	}
	else{
		G.adjmultiList[index1].firstEdge = edge;

		edge->iLink = p;
	}

	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
	if(!q){
		G.adjmultiList[index2].firstEdge = edge;
		edge->jLink = NULL;
	}
	else{
		G.adjmultiList[index2].firstEdge = edge;
		edge->jLink = q;
	}
}

Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
	int index2 = locateNode(G, node2);
	if(index1<0 || index2<0) exit(-1);
	
	insertEdgeAction(G, index1, index2);

	return 1;
}
5、删除无向图中的边
删除无线图中的边B-C。

代码如下：
Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
	edgeNode *preEdge = curEdge;
	int count = 0;

	if(!curEdge) return 1;
	else{
		while(curEdge){
			count++;
			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
				break;
			}
			preEdge = curEdge;
			if(curEdge->iVex ==index1)
				curEdge = curEdge->iLink;
			else
				curEdge = curEdge->jLink;
		}
	}

	if(!curEdge)
		return 1;
	else if(count<=1){
		if(preEdge->iVex == index1)
			G.adjmultiList[index1].firstEdge = preEdge->iLink;
		else 
			G.adjmultiList[index1].firstEdge = preEdge->jLink;
	}
	else{
		if(preEdge->iVex == index1){ 
			if (curEdge->iVex == index1)
				preEdge->iLink = curEdge->iLink;
			else
				preEdge->iLink = curEdge->jLink;
		}
		else{
			if (curEdge->iVex == index1)
				preEdge->jLink = curEdge->iLink;
			else
				preEdge->jLink = curEdge->jLink;
		}
	}
	return 1;
}

Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
	int index1 = locateNode(G, node1);
	int index2 = locateNode(G, node2);

	deleteEdgeAction(G, index1, index2);
	deleteEdgeAction(G, index2, index1);

	return 1;
}
6、删除无向图中的顶点
删除结点C。

代码如下：
Status deleteNode(AMLGraph &G, vertexNode node){
	//删除结点时，结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
	int index = locateNode(G, node);

	for(int i = 0; i<G.vexNum; i++){
		if(i == index) continue;
		else{
			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
		}
	}
	G.adjmultiList[index].firstEdge = NULL;
	G.adjmultiList[index].data = '0';
	return 1;
}
7、全部代码：
// 邻接多重表.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

#define MAX_VERTEX_NUM 20

typedef int infoType;
typedef char vertexType;
typedef int Status;

typedef struct edgeNode{
	int iVex, jVex;
	struct edgeNode *iLink, *jLink;
	infoType *info;
}edgeNode;

typedef struct vertexNode{
	vertexType data;
	edgeNode *firstEdge;
}vertexNode;

typedef struct{
	vertexNode adjmultiList[MAX_VERTEX_NUM];
	int vexNum, edgeNum;
}AMLGraph;

int locateNode(AMLGraph &G, vertexNode node){
	for(int i=0; i<G.vexNum;i++){
		if(node.data == G.adjmultiList[i].data)
			return i;
	}
	return -1;
}

Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2);

Status createAMLGraph(AMLGraph &G, int vexNum){
	G.vexNum = vexNum;
	G.edgeNum = 0;
	for(int i = 0; i< G.vexNum; i++){
		cin>>G.adjmultiList[i].data;
		G.adjmultiList[i].firstEdge = NULL;
	}

	cout<<"Try to input arcs info"<<endl;
	while(1){
		char SWITCH;
		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
		
		cin>>SWITCH;
		if(SWITCH == 'y'){
			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;

			vertexNode node1, node2;
			cin>>node1.data>>node2.data;
			insertEdge(G, node1, node2);
			G.edgeNum++;
		}
		else
			break;
	}
	return 1;
}

void insertEdgeAction(AMLGraph &G, int index1, int index2){
	edgeNode *p, *q;
	edgeNode *edge = new edgeNode[1];
	
	edge->iVex = index1;
	edge->jVex = index2;

	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
	if(!p){
		G.adjmultiList[index1].firstEdge = edge;
		edge->iLink = NULL;
	}
	else{
		G.adjmultiList[index1].firstEdge = edge;

		edge->iLink = p;
	}

	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
	if(!q){
		G.adjmultiList[index2].firstEdge = edge;
		edge->jLink = NULL;
	}
	else{
		G.adjmultiList[index2].firstEdge = edge;
		edge->jLink = q;
	}
}

Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
	int index2 = locateNode(G, node2);
	if(index1<0 || index2<0) exit(-1);
	
	insertEdgeAction(G, index1, index2);

	return 1;
}

Status printAMLGraph(AMLGraph &G){
	for(int i = 0; i<G.vexNum; i++){
		cout<<i<<" "<<G.adjmultiList[i].data;
		edgeNode *edge = G.adjmultiList[i].firstEdge;

		while(edge){
			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
			if(edge->iVex == i){
				edge = edge->iLink;
			}
			else{
				edge = edge->jLink;
			}
		}
		cout<<"-->NULL"<<endl;
	}
	return 1;
}

Status insertNode(AMLGraph &G, vertexNode node){
	G.adjmultiList[G.vexNum].data = node.data;
	G.adjmultiList[G.vexNum].firstEdge = NULL;
	G.vexNum++;
	return 1;
}

Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
	edgeNode *preEdge = curEdge;
	int count = 0;

	if(!curEdge) return 1;
	else{
		while(curEdge){
			count++;
			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
				break;
			}
			preEdge = curEdge;
			if(curEdge->iVex ==index1)
				curEdge = curEdge->iLink;
			else
				curEdge = curEdge->jLink;
		}
	}

	if(!curEdge)
		return 1;
	else if(count<=1){
		if(preEdge->iVex == index1)
			G.adjmultiList[index1].firstEdge = preEdge->iLink;
		else 
			G.adjmultiList[index1].firstEdge = preEdge->jLink;
	}
	else{
		if(preEdge->iVex == index1){ 
			if (curEdge->iVex == index1)
				preEdge->iLink = curEdge->iLink;
			else
				preEdge->iLink = curEdge->jLink;
		}
		else{
			if (curEdge->iVex == index1)
				preEdge->jLink = curEdge->iLink;
			else
				preEdge->jLink = curEdge->jLink;
		}
	}
	return 1;
}

Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
	int index1 = locateNode(G, node1);
	int index2 = locateNode(G, node2);

	deleteEdgeAction(G, index1, index2);
	deleteEdgeAction(G, index2, index1);

	return 1;
}

Status deleteNode(AMLGraph &G, vertexNode node){
	//删除结点时，结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
	int index = locateNode(G, node);

	for(int i = 0; i<G.vexNum; i++){
		if(i == index) continue;
		else{
			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
		}
	}
	G.adjmultiList[index].firstEdge = NULL;
	G.adjmultiList[index].data = '0';
	return 1;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int vexNum = 5;
	AMLGraph G;
	cout<<"Try to create a adjacence multilist of a graph ..."<<endl;
	createAMLGraph(G, vexNum);
	printAMLGraph(G);

	cout<<"Try to insert a node into the graph..."<<endl;
	vertexNode node;
	cout<<"   please input the data of the node to insert:"<<endl;
	cin>>node.data;
	insertNode(G, node);
	printAMLGraph(G);

	cout<<"Try to insert a edge into the graph..."<<endl;
	vertexNode node1, node2;
	cout<<"   please choose two node:"<<endl;
	cin>>node1.data>>node2.data;
	insertEdge(G, node1, node2);
	printAMLGraph(G);

	cout<<"Try to delete the edge between two nodes..."<<endl;
	vertexNode node3, node4;
	cout<<"   please choose a edge with specifing two nodes:"<<endl;
	cin>>node3.data>>node4.data;
	deleteEdge(G, node3, node4);
	printAMLGraph(G);

	cout<<"Try to delete a node of the graph..."<<endl;
	vertexNode node5;
	cout<<"   please choose a node:"<<endl;
	cin>>node5.data;
	deleteNode(G, node5);
	printAMLGraph(G);

	system("pause");
	return 0;
}

数据结构——图——存储结构——邻接多重表
如果我们在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着，需要找到这条边的两个边表结点进行操作，这其实还是比较麻烦的。比如图7-4-11，若要删除左图的（v0,v2）这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较烦琐的。



因此，我们也仿照十字链表的方式，对边表结点的结构进行一些改造，也许就可以避免刚才提到的问题。
重新定义的边表结点结构如表7-4-3所示。



其中 ivex 和jvex是与某条边依附的两个顶点在顶点表中下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。
我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如图7-4-12所示，左图告诉我们它有4个顶点和5条边，显然，我们就应该先将4个顶点和5条边的边表结点画出来。由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的，不过为了绘图方便，都将ivex值设置得与一旁的顶点下标相同。



我们开始连线，如图7-4-13。首先连线的①②③④就是将顶点的 firstedge指向一条边，顶点下标要与ivex的值相同，这很好理解。接着，由于顶点v0的（v0,v1）边的邻边有(v0,v3）和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink 指向的结点的 jvex一定要和它本身的 ivex的值相同。同样的道理，连线⑦就是指(v1,v0）这条边，它是相当于顶点v1指向(v1，v,2）边后的下一条。vz有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点vs在连线④之后的下一条边。左图一共有5条边，所以右图有10条连线，完全符合预期。



到这里，大家应该可以明白，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的 (v0,v2）这条边，只需要将右图的⑥⑨的链接指向改为 ^ 即可。由于各种基本操作的实现也和邻接表是相似的

数据结构之图的存储结构：邻接多重表
#include<iostream>
using namespace std;
#define MAX 25

typedef int Status;
typedef char eleVex;

typedef struct ArcNode//边结构
{
	int ivex, jvex;
	int weight;
	struct ArcNode *ilink, *jlink;
}ArcNode;

typedef struct VNode//表头结构
{
	eleVex data;
	ArcNode *first;
}VNode;

typedef struct AMT//邻接多重链表结构
{
	VNode table[MAX];
	int vexnum, arcnum;
}AMT;