学习《introduction to algorithm》图论部分所做的笔记，包括里面算法的C++代码实现。
1. 拓扑排序(Topological sort)
如果你现在有很多任务需要去做，这些任务之间存在依赖关系，比如如果要完成任务B就必须先完成任务A，以这些作为节点，他们之前的依赖关系作为边可以形成一个图。要确定这些任务的完成顺序就是需要将这个图压缩到一维的时间轴上去。这就是拓扑需要解决的问题了
拓扑排序一般对每个节点进行深度优先搜索，按照搜索完成的时间进行排序就是最后拓扑排序的结果，需要注意的是在搜索的需要检测图中是否存在环形，如果存在环形是无法进行拓扑排序的，当使用深度搜索遍历到节点i时可以先用一个discover标记节点i已经被发现了，如果在该条支路的DFS中又遇到了节点i则出现了环形，如果没有遇到则可以将节点i设置为finish状态。
210. Course Schedule II 这个是Leetcode上面的一道关于拓扑排序的题，是关于一个选课的题目
There are a total of
numCoursescourses you have to take, labeled from0tonumCourses - 1. You are given an arrayprerequisiteswhereprerequisites[i] = [ai, bi]indicates that you must take coursebifirst if you want to take courseai.
- For example, the pair
[0, 1], indicates that to take course0you have to first take course1.Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].Example 3:
Input: numCourses = 1, prerequisites = [] Output: [0]Constraints:
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi- All the pairs
[ai, bi]are distinct.
class Solution {
private:
vector<int>visited; // 标记已经访问过的节点
vector<int>ret; // 用于返回的选课顺序
vector<vector<int>>q; // 用过邻接表来表示图
bool valide = true; // 标记是否形成环
const int initial = 0; // 初始状态
const int discover = 1; // 被发现
const int finish = 2; // 已经完成
// 深度搜索函数
void dfs(int n){
visited[n] = discover; // 标记当前节点已经被发现(discover)
for(const int i:q[n]){ // 遍历与当前节点相连的节点
if(visited[i] == discover){ // 如果存在环
valide = false;
return;
}
if(visited[i] == initial){ // 如果没有完成访问
dfs(i);
if(!valide){
return;
}
}
}
visited[n] = finish; // 标记当前节点已经完成(finish)
ret.push_back(n); // 按照完成的顺序添加即是拓扑排序的结果
}
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
if(numCourses == 1){ // 如果只有一门课程直接返回即可
return vector<int>{0};
}
visited.resize(numCourses);
q.resize(numCourses);
for(const auto i:prerequisites){ // 通过邻接表形成图
q[i[0]].push_back(i[1]);
}
// 对每一个元素进行DFS
for(int i=0; i<numCourses && valide; i++){
if(!visited[i]){ // 如果没有访问过
dfs(i);
}
}
if(!valide){ // 如果存在环，返回空数组
return vector<int>{};
}
return ret;
}
};2. 最小传播树(Minimum Spanning Tree)
将图中的所以节点连接起来使距离和最小，如果要取最小距离则一定不存在环，符合树的定义，所以称为最小传播树(Minimum Spanning Tree)，用数学公式可以表示为 \[ w(T) = \sum_{(w,v)\in T}w(u,v) \]
2.1 kruskal’s algorithm
对于有权无向图，Kruskal算法采用的是贪婪算法策略，首先将边根据其权重进行排序，后来按照从小到大的顺序迭代，不构成环则添加到目标树中，如果构成环则舍弃，继续下一条边
下面是该算法的C++代码实现
class MST_Kruskal{
private:
Graph graph;
int n; // 图中节点个数
// 需要用到的排序函数
static inline bool sortFunction(vector<int>& l, vector<int>& r){
return l[2] < r[2]; // 返回true的就会放在前面
}
public:
int pathLength = 0; // 最小传播树的路径和
vector<pair<int, int>>ans; // 运行结果
MST_Kruskal(Graph& graph, int n):graph(graph), n(n){}
void run(){
auto edges = graph.getAllEdges();
sort(edges.begin(), edges.end(), sortFunction); // 首先按照权重从小到大继续排序
DisjointSet disJointSet = DisjointSet(n);
for(const auto& i:edges){
int a = i[0], b = i[1], d = i[2];
// 如果两个节点不在同一颗树中
if(disJointSet.findSet(a) != disJointSet.findSet(b)){
pathLength += d;
ans.emplace_back(a, b);
disJointSet.unionSets(a, b); // 将两棵树合并成一棵树
}
}
}
};在算法的具体实现中使用到了Disjoint Set来判断添加一条新的边是否会构成环, 首先将每一个顶点初始化成一个单独的集合，然后按照权重从小到大的顺序迭代每一条边，如果边的两个顶点不在同一个集合中则说明不会形成环，将两个顶点所在的集合合并。
2.2 Prim’s algorithm
Prim算法同Kruskal一样都是采用贪婪策略，不过Kruskal从一条边到另一条边，而Prim算法是从一个点到另一个点，首先随便选取一个出发点（一般就选择index等于0的那个点）然后将与这个点相邻的边加入到以边的权重为基准的优先队列中，取出权重最小的那个边并将该条边弹出有限队列，如果那个边已经访问过就再从优先队列对取出另一条最小权重边，继续上面的过程，如果没有访问过就以那条边所对应的另一个点作为出发点重复上述过程，直到所以点都完成访问。
class Compare{
public:
bool operator() (Edge& a, Edge& b){
return a.weight > b.weight;
}
};
class MST_Prim{
private:
Graph graph;
public:
int pathLength = 0; // 最小传播树的路径和
vector<pair<int, int>>ans; // 运行结果
MST_Prim(Graph& graph):graph(graph){}
void run(){
// 边的优先队列(index, weight, parent)
priority_queue<Edge, vector<Edge>, Compare>q;
unordered_set<int>visted; // 用于存储已经访问过了的节点
q.push(Edge{0, 0, 0}); // 插入初始节点
while(!q.empty() && visted.size() != graph.size){
auto edge = q.top();q.pop();
if(visted.count(edge.next)){continue;} // 防止重复访问
visted.insert(edge.next); // 将当前节点标记为已访问
ans.emplace_back(edge.previous, edge.next); // 保存路径
pathLength += edge.weight; // 计算最短路径
for(auto i:graph.getAdjacent(edge.next)){ // 遍历相邻节点
int adjIndex = i.first;
int adjWeight = i.second;
if(!visted.count(adjIndex)){ // 如果没有访问过接添加到优先队列中
Edge temp;
temp.weight = adjWeight;
temp.previous = edge.next;
temp.next = adjIndex;
q.push(temp);
}
}
}
}
};3. 单源最短路径(Sigle Shortest path)
最短路径问题算是图论中的经典问题了，它在很多领域都有使用，比如路由器中的数据包转发就用到了最短路径算法。单源最短路是最短路径中最基础的一种，给定一个出发点和一个终点要求所经过的路径最短。一般有两种算法可以高效的解决这类问题一个是Bellman-Ford算法，另一个就是更为知名的Dijkstra算法。
3.1 Bellman-Ford algorithm
Bellman-Ford算法有点像广度优先搜索，首先初始化一个数组里面每个元素表示对应的节点，长度为图的所有节点数n，每个节点包含两个属性分别是weight表示与source节点的距离，parentIndex表示它的parent节点的坐标，所以将除了source节点之外的全部节点初始化为weight无限远，parentIndex就是它自己的index。然后将sourceIndex加入队列，开始遍历与之相连的节点，比较两者的距离信息，如果小于更新node信息，如果一个节点的node信息被更新了就将该节点加入队列继续遍历，直到队列为空。
struct node {
int parentIndex; // parent的Index
int weight; // 与source的距离
};
// BellmanFord最短路径算法
class BellmanFord{
private:
// (parent, distance)
vector<node>parent;
int INFINT = 1e5; // 表示无穷大
int sourceIndex, targetIndex, size;
vector<int>path;
Graph graph;
public:
//
BellmanFord(Graph& graph, int sourceIndex, int targetIndex)
: graph(graph), sourceIndex(sourceIndex), targetIndex(targetIndex)
{
for(int i = 0; i < graph.size; i++){
parent.push_back(node{i, INFINT});
}
parent[sourceIndex].parentIndex = sourceIndex;
parent[sourceIndex].weight = 0;
};
int run(){
queue<int>q; // 创建一个队列
q.push(sourceIndex);
while(!q.empty()){ // 形成最短路径
int sz = q.size();
for(int i = 0; i < sz; i++){
int currentIndex = q.front();q.pop(); // 取出添加的元素
for(const auto j:graph.getAdjacent(currentIndex)){
int jIndex = j.first, jWeight = j.second;
if(parent[jIndex].weight > parent[currentIndex].weight + jWeight ){
parent[jIndex].weight = parent[currentIndex].weight + jWeight;
parent[jIndex].parentIndex = currentIndex;
q.push(jIndex);
}
}
}
}
// 整理最短路径并输出
path.push_back(targetIndex);
int tempIndex = parent[targetIndex].parentIndex;
while(tempIndex != sourceIndex){
path.insert(path.begin(), tempIndex);
tempIndex = parent[tempIndex].parentIndex;
}
return parent[targetIndex].weight;
}
};3.2 Dijkstra algorithm
Dijkstra算法和Bellman-Ford算法类似，但是Bellman-Ford算法是将相邻的节点一起添加的队列中，迭代队列中的节点，并重复这个过程，Dijkstra则是将相邻的点添加的一个优先队列中，依次从优先队列从抽取weight最小的点并对相邻的节点更新
struct Node {
int index; // parent的Index
int weight; // 与source的距离
};
class Compare{
public:
bool operator() (Node& a, Node& b){
return a.weight > b.weight;
}
};
// Dijkstra最短路径算法
class Dijkstra{
private:
// 用于记录parent的index与当前节点的weight(当前节点的index由下标确定)
vector<Node>parent;
int INFINT = 1e5; // 表示无穷大
int sourceIndex, targetIndex, size;
vector<int>path;
Graph graph;
public:
//
Dijkstra(Graph& graph, int sourceIndex, int targetIndex)
: graph(graph), sourceIndex(sourceIndex), targetIndex(targetIndex)
{
for(int i = 0; i < graph.size; i++){
parent.push_back(Node{i, INFINT});
}
parent[sourceIndex].index = sourceIndex;
parent[sourceIndex].weight = 0;
};
int run(){
// 因为没办法更新优先队列里面的元素所以只能标记以访问元素，避免重复访问
unordered_set<int>visited;
priority_queue<Node, vector<Node>, Compare>q;
q.push(Node{sourceIndex, 0}); // 记录当前节点index与当前节点weight
while(!q.empty()){
auto currentNode = q.top(); q.pop();
if(visited.count(currentNode.index)){continue;} // 防止重复访问
visited.insert(currentNode.index); // 标记为已经访问
for(const auto j:graph.getAdjacent(currentNode.index)){
int jIndex = j.first, jWeight = j.second;
if(
!visited.count(jIndex) &&
parent[jIndex].weight > parent[currentNode.index].weight + jWeight
){
Node tempNode;
tempNode.index = jIndex;
tempNode.weight = parent[currentNode.index].weight + jWeight;
parent[jIndex].weight = parent[currentNode.index].weight + jWeight;
q.push(tempNode);
}
}
}
return parent[targetIndex].weight;
}
};