当前位置：首页 > news >正文

c++数据结构：图（邻接表）

news 来源：原创 2024/5/21 0:47:16

邻接表是图的一种链式结构。

邻接表的结构为:

表节点
头结点

邻接表的表示方法：

邻接表不唯一
适合存储稀疏图，当有n个节点和e个边时，需要n个头结点，2e个边节点
时间复杂度为：O(n*e)
空间复杂度为: O(n+2e)

顶点的出度为：链表节点的个数
顶点的入度为：需要遍历整个单链表
找出度易，找入度难
想更容易的找到入度的话，可以构建逆邻接表：（指向反转）

邻接矩阵和邻接表的区别：

邻接矩阵是唯一的，邻接表不唯一
邻接矩阵的空间复杂度：O（n^2）邻接表为的空间复杂度：O（n+e）
邻接矩阵多用于稠密图，邻接表多用于稀疏图

图的邻接表结构：（图）

#define Max_Num 50
class table_node//表节点
{
public:
	int adjvex;//邻接点所在的位置
	table_node* nextarc;//下一个弧
};
class head_node//头结点
{
public:
	char data;//顶点数据
	table_node* firstarc;//首弧的位置
};

class ADList
{
public:
	head_node adlist[Max_Num];//邻接表
	int vexnum;//顶点个数
	int arcnum;//弧的数量

    int find_num(char a);//寻找顶点位置
	void add_DU();//无向图的生成
};

无向图的实现：

int ADList::find_num(char a)寻找顶点位置
{
	for (int i = 0; i < vexnum; i++)
	{
		if (adlist[i].data == a)//如果数组中查找到下标
			return i;//返回下标
	}
	return	-1;//没有则返回-1
}
void ADList::add_DU()//无向图的生成
{
	cin >> vexnum >> arcnum;//输入顶点个数，弧的数量
	for (int i = 0; i < vexnum; i++)
	{
		cin >> adlist[i].data;//输入顶点的数据
		adlist[i].firstarc->nextarc = nullptr;//首弧的指针初nextarc始化为nullptr
	}
	for (int i = 0; i < arcnum; i++)//添加弧
	{
		char n, m;
		cin >> n>>m;//输入顶点
		int x = find_num(n);//获取顶点数组位置
		int y = find_num(m);
		table_node* p = new table_node(x);//新的表节点
		table_node* p1 = new table_node(y);//新的表节点
		//利用尾插法插到链表中
		p1->nextarc = adlist[x].firstarc->nextarc;//将p1插到数组下标为x的单链表中
		adlist[x].firstarc->nextarc = p1;

		p->nextarc = adlist[y].firstarc->nextarc;//将p插到数组下标为y的单链表中
		adlist[y].firstarc->nextarc = p;
	}
}

无向网的实现：

//邻接表(网)
#define Max_Num 50
class table_node//表节点
{
public:
	int adjvex;//邻接点所在的位置
	table_node* nextarc;//下一个弧
	int weight;//权值
	table_node(int i = 0,int w=0) :adjvex(i), weight(w),nextarc(nullptr) {}//构造函数

};
class head_node//头结点
{
public:
	char data;//顶点数据
	table_node* firstarc;//首弧的位置
};

class ADList
{
public:
	head_node adlist[Max_Num];//邻接表
	int vexnum;//顶点个数
	int arcnum;//弧的数量
	int find_num(char a);//寻找顶点位置
	void add_DU();//无向图的生成
};
int ADList::find_num(char a)寻找顶点位置
{
	for (int i = 0; i < vexnum; i++)
	{
		if (adlist[i].data == a)//如果数组中查找到下标
			return i;//返回下标
	}
	return	-1;//没有则返回-1
}
void ADList::add_DU()//无向图的生成
{
	cin >> vexnum >> arcnum;//输入顶点个数，弧的数量
	for (int i = 0; i < vexnum; i++)
	{
		cin >> adlist[i].data;//输入顶点的数据
		adlist[i].firstarc->nextarc = nullptr;//首弧的指针初nextarc始化为nullptr
	}
	for (int i = 0; i < arcnum; i++)//添加弧
	{
		char n, m; int w;
		cin >> n>> m>>w;//输入两个顶点，和一个权值
		int x = find_num(n);//获取顶点数组位置
		int y = find_num(m);
		table_node* p = new table_node(x,w);//新的表节点
		table_node* p1 = new table_node(y,w);//新的表节点
		//利用尾插法插到链表中
		p1->nextarc = adlist[x].firstarc->nextarc;//将p1插到数组下表为x的单链表中
		adlist[x].firstarc->nextarc = p1;

		p->nextarc = adlist[y].firstarc->nextarc;//将p插到数组下表为y的单链表中
		adlist[y].firstarc->nextarc = p;
	}
}