一、图论问题 Ⅵ

1、拓扑排序–软件构建

拓扑排序是将一个有向图转成线性的排序，需要判断有向图中是否存在环。这个比较经典的问题就是leetcode里207 课程表。和这题异曲同工。
思路就是：记录每个节点的入度，以及当前节点的下一个节点。优先选出入度为0的节点，因为入度为0表示不需要前置依赖（或者前置依赖已满足）。入度为0的节点进入队列，再出队列，消除对下一个节点的影响，也就是将下一个节点的入度减1，若产生新的入度为0的节点，则加入队列。

# include<iostream>
# include<vector>
# include<queue>using namespace std;int main(){int n, m; // n个文件  m条依赖关系cin >> n >> m;vector<int> indegree(n);vector<vector<int>> neighbor(n);int s, t;for(int i=0; i<m; ++i){cin >> s >> t;indegree[t]++;neighbor[s].push_back(t);}// 入度为0的进队列queue<int> q;for(int i=0; i<n; ++i){if(indegree[i]==0)q.push(i);}vector<int> ans;while(!q.empty()){int pre = q.front(); q.pop();ans.push_back(pre);for(auto cur : neighbor[pre]){indegree[cur]--;if(indegree[cur]==0)q.push(cur);}}if(ans.size()==n){for(int i=0; i<n-1; ++i)cout << ans[i] << " ";cout << ans[n-1] << endl;}else{cout << -1 << endl;}return 0;
}

2、dijkstra算法

dijkstra算法是经典的最短路算法，其算法主要流程是 1、选取源点到未被访问过且距离最近的节点； 2、将最近节点标记为访问过 3、更新非访问节点到源点的距离。可以发现，dijkstra算法与prim算法在算法流程上非常像。
在代码实现上，我们需要使用一个数组来记录每一个节点距离源点的最近距离。

# include<iostream>
# include<vector>
# include<climits>using namespace std;int main(){int n, m;cin >> n >> m;int s, e, v;vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));for(int i=0; i<m; ++i){cin >> s >> e >> v;grid[s][e] = v;}vector<int> minDist(n+1, INT_MAX);vector<bool> visited(n+1, false);int start = 1, end = n;minDist[start] = 0;for(int i=1; i<=n; ++i){int cur = 1, minVal = INT_MAX;// 1、选取源点到未被访问过且距离最近的节点； for(int v=1; v<=n; ++v){if(!visited[v] && minDist[v] < minVal){minVal = minDist[v];cur = v;}}// 2、将最近节点标记为访问过 visited[cur] = true;// 3、更新非访问节点到源点的距离for(int v=1; v<=n; ++v){if(!visited[v] && grid[cur][v] < INT_MAX && grid[cur][v] + minDist[cur] < minDist[v])minDist[v] = grid[cur][v] + minDist[cur];}}if(minDist[end] < INT_MAX)cout << minDist[end] << endl;elsecout << -1 << endl;return 0;
}