邻接表

大忽悠爱学习

发布于 2021-03-23 12:08:01

6250

发布于 2021-03-23 12:08:01

文章被收录于专栏：c++与qt学习

邻接矩阵缺点：

邻接矩阵是不错的存储结构，但是我们发现，对于边数相对于顶点较少的图，这种结构是存在对存储空间的极大浪费的

因此在处理稀疏图时，可以采用下面将要介绍的邻接表

无向图的邻接表

有向图的邻接表

网图的邻接表

邻接表存储有向图的类

有向图邻接表的构造函数初始化操作

邻接表的构造函数和输出函数代码实现

#include<iostream>
using namespace std;
//邻接链表
typedef char DataType; //顶点的数据类型
//边表结构体
struct ArcNode 
{
	int dajvex;//记录邻接点在数组中的下标
	ArcNode* next;
};
//顶点表结构体
struct VertexNode 
{
	DataType vertex;//顶点结构体的数据
	ArcNode* firstEdge;//相当于头指针，指向边表
};
const int MAX = 10; //图的最大顶点数
class Graph 
{
private:
	VertexNode adjList[MAX];//顶点表结构体数组
	int vertexNum;//顶点数
	int arcNum;//边数
public:
	Graph(DataType v[], int n, int e);
	void display();
};
//构造函数实现:用户传入的顶点结构体数组，里面存放着顶点数据  顶点数  边数
Graph::Graph(DataType v[], int n, int e) 
{
	vertexNum = n;//初始化顶点数
	arcNum = e;//初始化边数
	for (int i = 0; i < vertexNum; i++)
	{
		adjList[i].vertex = v[i]; //将用户传入的顶点数据给顶点结构体数组进行赋值
		adjList[i].firstEdge = NULL;
	}
	//建立边的关系
	for (int i = 0; i < arcNum; i++)
	{
		//输入边的信息存储在边表中
		int vi, vj;                              
		cin >> vi >> vj;//输入边依附两个顶点的编号
		ArcNode* s = new ArcNode;//将边表结构体开辟在堆区
		s->dajvex = vj;//这里是有向图，所以vi--->vj,dajvex存储的值是出度节点在数组中的下标
		//头插法
		s->next = adjList[vi].firstEdge;
		adjList[vi].firstEdge = s;
	}
}
//测试----------------
void Graph::display()
{
	for (int i = 0; i < vertexNum; i++)
	{
		cout << adjList[i].vertex << " ";
		ArcNode* workNode = adjList[i].firstEdge;
		while (workNode)
		{
			workNode = workNode->next;
			cout << workNode->dajvex <<" ";
		}
		cout << "================" << endl;
	}
}
int main()
{
	DataType v[4] = { 'v0','v1','v2','v3' };
	Graph p(v,4,4);
	p.display();
	system("pause");
	return 0;