ZJU 数据结构课程笔记 | 堆

这是我在学习浙江大学 MOOC『数据结构』的第五章：图 的过程中做的笔记。

ZJU 数据结构 MOOC 课程链接

什么是图

表示多对多的关系.
包含
- 一组顶点: 用V(Vertex)表示顶点集合.
- 一组边: 通常用E(Edge)表示边的集合.
  - 边是顶点对: (v, w) E, 其中v, w V.
  - 有向边<v, w>表示从v指向w的边(单行线).
  - 不考虑重边与自回路

在程序中表示一张图

邻接矩阵表示法

N个顶点从0到N-1进行编号

$若是中的边若不是中的边$

typedef struct GNode *PtrToGNode;
struct GNode {
	int Nv; //顶点数
	int Ne; //边数
	WeightType G[MaxVertexNum][MaxVertexNum];
	DataType Data[MaxVertexNum]; //存顶点数据
};
typedef PtrToGNode MGraph; //以邻接矩阵存储的图的类型

容易理解, 但浪费时间与空间

邻接表

G[n]为指针数组, 对应矩阵每行一个链表, 只存非零元素

对于网络, 结构中要增加权重域

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
	Vertex AdjV; //邻接点下标
	WeightType Weight; //边权重
	PtrToAdjVNode Next;
};
typedef struct VNode {
	PtrToAdjVNode FirstEdge;
	DataType Data; //顶点数据
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode {
	int Nv; //顶点数
	int Ne; //边数
	AdjList G; //邻接表
};
typedef PtrToGNode LGraph; //以邻接矩阵存储的图的类型

当图够稀疏时, 使用邻接表较为合算

图的遍历

深度优先搜索(Depth First Search)

void DFS(Vertex V)
{
	visited[V] = true;
	for (V的每个邻接点w) {
		if (! visited[W])
			DFS(W);
	}
}

广度优先搜索(Breadth First Search)

void BFS(Vertex V)
{
	visited[V] = true;
	Enqueue(V, Q);
	while(! IsEmpty(Q)) {
		V = Dequeue(Q);
		for (V的每个邻接点w)
			if(! visited[w]) {
				visited[w] = true;
				Enqueue(W, Q);
			}
	}
}

图的连通性

若从v到w存在一条(无向)路径, 则称v和w是连通的.
v到w的路径是一系列顶点的集合, 其中任一对相邻的顶点间都有图中的边. 路径的长度是路径中的边数(带权值则为权值和). 若v到w间所有顶点都不同, 称为简单路径.
回路: 起点等于终点.
连通图: 图中任意顶点均连通.
连通分量: 无向图的极大连通子图
- 极大顶点数
- 极大边数
强连通: 有向图中v与w间存在双向路径.
强连通图: 有向图的极大强连通子图

图的最短路径问题

无权图的单源最短路算法

递减/递增顺序找出到各顶点的最短路

void Unweighted(Vertex S)
{
	Enqueue(S, Q);
	while (! IsEmpty(Q)) {
		V = Dequeue(Q);
		for (V的每个邻接点w)
			if (dist[w] == -1) {
				dist[w] = dist[V] + 1;
				path[w] = V;
				Enqueue(W, Q);
			}
	}
}

有权图的单源最短路算法

递增顺序找出到各顶点的最短路

迪杰斯特拉算法

void Dijkstra(Vertex s)
{
	while (1) {
		V = 未收录顶点中dist最小者;
		if (V not exist)
			break;
		collected[V] = true;
		for (V的每个邻接点)
			if (collected[w] == false)
				if (dist[V] + E<V, W> < dist[W]) {
					dist[W] = dist[V] + E<V, W>;
					path[W] = V;
				}
	}
}

多源最短路径问题

弗洛伊德算法

void Floyd*()
{
	for (int i = 0; i < N; i ++) {
		for (int j = 0; j < N; j ++) {
			D[i][j] = G[i][j]; //邻接矩阵
			path[i][j] = - 1;
		}
	}
	for (int k = 0; k < N; k ++) {
		for (int i = 0; i < N; i ++) {
			for (int j = 0; j < N; j ++) {
				if (D[i][k] + D[k][j] < D[i][j]) {
					D[i][j] = D[i][k] + D[j][k];
					path[i][j] = k; // 记录路径, 便于递归打印
				}
			}
		}
	}
}

图的最小生成树问题

如果连通图G的一个子图是包含G的所有结点的树, 则称该子图为G的生成树（Spanning Tree).

向生成树中任意加入一条边都一定构成回路.

最小生成树是边的权重和最小的生成树.

最小生成树存在条件:

图连通.
图中包含N个结点和N-1条边.

最小生成树存在图连通

利用贪心算法解决最小生成树问题.

只能用图里已有的边.
正好用掉条边.
不能有回路.

Prim算法

让一棵小树长大

每次选择最小边, 注意所选择的边不构成回路.

void Prim()
{
	MST = {s}; //选定根节点
	while (1) {
		V = 未收录顶点中dist最小者;
		if (V not exist) 
			break;
		MST = {s} + V; //收录该顶点
		for (V的每个邻接点)
			if (w未被收录) {
				if(E(V, W) < dist[W]) {
					dist[W] = E(V, W);
					parent[W] = V;
				}
			}
	}
	if(MST内存储顶点不到|V|个)
		Error("生成树不存在");
}

该算法时间复杂度为o().

Prim算法一般用于解决稠密图的最小生成树问题.

Kruskal算法

把森林合并成树

初始状态为每个顶点构成一棵树, 每次收录权重最小的边, 使得多棵树合并为一棵树, 所收录的边不构成回路.

void Kruskal(Garph G)
{
	MST = { };
	while (MST中不到|V| - 1条边 && E中还有边) {
		从E中取一条权重最小的边E(V, W); //最小堆
		delete(E, E(V, W));
		if(E(V, W)不在MST中构成回路) //并查集
			add(MST, E(V,W));
		else 
			continue;
	}
	if (MST中不到|V| - 1条边)
		Error("生成树不存在");
}

该算法时间复杂度为o().

拓扑排序

拓扑序: 针对有向无环图(DAG), 找到一个可以执行的线性顺序.

如果这个图不是 DAG，那么它是没有拓扑序的;
如果是 DAG，那么它至少有一个拓扑序;
反之，如果它存在一个拓扑序，那么这个图必定是 DGA.

**算法思路: **随时将入度变为0的结点放入一个容器中.

void TopSort(Graph G)
{
	int cnt = 0;
	for (every V in G)
		if (Indegree[V] == 0)
			Enqueue(V, Q);
	while (! Isempty(Q)) {
		V = Dequeue(Q);
		输出V, 或者记录V的输出序号;
		cnt ++;
		for (every adjacency point W of V)
			if (-- Indegree[W] == 0)
				Enqueue(W, Q);
	}
	if (cnt != |V|)
		Error("there are cercuit in the map.")
}

关键路径问题

AOE(Activity On Edge)网络

安排项目工序

拓扑排序主要解决「工程是否能顺序进行」的问题, 关键路径在拓扑排序的基础上解决「工程最短时间的问题」.