邻接多重表存储无向图以及有关操作

数据结构是编程里面最重要的一门基础课之一，所以学多少遍都不可以嫌多，算法的知识当然是融在其中，多练习，多思考，基础打好了，其他的东西学起来也就so easy了。

邻接多重表，是对用邻接表存储无向图的一种压缩存储，当然也是链式存储，邻接多重表的相关概念，可以百度、谷歌、或者看有关书籍。大部分书都没有详细介绍这个结构的应用(至少我目前还没看到有书上有写)，只是说 这个结构在对无向图的边进行操作的时候会比较方便，确实有一点吧，在插入和删除边的时候，虽然不用想邻接表那样去找两条，但是也是需要进行一些判判断。下面是代码，邻接多重表存储的无向图的一些相关操作：

文件"graph.h"

#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;

bool visited[100]; //顶点是否被访问标志

//邻接多重表的存储
//边结点
struct EBox
{
	int mark;//标志域，指示该边是否被访问过(0:没有 1:有)
	int ivex,jvex;//该边关联的两个顶点的位置
	EBox *ilink,*jlink;//分别指向关联这两个顶点的下一条边
};

//顶点结点
struct VexBox
{
	string data;  //顶点名称
	EBox *firstedge;//指向第一条关联该结点的边
};

class AMLGraph
{
private:
	VexBox *adjmulist; //顶点数组指针
	int vexnum; //定点数目
	int arcnum; //边数目
	int maxnum; //顶点数最大值
public:
	AMLGraph(int num=20)
	{
		adjmulist=new VexBox[num];
		maxnum=num;
	}
	
	~AMLGraph()
	{
		delete[]adjmulist;
	}

	//定位顶点在顶点数组中的位置
	int Locate_Vex(string v)
	{
		for(int i=0;i<vexnum;i++)
			if(adjmulist[i].data == v)
				return i;
		return -1;
	}

	void CreateUDG_AML()
	{
		//邻接多重表，存储无向图
		string v1,v2;
		int i,j,k;
		cout<<"输入定点数目和弧的数目：";
		cin>>vexnum>>arcnum;

		while(vexnum>maxnum)
		{
			cout<<"顶点数目太多，请重新输入顶点数和边数：";
			cin>>vexnum>>arcnum;
		}

		cout<<"输入每个顶点的名称：";
		for(i=0;i<vexnum;i++)
		{
			cin>>adjmulist[i].data;
			adjmulist[i].firstedge=NULL;
		}

		for(k=0;k<arcnum;k++)
		{
			cout<<"输入边的两个顶点：";
			cin>>v1>>v2;
			while(Search_Arc(v1,v2))
			{
				cout<<"该边已存在，本图不支持存在平行边"<<endl;
				cout<<"重新输入边的两个顶点：";
				cin>>v1>>v2;
			}

			i=Locate_Vex(v1);
			j=Locate_Vex(v2);

			while(i == -1 || j == -1)
			{
				cout<<"两个顶点中有不符合要求的，请重新输入：";
				cin>>v1>>v2;
				i=Locate_Vex(v1);
				j=Locate_Vex(v2);
			}

			//采用头插入方式，代码较好写，无向图顺序并不重要，所以没关系
			EBox *p=new EBox;
			p->ivex=i;
			p->jvex=j;
			p->ilink=adjmulist[i].firstedge;
			p->jlink=adjmulist[j].firstedge;
			adjmulist[i].firstedge=adjmulist[j].firstedge=p;
		}

		cout<<"无向图构造完成"<<endl;
	}

	bool Search_Arc(string v1,string v2)
	{
		//搜索对应的边是否存在
		int i,j;
		EBox *p;
		i=Locate_Vex(v1);
		j=Locate_Vex(v2);

		if(i == -1 || j == -1)
		{
			cout<<"顶点错误，改边不存在"<<endl;
			return false;
		}

		p=adjmulist[i].firstedge;
		while(p)
		{
			if(p->ivex == i && p->jvex == j)
				return true;
			else if(p->jvex == i && p->ivex == j)
				return true;
			else if(p->ivex == i)
				p=p->ilink;
			else if(p->jvex == i)
				p=p->jlink;
		}
		return false;
	}

