【汇总】图的存储方法

本篇博客汇总了多种储存图的方法，为了帮自己梳理知识qwq

（封面抽象）

一. 邻接矩阵

空间复杂度 O(n^2)。

适用于点少、边多的稠密图，不适用于点多、边少的稀疏图 。

代码框架：（均已储存无向图为例）

const int N = 10;
int g[N][N];
cin >> n >> m;
while(m--)
{
	int u, v, w;
	cin >> u >> v >> w;
	g[u][v] = w;
	g[v][u] = w;
}

二. 邻接表

空间复杂度O(n+m)。

使用于点多、边少的稀疏图 。

代码框架：

vector<int> e[N];
//e[i]:可以到达i点的边的数量
while(m--)
{
	int u, v;
	cin >> u >> v;
	e[u].push_back(v);
	e[v].push_back(u);
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n, m;
vector<int> e[N];

int main()
{
	cin >> n >>m;
	while(m--)
	{
		int u, v, w; 
		cin >> u, v, w;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
	{
		cout << i << ":";
		for(int j = 0; j < e[i].size(); j++)
		{
			cout << e[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

三. 链式前向星

struct node
{
	int to;	//到达点
	int wei; //边权
	int next; //下一条边号 
} e[N*N];
int haed[N]; //i号点邻接表的第一条边 
int cnt; //数组下标

void add(int a, int b, int c)
{
	e[++cnt].to = b;
	e[cnt].wei = c;
	e[cnt].next = head[a];
	head[a] = cnt;
}

while(m--)
{
	int u, v, w;
	cin >> u >> v >> w;
	add(u, v, w);
}
//遍历输出邻接表
for(int i = 1; i <= n; i++)
{
	cout << i << ": ";
	for(int j = head[i]; )
}

（拜拜ヾ(•ω•`)o）水了一篇