-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathoperation-sort-graph.go
110 lines (85 loc) · 3.16 KB
/
operation-sort-graph.go
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package algorithms_go
/**
深度优先搜索
深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
时间复杂度：O(|V| + |E|)
*/
/**
广度优先搜索
广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法
时间复杂度：O(|V| + |E|)
*/
/**
拓扑排序
拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v的边，u 的下标先于 v
时间复杂度：O(|V| + |E|)
*/
/**
Dijkstra算法
迪杰斯特拉算法是目前公认的较好的最短路径算法。
Dijkstra 算法是一种在有向图中查找单源最短路径的算法
时间复杂度：O(|V|^2)
*/
/**
Bellman-Ford算法
Bellman-Ford 是一种在带权图中查找单一源点到其他节点最短路径的算法
虽然时间复杂度大于 Dijkstra 算法，但它可以处理包含了负值边的
时间复杂度：
最优：O(|E|)
最差：O(|V||E|)
*/
/**
Floyd-Warshall算法
Floyd-Warshall 算法是一种在无环带权图中寻找任意节点间最短路径的算法。
该算法执行一次即可找到所有节点间的最短路径（路径权重和）。
时间复杂度：
最优：O(|V|^3)
最差：O(|V|^3)
平均：O(|V|^3)
*/
/**
最小生成树算法
最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之，最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
时间复杂度：O(|V|^2)
*/
/**
Kruskal算法
Kruskal 算法也是一个计算最小生成树的贪心算法，但在 Kruskal 算法中，图不一定是连通的。
时间复杂度：O(|E|log|V|)
*/
/**
贪心算法
贪心算法总是做出在当前看来最优的选择，并希望最后整体也是最优的。
使用贪心算法可以解决的问题必须具有如下两种特性：
最优子结构
问题的最优解包含其子问题的最优解。
贪心选择
每一步的贪心选择可以得到问题的整体最优解。
实例-硬币选择问题
给定期望的硬币总和为 V 分，以及 n 种硬币，即类型是 i 的硬币共有coinValue[i] 分，i的范围是 [0...n – 1]。假设每种类型的硬币都有无限个，求解为使和为 V 分最少需要多少硬币？
硬币：便士（1美分），镍（5美分），一⻆（10美分），四分之一（25美分）。
假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币，然后从 V 中减掉该硬币的值，如此重复进行。
V = 41 | 使用了0个硬币
V = 16 | 使用了1个硬币(41 – 25 = 16)
V = 6 | 使用了2个硬币(16 – 10 = 6)
V = 1 | 使用了3个硬币(6 – 5 = 1)
V = 0 | 使用了4个硬币(1 – 1 = 0)
*/
/*
位运算
位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
测试第 k 位：s & (1 << k);
设置第k位：s |= (1 << k);
关闭第k位：s &= ~(1 << k);
切换第k位：s ^= (1 << k);
乘以2n：s << n;
除以2n：s >> n;
交集：s & t;
并集：s | t;
减法：s & ~t;
提取最小非0位：s & (-s);
提取最小0位：~s & (s + 1);
交换值：x ^= y; y ^= x; x ^= y
*/
//
//运行时分析