	void Find_Neighbour(string v)
	{
		//输出顶点v的邻接顶点
		int i=Locate_Vex(v);
		if(i == -1)
		{
			cout<<"该顶点不存在图中"<<endl;
			return ;
		}
		
		EBox *p=adjmulist[i].firstedge;
		if(p)
		{
			cout<<"顶点 "<<v<<" 的邻接顶点为：";
			while(p)
			{
				if(p->ivex == i)
				{
					cout<<adjmulist[p->jvex].data<<"  ";
					p=p->ilink;
				}
				else
				{
					//p->jvex == i
					cout<<adjmulist[p->ivex].data<<"  ";
					p=p->jlink;
				}
			}
		}
		else
			cout<<"该顶点无相邻顶点"<<endl;
	}

	bool Insert_Arc(string v1,string v2)
	{
		//插入新边，不插入平行边
		if(Search_Arc(v1,v2))
		{
			cout<<"该边已存在图中，不重复插入"<<endl;
			return false;
		}

		int i,j;
		i=Locate_Vex(v1);
		j=Locate_Vex(v2);

		if(i == -1 || j == -1)
		{
			cout<<"两个顶点中，又不符合要求的，插入失败"<<endl;
			return false;
		}
		
		EBox *p=new EBox;
		p->ivex=i;
		p->jvex=j;
		p->ilink=adjmulist[i].firstedge;
		p->jlink=adjmulist[j].firstedge;
		adjmulist[i].firstedge=adjmulist[j].firstedge=p;

		//记得边数要加1
		arcnum++;
		return true;
	}

	bool Delete_Arc(string v1,string v2)
	{
		//删除顶点v1,v2之间的边
		if(Search_Arc(v1,v2))
		{
			int i,j;
			i=Locate_Vex(v1);
			j=Locate_Vex(v2);
	
			if(i == -1 || j == -1)
			{
				cout<<"输入的顶点中，有不在图中的，所以删除失败"<<endl;
				return false;
			}

			//四个指针，pre是指向待删除边的前一条边，rear是指向待删除的边
			//i，j是代表两个端点
			EBox *ipre,*irear,*jpre,*jrear;

			//初始化四个指针
			ipre=irear=adjmulist[i].firstedge;
			jpre=jrear=adjmulist[j].firstedge;

			//下面先判断第一条边是不是就是要删除的边
			if(ipre->ivex == i && ipre->jvex == j)
			{
				adjmulist[i].firstedge=ipre->ilink;
				adjmulist[j].firstedge=ipre->jlink;
				delete ipre;
				arcnum--;
				return true;
			}
			else if(ipre->jvex == i && ipre->ivex == j)
			{
				adjmulist[i].firstedge=ipre->jlink;
				adjmulist[j].firstedge=ipre->ilink;
				delete ipre;
				arcnum--;
				return true;
			}
			else
			{
				//待删除的边不是第一条
				//先让irear指向待删除的那条边
				while(irear)
				{
					if(irear->ivex == i && irear->jvex != j)
					{
						ipre=irear;
						irear=irear->ilink;
					}
					else if(irear->jvex == i && irear->ivex != j)
					{
						ipre=irear;
						irear=irear->jlink;
					}
					else if(irear->ivex == i && irear->jvex == j)
						break;
					else if(irear->jvex == i && irear->ivex == j)
						break;
				}

				if(!irear)
					return false;

				//下面让jrear指向待删除边
				if(irear->ivex == i)
				{
					//所以irear->jvex == j
					while(jrear)
					{
						if(jrear->ivex == i && jrear->jvex == j)
							break;
						else if(jrear->jvex == j)
						{
							jpre=jrear;
							jrear=jrear->jlink;
						}
						else if(jrear->ivex == j)
						{
							jpre=jrear;
							jrear=jrear->ilink;
						}
					}
					if(!jrear)
						return false;
				}
				else
				{
					//irear->ivex == j
					while(jrear)
					{
						if(jrear->ivex == j && jrear->jvex == i)
							break;
						else if(jrear->ivex == j)
						{
							jpre=jrear;
							jrear=jrear->ilink;
						}
						else if(jrear->jvex == j)
						{
							jpre=jrear;
							jrear=jrear->jlink;
						}
					}
					if(!jrear)
						return false;
				}

				//下面是开始删除，待删除边不是第一条边的情况
				if(irear->ivex == i && irear->jvex == j)
				{
					//删除时要判断每个顶点关联的前一条边的情况
					if(ipre->ivex == i)
						ipre->ilink=irear->ilink;
					else
						ipre->jlink=irear->ilink;

					if(jpre->ivex == j)
						jpre->ilink=jrear->jlink;
					else
						jpre->jlink=jrear->jlink;

					delete irear;
					arcnum--;
					return true;
				}
				else
				{
					//irear->jvex == i && irear->ivex == j
					//删除时要判断每个顶点关联的前一条边的情况
					if(ipre->ivex == i)
						ipre->ilink=irear->jlink;
					else
						ipre->jlink=irear->jlink;

					if(jpre->ivex == j)
						jpre->ilink=jrear->ilink;
					else
						jpre->jlink=jrear->ilink;

					delete irear;
					arcnum--;
					return true;
				}
			}
		}
		else
			cout<<"该边不存在"<<endl;
		return false;
	}

