图的存储与遍历C++实现

1、图的存储

设点数为n,边数为m

1.1、二维数组

方法：使用一个二维数组 adj 来存边，其中 adj[u][v] 为 1 表示存在 u到 v的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储u到v的边的边权。
复杂度:
- 查询是否存在某条边：\(O(1)\)
- 遍历一个点的所有出边：\(O(n)\)
- 遍历整张图：\(O(n^2)\)
- 空间复杂度：\(O(n^2)\)

1.2、邻接表

方法：使用一个支持动态增加元素的数据结构构成的数组，如 vector< int> adj[n + 1] 来存边，其中 adj[u] 存储的是点u的所有出边的相关信息（终点、边权等）；
复杂度:
- 查询是否存在u到v的边：\(O(d^+(u))\)（如果事先进行了排序就可以使用二分查找做到\(O(log(d^+(u)))\) ）。
- 遍历点u的所有出边：\(O(d^+(u))\)。
- 遍历整张图：O(n+m)。
- 空间复杂度：O(m)。

1.3、直接存边

方法：使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）
```
struct Edge{

	int u,v;//边的端点

	int w;//权重

}Edges[MAXN];
```
复杂度:
- 查询是否存在某条边：\(O(m)\)。
- 遍历一个点的所有出边：\(O(m)\)。
- 遍历整张图：\(O(nm)\)。
- 空间复杂度：\(O(m)\)。
由于直接存边的遍历效率低下，一般不用于遍历图。在Kruskal算法中，由于需要将边按边权排序，需要直接存边

1.4、链式前向星（本质是用数组模拟链表）

方法：本质是用数组模拟链表，主要有两个数组

Edges[MAXN] 存储边的信息，包括两个端点、权重、下一条边在Edges中的索引；

head[MAXN] head[i]为节点i的第一条出边在Edges中的序号；

在插入边的时候维护一个tot变量记录总计的边的个数

复杂度：
- 查询是否存在u到v的边：\(O(d^+(u))\)（如果事先进行了排序就可以使用二分查找做到\(O(log(d^+(u)))\) ）。
- 遍历点u的所有出边：\(O(d^+(u))\)。
- 遍历整张图：O(n+m)。
- 空间复杂度：O(m)。

代码板子：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

struct Edge

{//边结构体

	int u,v;//边的端点；

	int w;//权重

	int nxt;//下一条边在Edge中的索引

}Edges[MAXN];

int head[MAXN];//每个节点出边

int tot;//总的边数,随着边的增加而增加

void init(int n){

	tot=0;

	//初始化head数组

	for(int i=0; i<n; i++)

		head[i]=-1;

	//memset(head,-1,sizeof(head));

	//memset是以字节为单位，初始化内存块

	//字节单位的数组时，可以用memset把每个数组单元初始化成任何你想要的值

	//因为一个int类型的变量占4个字节，而memset是将每一个字节初始化成1，

	//所以一个int类型的变量被初始化成了0x01010101。而这个数是16843009

	//memset初始化int只能初始化0和-1；

}

void addEdge(int u,int v,int w){

	Edges[tot].u=u;

	Edges[tot].v=v;

	Edges[tot].w=w;

	Edges[tot].nxt=head[u];

	head[u] = tot;

	tot++;

}

2、图的遍历

2.2、dfs(深度优先 depth first search)

基于上述的链式前向星实现

void dfs(int u) {

  //v 可以是图中的一个顶点

  //也可以是抽象的概念，如 dp 状态等，这一点很难想

  vis[u] = 1; //标记该节点被访问过

  for (int i = head[u]; i; i = Edges[i].nxt) {

    if (!vis[Edges[i].v]) {

    //task to do

    dfs(v);

    }

  }

}

2.3、bfs(宽度优先 breadth first search)

每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。这样做BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路所包含的边数最小。在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

基于上述的链式前向星实现:

void bfs(int u){

	vector<int> d;//记录到达各个节点的最近距离；

	vector<int> p;//记录最短路上的节点

	vector<int> vis(MAXN,0);//0代表节点未被访问过

	queue<int> q;

	q.push(u);

	vis[u]=1;//标记访问

	d[u]=0;

	p[u]=-1;

	while(!q.empty()){

		u=q.front();

		q.pop();

		for(int i=head[u]; i; i=Edges[i].nxt){

		  int v = Edges[i].v;//到达的点

		  if(!vis[v]){

		      q.push(v);

		      vis[v]=1;

		      d[v]=d[u]+1;

		      p[v]=u;//记录前序节点

		      //task to do

		  }

		}

	}

}

看到这里的朋友，祝你生活愉快，完事顺意！

️

巴特西

图的存储与遍历C++实现

1、图的存储

1.1、二维数组

1.2、邻接表

1.3、直接存边

1.4、链式前向星（本质是用数组模拟链表）

2、图的遍历

2.2、dfs(深度优先 depth first search)

2.3、bfs(宽度优先 breadth first search)

最新文章

热门文章