图的几种存储方式

之前几天把数据结构扔在一边，在看离散数学的图论部分，看了大部分，最后还是觉得纯数学的，有一些可能现在我刚接触图还不会觉得有什么用，所以就选择性的跳过一些，现在也决定先放下书，回到数据结构上，开始图的部分的学习。

图的存储通用的存储方式有邻接矩阵表示法、邻接表表示法。为方便有向图的顶点的入度与出度的计算，有 有向图的十字链表表示法。为方便对无向图的边进行操作，有 无向图的邻接多重表表示法。

邻接矩阵表示法应该算是最容易的一种表示法，一些简单的操作比如查找某顶点的指定邻接点等很容易实现。

邻接表表示在计算无向图顶点的度很方便，计算有向图的出度也很方便，但是计算入度的话就要从第一个结点开始遍历，比较麻烦，这时采用逆邻接表表示法的话，求有向图的入度就会很方便，相应的，出度就不方便了，所以要根据需要选择存储结构。

如果在程序中要统计有向图的度，那么最好的方式就是采用十字链表的存储方式。

邻接多重表可以看作是对无向图的邻接矩阵的一种压缩表示，当然这种结构在边的操作上会方便很多，但是我现在还没学到，所以暂时还不知道。下面是几种表示方法的算法实现，逆邻接表和邻接表的实现方式几乎一样，所以就不贴出来了。

#define MAX_VERTEX_NUM 20

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

template<class T>
int Locate_Vex(T G,string x) //定位顶点位置
{
	for(int k=0;G.vexs[k]!=x;k++);
	return k;
}

//邻接矩阵存储图
struct MGraph
{
	string vexs[MAX_VERTEX_NUM];//顶点数组
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
	int vexnum;//顶点数目
	int arcnum;//边数目
};

void CreateUDN_MG(MGraph &G)
{
	//采用邻接矩阵表示法，构造无向网
	cin>>G.vexnum>>G.arcnum;
	for(int i=0;i<G.vexnum;i++)
		cin>>vaxs[i];
	
	for(i=0;i<G.vexnum;i++)
		for(int j=0;j<G.vexnum;j++)
			G.arcs[i][j]=-1;
	//上面是初始化邻接矩阵，-1表示两点间边的权值为无穷大
	
	for(int k=0;k<G.arcnum;k++)
	{
		string v1,v2;
		int w;
		cin>>v1>>v2>>w;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
		while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)
		{
			cout<<"结点位置输入错误,重新输入: ";
			cin>>v1>>v2>>w;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}
		G.arcs[i][j]=w;
		G.arcs[j][i]=G.arcs[i][j]; //置对称边
	}
}

//邻接表存储图
//表结点
struct ArcNode
{
	int adjvex; //弧所指向顶点的位置
	ArcNode *nextarc;// 指向下一条弧
};

//头结点
typedef struct VNode
{
	string data;//顶点名
	ArcNode *firstarc;//指向第一条关联顶点的弧
}AdjList[MAX_VERTEX_NUM];

struct ALGraph
{
	AdjList vertices;//头结点数组
	int vexnum;
	int arcnum;
};

void CreateDG_ALG(ALGraph &G)
{
	//采用邻接表存储表示，构造有向图G
	string v1,v2;
	int i,j,k;
	cin>>G.arcnum>>G.vexnum;
	
	//构造头结点数组
	for(i=0;i<G.vexnum;i++)
	{
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	}

	//输入各弧并构造邻接表
	for(k=0;k<G.arcnum;k++)
	{
		cin>>v1>>v2;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
		while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)
		{
			cout<<"结点位置输入错误,重新输入: ";
			cin>>v1>>v2;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}
	
		ArcNode *p=new ArcNode;
		p->adjvex=j;
		p->nextarc=NULL;
		p->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p;
	}
}

//十字链表方式存储有向图
//弧结点
struct ArcBox
{
	int tailvex,headvex;//弧结点头尾结点位置
	ArcBox *hlink,*tlink;//弧头和弧尾相同的弧的链域
};

//顶点结点
struct VexNode
{
	string data;
	ArcBox *firstin,*firstout;//顶点第一条入弧和出弧
};

struct OLGraph
{
	VexNode xlist[MAX_VERTEX_NUM];
	int vexnum;
	int arcnum;
};

void CreateDG_OLG(OLGraph &G)
{
	//采用十字链表存储表示，构造有向图G
	string v1,v2;
	int i,j,k;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;i++)
	{
		cin>>G.xlist[i].data;
		G.xlist[i].firstin=NULL;
		G.xlist[i].firstout=NULL;
	}
	for(k=0;k<G.arcnum;k++)
	{
		cin>>v1>>v2;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
	
		while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)
		{
			cout<<"结点位置输入错误,重新输入: ";
			cin>>v1>>v2;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}		

		ArcBox *p=new ArcBox;
		p->tailvex=i;
		p->headvex=j;
		p->hlink=G.xlist[j].firstin;
		p->tlink=G.xlist[i].firstout;
		G.xlist[i].firstout=G.xlist[j].firstin=p;
	}
}
		
//邻接多重表存储
//边结点
struct EBox
{
	int mark;//标志域，指示该边是否被访问过(0:没有 1:有)
	int ivex,jvex;//该边关联的两个顶点的位置
	EBox *ilink,*jlink;//分别指向关联这两个顶点的下一条边
};

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

struct AMLGraph
{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum;
	int arcnum;
};

void CreateUDG_AML(AMLGraph &G)
{
	//用邻接多重表存储，构造无向图G
	string v1,v2;
	int i,j,k;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i<G.vexnum;i++)
	{
		cin>>G.adjmulist[i].data;
		G.adjmulist[i].firstedge=NULL;
	}

	for(k=0;k<G.arcnum;k++)
	{
		cin>>v1>>v2;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
		
		while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)
		{
			cout<<"结点位置输入错误,重新输入: ";
			cin>>v1>>v2;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}

		EBox *p=new EBox;
		p->ivex=i;
		p->jvex=j;
		p->ilink=G.adjmulist[i].firstedge;
		p->jlink=G.adjmulist[j].firstedge;
		p->mark=0;
		G.adjmulist[i].firstedge=G.adjmulist[j].firstedge=p;
	}
}