	//深度优先遍历
	void DFS_Traverse()
	{
		for(int i=0;i<vexnum;i++)
			visited[i]=false;
		for(i=0;i<vexnum;i++)
			if(!visited[i])
				DFS(i);
			cout<<endl;
	}

	void DFS(int v)
	{
		visited[v]=true;
		cout<<adjmulist[v].data<<"  ";
		EBox *p=adjmulist[v].firstedge;
		while(p)
		{
			if(p->ivex == v)
			{
				if(!visited[p->jvex])
					DFS(p->jvex);
				p=p->ilink;
			}
			else
			{
				if(!visited[p->ivex])
					DFS(p->ivex);
				p=p->jlink;
			}
		}
	}

	//广度优先遍历
	void BFS_Traverse()
	{
		for(int i=0;i<vexnum;i++)
			visited[i]=false;
		for(i=0;i<vexnum;i++)
			if(!visited[i])
				BFS(i);
		cout<<endl;
	}

	void BFS(int v)
	{
		visited[v]=true;
		cout<<adjmulist[v].data<<"  ";
		EBox *p;
		int pos;
		queue<int> qu;
		qu.push(v);
		while(!qu.empty())
		{
			pos=qu.front();
			qu.pop();
			p=adjmulist[pos].firstedge;
			while(p)
			{
				if(p->ivex == pos)
				{
					if(!visited[p->jvex])
					{
						visited[p->jvex]=true;
						cout<<adjmulist[p->jvex].data<<"  ";
						qu.push(p->jvex);
					}
					p=p->ilink;
				}
				else
				{
					if(!visited[p->ivex])
					{
						visited[p->ivex]=true;
						cout<<adjmulist[p->ivex].data<<"  ";
						qu.push(p->ivex);
					}
					p=p->jlink;
				}
			}
		}
	}

	void Mark_Unvisited()
	{
		//置边的访问标志为未访问
		int i;
		EBox *p;
		for(i=0;i<vexnum;i++)
		{
			p=adjmulist[i].firstedge;
			while(p)
			{
				p->mark=0;
				if(p->ivex == i)
					p=p->ilink;
				else
					p=p->jlink;
			}
		}
	}

	void Display()
	{
		//输出邻接多重表
		int i;
		EBox *p;
		Mark_Unvisited();
		cout<<"顶点为：";
		for(i=0;i<vexnum;i++)
			cout<<adjmulist[i].data<<"  ";
		cout<<endl;

		cout<<"总共有"<<arcnum<<"条边"<<endl;
		for(i=0;i<vexnum;i++)
		{
			p=adjmulist[i].firstedge;
			while(p)
			{
				if(p->ivex == i)
				{
					if(!p->mark)
					{
						cout<<adjmulist[i].data<<"--"<<adjmulist[p->jvex].data<<endl;
						p->mark=1;
					}
					p=p->ilink;
				}
				else
				{
					if(!p->mark)
					{
						cout<<adjmulist[p->jvex].data<<"--"<<adjmulist[p->ivex].data<<endl;
						p->mark=1;
					}
					p=p->jlink;
				}
			}
		}
	}
};

