数据结构-图形（相邻链表）

邻接矩阵好吗？这是一种图形存储结构，但是我们还发现，对于边和顶点数量相对较少的图形，这种结构会浪费存储空间. 例如，如果我们要处理如下所示的稀疏有向图，则邻接矩阵中除了arc [1] [0]权重值外没有其他弧. 实际上，这些存储空间是浪费的.

因此，选择一个新的数据结构来存储此稀疏图尤为重要. 这时，链表结构用于存储原始连接信息.

//图的邻接链表存储结构
//边表节点结构，一个adjvex用来存储邻接点的位置，一个next指针用来指向下一个节点
typedef struct EdgeNode
{
	int adjvex;  //存储顶点下标信息
	struct EdgeNode *next;
} EdgeNode;
//顶点表节点结构
typedef struct
{
	string Vexs;  //用来存储顶点信息
	EdgeNode *firstedge;  //用来存储当前顶点的下一个顶点
} VexList;
//这里用动态数组存储顶点表，然后numVertex,numEdge是一个图的顶点数和边数
typedef struct
{
	vector<VexList> VexList;
	int Vertexs, Edges;
} GraphList;

此处用于创建边表的方法是尾部插值方法. “词头数据结构”使用词头插值方法. 就个人而言链表的结构，尾部插值方法更容易理解. 其他方面与邻接矩阵创建图时的想法基本相同.

void CreateGraph(GraphList * G)
{
	string v1, v2;
	EdgeNode * e, *p, *q;
	cout << "请输入顶点数和边数：" << endl;
	cin >> G->Vertexs >> G->Edges;
	cout << "请输入顶点的信息：" << endl;
	for (int i = 0; i < G->Vertexs; ++i){
		VexList tmp;
		cin >> tmp.Vexs;
		tmp.firstedge = NULL;
		G->VexList.push_back(tmp);
	}
	for (int k = 0; k < G->Edges; ++k){
		int i, j;//(Vi，Vj)
		cout << "请输入边（Vi,Vj）：" << endl;
		cin >> i >> j;
		if (G->VexList[i].firstedge == NULL){//当前顶点i后面没有顶点
			e = new EdgeNode;
			e->adjvex = j;
			e->next = NULL;
			G->VexList[i].firstedge = e;
		}
		else{  //当前i后面有顶点
			EdgeNode *p = G->VexList[i].firstedge;
			while (p->next){
				p = p->next;
			}
			e = new EdgeNode;
			e->adjvex = j;
			e->next = NULL;
			p->next = e;
		}
		//因为是无向图，所以（Vi,Vj）与（Vj,Vi）都要连接起来
		if (G->VexList[j].firstedge == NULL){ //当前顶点j后面没有顶点
			e = new EdgeNode;
			e->adjvex = i;
			e->next = NULL;
			G->VexList[j].firstedge = e;
		}
		else{  //当前j后面有顶点
			EdgeNode *p = G->VexList[j].firstedge;
			while (p->next){
				p = p->next;
			}
			e = new EdgeNode;
			e->adjvex = i;
			e->next = NULL;
			p->next = e;
		}
	}
}

我还写了一个打印图片的功能.

//打印连接链表
void PrintGraph(GraphList *G)
{
	cout << "所建立的邻接表如以下所示：" << endl;
	for (int i = 0; i<G->Vertexs; i++){
		cout << G->VexList[i].Vexs;             //先输出顶点信息
		EdgeNode * e = G->VexList[i].firstedge;
		while (e){                           //然后就开始遍历输出每个边表所存储的邻接点的下标
			cout << "-->" << e->adjvex;
			e = e->next;
		}
		cout << endl;
	}
}

此时还需要一个全局访问数组

bool Visited_List[100];

它与基于邻接矩阵的DFS基本相同. 并不是所有的废话，只需直接输入代码即可.

//DFS
void DFS(GraphList *G, int i)
{
	EdgeNode * p;
	Visited_List[i] = true;
	cout << G->VexList[i].Vexs << "  ";
	p = G->VexList[i].firstedge;
	while (p){
		if (!Visited_List[p->adjvex])
			DFS(G, p->adjvex);
		p = p->next;
	}	
}
void DFSTraver(GraphList *G)
{
	cout << "深度优先遍历顺序：" << endl;
	for (int i = 0; i<G->Vertexs; ++i)
		Visited_List[i] = false;
	for (int i = 0; i<G->Vertexs; ++i){
		if (!Visited_List[i])
			DFS(G, i);
	}
	cout << endl;
}

这里的想法基本上与邻接矩阵相同，也就是说，现在在一个链表中遍历了边表.

//BFS  特点要使用队列，很像树的层序遍历
void BFSTraver(GraphList *G)
{
	cout << "广度优先遍历顺序：" << endl;
	EdgeNode * p;
	queue<int> Q;
	for (int i = 0; i<G->Vertexs; ++i)
		Visited_List[i] = false;
	for (int i = 0; i<G->Vertexs; ++i){
		if (!Visited_List[i]){
			Visited_List[i] = true;
			cout << G->VexList[i].Vexs << "  ";
			Q.push(i);
			while (!Q.empty()){
				i = Q.front();
				Q.pop();
				p = G->VexList[i].firstedge;
				while (p){//把当前顶点下相连接的点找完
					if (!Visited_List[p->adjvex]){
						Visited_List[p->adjvex] = true;
						cout << G->VexList[p->adjvex].Vexs << "  ";
						Q.push(p->adjvex);
					}
					p = p->next;
				}
			}
		}
	}
}

emmmm链表的结构，是时候再次进行测试了. . . 取相同的测试数据，然后输入如下所示的数据.

结果:

结束！

参考以前的人们的工作

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-238794-1.html