【数据结构】链式向前星

博主： Fivk
发布时间：2022 年 03 月 12 日
918 次浏览
1429字数
分类：数据结构

> 树是一种特殊的图（无环连通图）， 图分为**有向图**和**无向图**，而**无向图**只是一种特殊的有向图，所以我们只需要考虑如何建立有向图即可。

有向图的存储一般分为两大类，第一种是用的比较少的，第一种是邻接矩阵，第二种是邻接表。

# 1.邻接矩阵

方法：使用一个二维数组 `g` 来存边，其中 `g[u][v]` 为 1 表示存在 $u$到$v$的边，为 0 表示不存在。如果是带边权的图，可以在 `g[u][v]` 中存储$u$到$v$的边的边权。

</div>

## 案例

<div class="inner-content" >
<p class="inser-title">【算法基础】最短距离Dijkstra</p>
<div class="inster-summary text-muted">
因为之前已经介绍过了，现在就不仔细介绍了，直接上算法。朴素版从s到t的最短距离算法流程：b[]表示当前已经确定最短...
</div>
</div>
</a>

</div>

</div>

<div class="inner-content" >
<p class="inser-title">【数据结构】图论算法_最短路径算法</p>
<div class="inster-summary text-muted">
如图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点中的距离会有不同的路径...
</div>
</div>
</a>

</div>

</div>

<div class="inner-content" >
<p class="inser-title">【数据结构】图论算法_最小树生成</p>
<div class="inster-summary text-muted">
一、什么是图的最小生成树（MST）不知道大家还记不记得树的一个定理：N个点用 N - 1 条边连接成一个连通块，形...
</div>
</div>
</a>

</div>

</div>

## 复杂度

查询是否存在某条边：$O(1)$。

遍历一个点的所有出边：$O(n)$。

遍历整张图：$O(n^2)$。

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

## 应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以$O(1)$查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

# 2.邻接表

使用一个支持动态增加元素的数据结构构成的数组，如 `vector<int> g[n + 1]` 来存边，其中 `g[u]` 存储的是点  的所有出边的相关信息（终点、边权等）。

</div>

## 代码实现

### 数据定义

> h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。

```cpp
int h[N], e[M], ne[M], idx;
bool st[N];
```

### 插入边

> 插入一条a指向b的边

```cpp
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
```

### 遍历

#### 深度优先遍历

```cpp
void dfs(int u) {
	st[u] = true;	// 标记已经被遍历过了
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) dfs(j);
	}
}
```

#### 广度优先遍历

```cpp
void bfs() {
	int q[N];	// 定义队列 
	int hh = 0, tt = 0;	// 头和尾指针 
	memset(st, 0, sizeof st);
	q[0] = 1;
	while (hh <= tt) {
		int t = q[hh ++];
		st[t] = true;
		cout << t << ' ';
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (!st[j]) {
				q[++ tt] = j;
			}
		}
	}
}
```

## 复杂度

