邻接多重表存储无向图以及有关操作
数据结构是编程里面最重要的一门基础课之一,所以学多少遍都不可以嫌多,算法的知识当然是融在其中,多练习,多思考,基础打好了,其他的东西学起来也就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)
{
//搜索对应的边是