文件"main.cpp"

#include "graph.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
	AMLGraph G;
	G.CreateUDG_AML();

	string v,v1,v2;
	cout<<"输入顶点名称，将输出其相邻顶点：";
	cin>>v;
	G.Find_Neighbour(v);
	cout<<endl;

	cout<<"邻接多重表结构："<<endl;
	G.Display();

	cout<<"深度优先遍历序列：";
	G.DFS_Traverse();

	cout<<"广度优先遍历序列：";
	G.BFS_Traverse();

	cout<<"输入你要插入的新的边的两个顶点的名称：";
	cin>>v1>>v2;
	if(G.Insert_Arc(v1,v2))
	{
		cout<<"插入成功"<<endl;
		G.Display();
		
		cout<<"插入后深度优先遍历序列为：";
		G.DFS_Traverse();
	
		cout<<"插入后广度优先遍历序列为：";
		G.BFS_Traverse();
	}

	cout<<"输入你要删除的边的另个顶点的名称：";
	cin>>v1>>v2;
	if(G.Delete_Arc(v1,v2))
	{
		cout<<"删除成功"<<endl;
		G.Display();

		cout<<"删除后深度优先遍历序列为：";
		G.DFS_Traverse();
		
		cout<<"删除后广度优先遍历序列为：";
		G.BFS_Traverse();
	}
	
	return 0;
}

测试结果：

输入定点数目和弧的数目：6 8
输入每个顶点的名称：v1 v2 v3 v4 v5 v6
输入边的两个顶点：v1 v2
输入边的两个顶点：v1 v3
输入边的两个顶点：v1 v5
输入边的两个顶点：v2 v5
输入边的两个顶点：v3 v4
输入边的两个顶点：v3 v1
该边已存在，本图不支持存在平行边
重新输入边的两个顶点：v2 v1
该边已存在，本图不支持存在平行边
重新输入边的两个顶点：v3 v6
输入边的两个顶点：v4 v2
输入边的两个顶点：v5 v4
无向图构造完成
输入顶点名称，将输出其相邻顶点：v5
顶点 v5 的邻接顶点为：v4  v2  v1
邻接多重表结构：
顶点为：v1  v2  v3  v4  v5  v6
总共有8条边
v1--v5
v1--v3
v1--v2
v2--v4
v2--v5
v3--v6
v3--v4
v4--v5
深度优先遍历序列：v1  v5  v4  v2  v3  v6
广度优先遍历序列：v1  v5  v3  v2  v4  v6
输入你要插入的新的边的两个顶点的名称：v5 v6
插入成功
顶点为：v1  v2  v3  v4  v5  v6
总共有9条边
v1--v5
v1--v3
v1--v2
v2--v4
v2--v5
v3--v6
v3--v4
v4--v5
v5--v6
插入后深度优先遍历序列为：v1  v5  v6  v3  v4  v2
插入后广度优先遍历序列为：v1  v5  v3  v2  v6  v4
输入你要删除的边的另个顶点的名称：v1 v2
删除成功
顶点为：v1  v2  v3  v4  v5  v6
总共有8条边
v1--v5
v1--v3
v2--v4
v2--v5
v3--v6
v3--v4
v4--v5
v5--v6
删除后深度优先遍历序列为：v1  v5  v6  v3  v4  v2
删除后广度优先遍历序列为：v1  v5  v3  v6  v4  v2
Press any key to continue

初始生成的无向图如下所示：

经过插入删除后生成的图就不画出来了 大家一看就知道了

写完代码 完善和debug的过程很艰辛 有时很恶心 但是自己觉得还满意 还不错后，就会觉得很爽啦 所以多自己动手写 是很好的锻炼