图的三种存储方式

邻接表

稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#define MAXN 1005;
using namespace std;
struct edge{
	int to,cost;
};
int n,m;
vector <edge> p[MAXN];
int v[MAXN][MAXN];
int main()
{
	cin>>n>>m;
	for(int i=1;i<m;i++)
	{
		int u,v,l;
		cin>>u>>v>>l;
		p[u].push_back(edge{v,l})
	}//p[v].push_back(edge{u,l});当是无向图在加一条边 
	//把邻接表转换为邻接矩阵
	//p[u].size() 代表第u个点几条边 p[u].clear() 清除u的全部边 
	for(int i=1;i<=n;i++)
{
	for(int j=0;j<p[i].size();j++)
	{
		v[i][p[i][j].to]=p[i][j].cost;
	}
}
 
}

DFS BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <queue>
#define MAXN 1005
using namespace std;
struct edge{
	int to,cost;
};
queue<int> q;
int n,m;
vector <edge> p[MAXN];
int v[MAXN][MAXN];
bool vis[MAXN],vis2[MAXN];
void dfs(int x)//dfs——深度优先遍历，x表示当前遍历到x号顶点
{
	vis[x]=1;//这个顶点已经走过啦！
	cout<<x<<" ";
	for(int i=0;i<p[x].size();i++)//一条一条边去搜索
	{
		int point=p[x][i].to;//找出当前这条边（也就是e[x][i]）的终点
		if(!vis[point]){//如果这个点没走过
			dfs(point);//那就接着往下搜吧！
		}
	}
}
void bfs(int x)
{
	q.push(x);
	cout<<x<<" ";
	vis2[x]=1;
	while(q.empty()!=1)
	{
		int fro=q.front();  //把队首取出来
		for(int i=0;i<p[fro].size();i++){   //每条边去试
			int point=p[fro][i].to;  //取终点（和dfs差不多）
			if(!vis2[point]){  //没访问过，推进去，输出，标记
				q.push(point); 
				cout<<point<<" ";
				vis2[point]=1;
			}
		}
		q.pop();  //队首搜完啦！把它弄出去
	}
	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		p[u].push_back(edge{v,0});
		p[v].push_back(edge{u, 0});
	}
	dfs(1);
	cout<<endl;
	bfs(1);

}

1
2
3
也就是说p不是传统的二维数组，起到了类似二维数组的作用吗
ChatGPT
是的，你理解得很对。尽管 p 的定义看起来像是一个二维数组，但它实际上是一个一维数组，其中的每个元素都是一个向量（vector），这个向量存储了与对应顶点相关联的边的信息。在这种情况下，p 数组模拟了二维数组的行的概念，其中每一行都是一个向量，表示一个顶点和与它相连的边。这种方式更加灵活，特别适用于表示稀疏图，其中每个顶点的边数可能不同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
假设你有一个简单的无向图，包含四个顶点（1，2，3，4）和以下边：

(1, 2)
(1, 3)
(2, 4)
(3, 4)
根据这个图，我们可以构建 p 数组的结构。以下是在图中添加这些边后，p 数组的结构：

plaintext
Copy code
p[1]: { {2, 0}, {3, 0} }
p[2]: { {1, 0}, {4, 0} }
p[3]: { {1, 0}, {4, 0} }
p[4]: { {2, 0}, {3, 0} }
这表示：

顶点 1 有两条边，分别连接到顶点 2 和顶点 3。
顶点 2 有两条边，分别连接到顶点 1 和顶点 4。
顶点 3 有两条边，分别连接到顶点 1 和顶点 4。
顶点 4 有两条边，分别连接到顶点 2 和顶点 3。
每个 p[i] 都是一个向量，包含了与顶点 i 相关联的边的信息。

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#define MAXN 1005;
using namespace std;
int n;
int v[MAXN][MAXN];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>v[i][j];
		}
	}//建图  
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(v[i][j]>0)
			{
				cout<<"edge from point"<<i<<"to point"<<j<<"with length"<<v[i][j]<<endl;
			}
		}
	}
	return 0;
}

无脑

简单

适合稠密图

链式前向星

学🏀杯在学

现在可以不用

算了 也学学吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
int dis[500010],n,m,f,g,w,t=1,s,q[200000],h,st[500010],tot;
bool vis[100010];
/*
st[i]表示到达i点的最后一条边的编号； 
dis[i]表示从起点到i点目前为止的最短距离； 
vis[i]=true表示点i在队列里； 
vis[i]=false表示点i不在队列里； 
数组q是队列； 
h是指队列的头指针，t是指队列的尾指针； 
*/
struct node //不开结构体，变量有点乱，所以开结构体； 
{ 
    int to;//这条边连接的终点； 
    int v;//这条边的长度； 
    int last;//前一条边； 
}e[500010]; 
void add(int from,int to,int val)
/*
val表示传入的这条边的权值； 
from表示传入的这条边的起点； 
to表示传入的这条边的终点； 
*/
{     
    tot++;//表示当前这条边的编号； 
    e[tot].to=to;//更新当前这条边的终点； 
    e[tot].v=val;//更新当前这条边的长度（权）； 
    e[tot].last=st[from];
/*
    e[tot].last表示的是当前读入的这条边的上一条边； 
    st[from]表示的是 到当前读入的边为止（不包括这条边） 的上一条边的序号； 
*/
    st[from]=tot;//更新为 当前读入的边为止（包括这条边） 的上一条边的序号；
}

最短路

弗洛伊德

必须用邻接矩阵