查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$（如果事先进行了排序就可以使用 [二分查找](https://blog.fivk.cn/archives/1090.html) 做到 $O(\log(d^+(u)))$）。

遍历点 $u$ 的所有出边：$O(d^+(u))$。

遍历整张图：$O(n+m)$。

空间复杂度：$O(m)$。

## 应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

## 实现案例

```cpp
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = N * 2;

// h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。 
int h[N], e[M], ne[M], idx;
bool st[N];
int n;	// n条边

// 插入一条a指向b的边 
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// 深度优先遍历
void dfs(int u) {
	cout << u << ' ';
	st[u] = true;	// 标记已经被遍历过了
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) dfs(j);
	}
}

// 广度优先遍历 
void bfs() {
	int q[N];	// 定义队列 
	int hh = 0, tt = 0;	// 头和尾指针 
	memset(st, 0, sizeof st);
	q[0] = 1;
	while (hh <= tt) {
		int t = q[hh ++];
		st[t] = true;
		cout << t << ' ';
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (!st[j]) {
				q[++ tt] = j;
			}
		}
	}
}

int main () {
	memset(h, -1, sizeof h);
	cin >> n;

for (int i = 1; i <= n; i ++) {
		int a, b;
		cin >> a >> b; 
		add(a, b);
		add(b, a);
	}

cout << "深度优先遍历：";
	dfs(1);
	cout << endl;
	cout << "广度优先遍历：";
	bfs(); 
	return 0;
}
```

> 输入样例
>
> ```in
> 8
> 1 2
> 1 7
> 1 4
> 2 8
> 2 5
> 4 3
> 3 9
> 4 6
> ```
> 输出样例
>
> ```out
> 深度优先遍历：1 4 6 3 9 7 2 5 8
> 广度优先遍历：1 4 7 2 6 3 5 8 9
> ```

最后修改：2022 年 04 月 18 日

如果觉得我的文章对你有用，请随意赞赏

【数据结构】链式向前星

Fivk • 2022 年 03 月 12 日

> 树是一种特殊的图（无环连通图）， 图分为**有向图**和**无向图**，而**无向图**只是一种特殊的有向图，所以我们只需要考虑如何建立有向图即可。

有向图的存储一般分为两大类，第一种是用的比较少的，第一种是邻接矩阵，第二种是邻接表。

# 1.邻接矩阵

</div>

## 案例

## 复杂度

查询是否存在某条边：$O(1)$。

遍历一个点的所有出边：$O(n)$。

遍历整张图：$O(n^2)$。

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

## 应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以$O(1)$查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

# 2.邻接表

使用一个支持动态增加元素的数据结构构成的数组，如 `vector<int> g[n + 1]` 来存边，其中 `g[u]` 存储的是点  的所有出边的相关信息（终点、边权等）。

</div>

## 代码实现

### 数据定义

> h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。

```cpp
int h[N], e[M], ne[M], idx;
bool st[N];
```

### 插入边

> 插入一条a指向b的边

```cpp
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
```

### 遍历

#### 深度优先遍历

```cpp
void dfs(int u) {
	st[u] = true;	// 标记已经被遍历过了
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) dfs(j);
	}
}
```

#### 广度优先遍历

## 复杂度

查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$（如果事先进行了排序就可以使用 [二分查找](https://blog.fivk.cn/archives/1090.html) 做到 $O(\log(d^+(u)))$）。

遍历点 $u$ 的所有出边：$O(d^+(u))$。

遍历整张图：$O(n+m)$。

空间复杂度：$O(m)$。

## 应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

## 实现案例

```cpp
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = N * 2;

// h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。 
int h[N], e[M], ne[M], idx;
bool st[N];
int n;	// n条边

// 插入一条a指向b的边 
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// 深度优先遍历
void dfs(int u) {
	cout << u << ' ';
	st[u] = true;	// 标记已经被遍历过了
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) dfs(j);
	}
}

int main () {
	memset(h, -1, sizeof h);
	cin >> n;

for (int i = 1; i <= n; i ++) {
		int a, b;
		cin >> a >> b; 
		add(a, b);
		add(b, a);
	}

cout << "深度优先遍历：";
	dfs(1);
	cout << endl;
	cout << "广度优先遍历：";
	bfs(); 
	return 0;
}
```

> 输入样例
>
> ```in
> 8
> 1 2
> 1 7
> 1 4
> 2 8
> 2 5
> 4 3
> 3 9
> 4 6
> ```
> 输出样例
>
> ```out
> 深度优先遍历：1 4 6 3 9 7 2 5 8
> 广度优先遍历：1 4 7 2 6 3 5 8 9
> ```

【数据结构】链式向前星

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【C】内存布局

【Java】集合

【Java】运算符、表达式、方法

C语言入门这一篇就够了-学习笔记(一万字)

【前端笔记】CSS3

【数据结构】链式向前星