数据结构之图的邻接表存储方法

图的邻接表是一种顺序分配（如数组）和链式分配（如链表）相结合的存储方法。其中数组（顺序分配）用来存放图的各个顶点的数据信息，链表（链式分配）用来存放依附于相应顶点的边的信息。

数组中的每个顶点的信息都是由两部分组成的：顶点域和指针域。结构如下：

其中，V表示顶点域，用来存放顶点数据信息，Link表示指针域，用来表示依附于该顶点的第一条边的链结点地址。

网的链表每个节点包含三个要素：顶点位置，权值，指针域。若图不是网络，则可以去掉权值这个要素。结构如下：

其中，Position表示与链表中与头结点相连边的另一端点的顶点位置，Weight表示该条边的权值，Next指出与头结点邻接的下一条边对应的边结点的位置。

通常情况下，我们将n个顶点的数据信息存放在一个V[n]数组中，该数组中的每一个数据均表示链表的头结点，共有n个链表。举个例子，如下图所示：

该图中共有5个顶点，因此顶点数组下标为0~4。顶点1,2之间存在权值为3的边，顶点2,3之间存在权值为4的边，顶点3,4之间存在权值为9的边，顶点4,5之间存在权值为6的边，顶点5,1之间存在权值为2的边。邻接表如下：

下面我们通过代码来构建以下上述图中的邻接表。

首先建立顶点与边结点的结构。

//邻接表的边结点类型




typedef struct edge {




	int adjvex;	//该边的终止顶点在顶点数组中的位置




	int weight;	//该边的权值




	edge* next;	//指向下一个边结点




}ELink;



//邻接表的顶点类型




typedef struct ver {




	int vertex;	//顶点的数据信息




	ELink* link;	//指向第一条边对应的边结点




}VLink;

然后创建一个邻接表。

void createAdjacencyList( VLink* G, int n, int e ) 



{



	int VInfo;	//邻接表的数据信息




	int vi, vj, weight;//边结点与权值




	ELink *pFirst, *pLast;



	cout << "请按顺序输入邻接表顶点的数据信息：" << endl;



	for (int i=0; i<n; i++) {	//输入顶点数组




		cout << "请输入第" << i+1 << "个顶点的数据信息：" << endl;



		cin >> VInfo;



		G[i].vertex = VInfo;



		G[i].link = NULL;



	}



 



	cout << "请输入邻接表边结点的数据信息（输入顺序：连接点1的位置编号，连接点2的位置编号，权值）：" << endl;



	for(int i=0; i<e; i++) {	//输入边的信息




		cout << "请输入第" << i+1 << "条边的数据信息：" << endl;



		cin >> vi >> vj >> weight;



		pFirst = new ELink;



		pFirst->adjvex = vj;



		pFirst->weight = weight;



		pFirst->next = NULL;



		pLast = new ELink;



		pLast->adjvex = vi;



		pLast->weight = weight;



		pLast->next = NULL;



		insertElement(G, vi, pFirst); //该函数用来将边信息pFirst链接在顶点数组G的第vi个顶点后面




		insertElement(G, vj, pLast);



	}



}

上述代码中的insertElement函数表示如下：

//该函数用来将边信息p插入到顶点数组G的pos位置之后



void insertElement( VLink* G, int pos, ELink * p ) 



{



	ELink *q;



	if (G[pos].link == NULL)	{



		G[pos].link = p;



	}



	else {



		q = G[pos].link;



		while(q->next) {



			q = q->next;



		}



		q->next = p;



	}



}

然后，我们将该邻接表打印出来，用来测试上述创建邻接表是否正确。

void printAdjacentcyList( VLink* G, int n ) 



{



	cout << "打印邻接表信息如下：" << endl;



	ELink* p;



	for(int i=0; i<n; i++) {



		cout << G[i].vertex;



		p = G[i].link;



		while (p) {



			cout << "---->" << p->adjvex << "|" << p->weight;



			p = p->next;



		}



		cout << endl;



	}



}

主函数如下：

int _tmain(int argc, _TCHAR* argv[])



{



	int n, e;



	cout << "请输入图的顶点数：" << endl;



	cin >> n;



	cout << "请输入图的边数：" << endl;



	cin >> e;



 



	VLink* G = new VLink[n];



	createAdjacencyList(G, n, e);



	printAdjacentcyList(G, n);



	delete G;



 



	return 0;



}

将上述示例中图的信息输入后，控制台输出信息如下图所示。