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

lovecontry

浏览: 1095007 次

最近访客更多访客>>

u012363178

seven.zhou

hone

zclzcllll

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1381)

社区版块

存档分类

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

测试结果：

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