在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。 顶点用圆圈表示，顶点的集合可以使用V表示。边就是这些圆圈之间的连线，每一条边可以用一个点对 $(v,w)$ 表示，其中$v,w \in V$。
如果点对顺序无关，即$(v,w)$和$(w,v)$是同一条边，那么此图就被称为无向图；反之如果点对有序，相当于边有箭头指向，那么此图就被称为有向图。
一、图的表示法
以一个无向图为例，展示三种图的表示法
1.1 邻接矩阵
1
2
3
4
5
| [[0, 1, 1, 1, 1],
[1, 0, Inf, Inf, Inf],
[1, Inf, 0, Inf, Inf],
[1, Inf, Inf, 0, Inf],
[1, Inf, Inf, Inf, 0]]
|
上面矩阵数值为0表示同一个点，为1表示有边相连（边长默认1），Inf（一个很大的数）表示不可达
1.2 邻接表
使用链表记录相邻点集合
1
2
3
4
5
| 0: [1, 2, 3, 4]
1: [0]
2: [0]
3: [0]
4: [0]
|
1.3 边集
将图中4条边记录下来：
1
| [(0,1), (0,2), (0,3), (0,4)]
|
二、最短路问题
在一个连通图中, 如何求解从一个节点到另一个节点的最短路径, 称为最短路问题。
Dijkstra 算法是解决单源最短路问题的经典算法，适用于边长为非负值的大多数情况。
Dijkstra 算法与优先队列
第一步：使用一个数组dist储存从原点到该点的最短距离, 原点初始化为0, 其余全部初始化为不可达；另用一个数组used标记某点是否已访问。目标点point和原点到其最短距离dist[point]作为一个 pair 加入优先队列, 优先队列按照最短距离的大小逆序排列.
第二步：若优先队列为空，则退出循环；否则从优先队列中取出一条最短边，遍历最短边对应目标点的所有相邻节点（故使用Dijkstra算法时宜采用临接表形式来表示图），
若通过目标点到达其相邻节点的路径比原路径更短, 则更新dist路径.
第三步：选出used数组中标记的未访问的节点中dist最小的节点next，将pair<next, dist[next]>加入优先队列。返回第二步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int dist[maxn];
typedef pair<int, int> P;
void dijkstra(int source) {
priority_queue<P, vector<P>, greater<P> > pq;
memset(dist, 0xff, sizeof dist);
dist[source] = 0;
qp.push(0, source);
while(!pq.empty()) {
P pair = pq.top(); pq.pop();
int shortest = p.first, point = pair.second;
if (shortest > dist[point]) continue;
for(auto &e : graph[point]) {
int next = e.second, dist_update = dist[point] + e.first;
if(dist_update < dist[next]) {
dist[next] = dist_update;
pq.push(dist_update, next);
}
}
}
}
|
priority_queue
C++ 中的优先队列是一个容器, 插入时为对数时间的复杂度, 读取最大值或最小值为常数时间的复杂度.
使用 STL 中的 std::priority_queue 需要包含头文件 queue.
默认是从大到小排序, 也可以通过指定 greater<T> 参数进行从小到大排序. 如果自定义比较方法的一定要注意, 这里需要定义一个比较 type 而不是比较函数. 在用于比较的类型(struct或class)中重写 operator() 而不是 operator<.
1
2
3
4
5
6
7
8
9
10
11
12
| class Cmp{
public:
bool operator() (const Tri& t1, const Tri& t2) const{
if(t1.time == t2.time){
if(t1.send == t2.send){
return t1.receive < t2.receive;
}
else return t1.send < t2.send;
}
return t1.time < t2.time;
}
};
|
一些特殊案例
注意有些情况下，比如存在多个source和target值的情况，Dijkstra需要都加入：
如果下面这题使用图的最短路算法
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
|
import java.util.*;
class Solution {
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
HashMap<Integer, Boolean> searched = new HashMap<>();
class Pair{
public int k;
public int v;
public Pair(int point, int dist) {
k = point;
v = dist;
}
}
PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new Comparator<Pair>(){
@Override
public int compare(Pair o1, Pair o2) {
return o1.v - o2.v;
}
});
public int numBusesToDestination(int[][] routes, int source, int target) {
for(int i=0; i<routes.length; ++i) {
ArrayList<Integer> ring = new ArrayList<Integer>(routes[i].length);
for(int j=0; j<routes[i].length; ++j) {
ring.add(routes[i][j]);
}
for(int j=0; j<routes[i].length; ++j) {
if(graph.get(routes[i][j]) == null) {
graph.put(routes[i][j], new ArrayList<Integer>());
searched.put(routes[i][j], false);
}
ArrayList<Integer> neighbors = graph.get(routes[i][j]);
neighbors.addAll(ring);
neighbors.remove(neighbors.indexOf(routes[i][j]));
}
}
Pair pair = new Pair(source, 0);
searched.put(source, true);
pq.add(pair);
while(!pq.isEmpty()) {
Pair out = pq.poll();
searched.put(out.k, true);
if(out.k == target) {
return out.v;
}
ArrayList<Integer> neighbors = graph.get(out.k);
int dist = out.v;
for(int point : neighbors) if(!searched.get(point)) {
pq.add(new Pair(point, dist+1));
}
}
return -1;
}
}
|
上述解答会在这个用例超时：
1
2
3
| [[0,1,2, ..., 90000]]
0
900
|
判定是否连接的方法可以是将公交路线放在集合中，检查两个集合的交集是否为空；或者将公交路线中的车站进行递增排序，并使用双指针的方法检查是否有相同的车站。
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
import java.util.*;
class Solution {
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
HashMap<Integer, Boolean> searched = new HashMap<>();
class Pair{
public int k;
public int v;
public Pair(int point, int dist) {
k = point;
v = dist;
}
}
PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new Comparator<Pair>(){
@Override
public int compare(Pair o1, Pair o2) {
return o1.v - o2.v;
}
});
public int numBusesToDestination(int[][] routes, int source, int target) {
if(source == target) return 0;
for(int i=0; i<routes.length; ++i) {
graph.put(i, new ArrayList<Integer>());
searched.put(i, false);
}
for(int i=0; i<routes.length; ++i) {
for(int j=0; j<routes.length; ++j) {
if(intersect(routes[i], routes[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
}
}
for(int i=0; i<routes.length; ++i) {
if(Arrays.binarySearch(routes[i], source)>=0) {
Pair pair = new Pair(i, 0);
searched.put(i, true);
pq.add(pair);
}
}
int min = Integer.MAX_VALUE;
while(!pq.isEmpty()) {
Pair out = pq.poll();
searched.put(out.k, true);
if(Arrays.binarySearch(routes[out.k], target)>=0) {
min = Math.min(min, out.v+1);
}
ArrayList<Integer> neighbors = graph.get(out.k);
int dist = out.v;
for(int route : neighbors) if(!searched.get(route)) {
pq.add(new Pair(route, dist+1));
searched.put(route, true);
}
}
if(min == Integer.MAX_VALUE) return -1;
return min;
}
public boolean intersect(int[] A, int[] B) {
int i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] == B[j]) return true;
if (A[i] < B[j]) i++; else j++;
}
return false;
}
}
|
三、最小生成树 (minimal spanning tree)
在实际应用中, 我们经常会遇到求解最小生成树的问题，比如城市之间的通信管道铺设要求总长最短。
由于树可看作一种不形成环的无向连通图，对于一个带权无向连通图，最小生成树就是图中边的一个子集，该子集连接了图中的所有点，并且权值和最小。
Kruskal 算法与并查集
该算法的目的是找出一个图中的最小生成树。具体做法如下：
- 初始化最小生成树的边的集合S。将所有的边按照升序排列，依次取出长度最小的边。
- 判断取出边所连接的两点是否连通，如果已经连通，说明这两点已经构成了最小生成树，则不做处理；若未连通，则将两点通过并查集连接，并将这个边加入集合S中；
- 当遍历完所有边后，返回集合S，即为最小生成树的边的集合
1
2
3
4
5
6
7
8
9
10
11
12
|
List<Integer> kruskal(int[][] edges) {
Arrays.sort(edges, comparator);
List<Integer> MST = new ArrayList<>();
for(int[] edge : edges) {
if(findPar(edge[1]) != findPar(edge[2])) {
union(edge[1], edge[2]);
MST.add(edge[0]);
}
}
return MST;
}
|
并查集 (union-find set)
并查集是一种特殊的树状结构, 用每一棵树来表示一个集合. 使用路径压缩方法将树压缩为两层, 因此查找效率非常高. 假如分类用整型连续标记, 查找函数可以写成下面这样:
1
2
3
4
5
6
7
8
9
10
| int par[maxn];
int findPar(int x){
if (par[x] == x) return x;
return par[x] = findPar(par[x]);
}
void init(int n){
for(int i=0; i<n; ++i) par[i] = i;
}
|
在使用的时候, 进行合并操作:
1
2
3
| scanf("%d%d", &a, &b);
int x = par[a], y = par[b];
if (x != y) par[x] = y;
|
并查集提高了查找的速度，但是也有其局限性。比如并查集判断图中是否有连通环，只能针对一个图下。来看 LeetCode[785] Is Graph Bipartite，这道题就不能用并查集做，因为两个不连通有环图图和一个单线的无环图，他们的并查集结果都是2,无法区分。
所以这道题要检查图中是否存在环，只能使用深度优先搜索：
1
2
3
4
5
6
7
8
9
10
11
12
13
| boolean isCycle(int course) {
if(localMarked[course]) return true;
if(globalMarked[course]) return false;
globalMarked[course] = true;
localMarked[course] = true;
if(graph[course]!=null)for(int pre : graph[course]) {
if(isCycle(pre)) {
return false;
}
}
localMarked[course] = false;
return false;
}
|
例题：LeetCode 1489：找到最小生成树里的关键边和伪关键边
先找关键边，再找伪关键边，剩下的都是非关键边。
关键边是所有最小生成树边集合的交集，如果被去掉了，则最小生成树的权值和会增加。
伪关键边是所有最小生成树边集合-关键边集合的结果。判断伪关键边的方法是：
- 如果此边是关键边，则其不是伪关键边；
- 否则，如果提前将关键边的两点连通，之后计算出的最小生成树权值如不变，则说明是伪关键边，若变化（增大），则说明是非关键边。
四、深度优先搜索与广度有限搜索
五、拓扑排序
4.1 拓扑排序判断是否有环
使用拓扑排序可以判断有向图和无向图中是否有环。
判断有向图是否有环的步骤：
Step 1：求出图中所有结点的入度
Step 2：将所有入度=0的结点入队
Step 3：当队列不为空时，不断弹出队首元素。将队首元素指向的相邻节点的入度-1（相当于从图中去掉这个结点和它的所有出度），当相邻节点的入度减至0时，将该相邻结点入队。
Step 4：循环结束时判断已经访问的结点数是否等于n。如果等于则说明所有结点都被去掉了，图中不存在环;反之，说明存在环。
判断无向图是否有环的步骤：
Step 1：求出图中所有节点的度
Step 2：将所有度<=1的结点入队（独立结点的度为0）
Step 3：当队列不为空时，弹出队首元素。将与队首元素相邻节点的度-1（相当于从图中去掉这个结点和它的相邻边），如果相邻节点的度变为1,则将相邻结点入队。
Step 4：循环结束时判断已经访问的结点数是否等于n。如果等于则说明所有结点都被去掉了，图中不存在环；反之，说明存在环。
例题： LC 207 课程表
4.2 拓扑排序的遍历顺序
拓扑排序的遍历顺序不止一种，所以返回其中一个即可。使用bfs算法进行遍历，返回存储在数组中的访问路径。
Comments
shortnamefor Disqus. Please set it in_config.yml.