day58 第十一章：图论part08

拓扑排序精讲

关键：

先找到入度为0的节点，把这些节点加入队列/结果，然后依次循环再找。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系vector<int> result; // 记录结果while (m--) {// s->t，先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件，可以作为开头，先加入队列if (inDegree[i] == 0) que.push(i);//cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int  cur = que.front(); // 当前选中的文件que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;}

dijkstra（朴素版）精讲

不能处理负权重，贪心算法，minDist表示距离原点最近的距离。

跟prim一样

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main(){int n,m,s,e,v;cin>>n>>m;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<bool> visited(n+1, false);vector<int> minDist(n+1, INT_MAX);int start = 1;minDist[start] = 0;for(int i=0;i<n;i++){int cur = -1;int minVal = INT_MAX;//1.选择未到过的且距离起始点最近车站for(int j=1;j<=n;j++){if(!visited[j] && minDist[j]<minVal){cur = j;minVal = minDist[j];}}if(cur == -1) {break;}//2.到达该车站visited[cur] = true;//3.更新minDistfor(int j=1;j<=n;j++){if(!visited[j] && grid[cur][j]!=INT_MAX && minDist[cur]+grid[cur][j]<minDist[j]){minDist[j] = minDist[cur]+grid[cur][j];}}// cout<<"cur="<<cur<<endl;// for(int k=1;k<=n;k++){//     cout<<minDist[k]<<" ";// }// cout<<endl;}int count = 0;for(int i=1;i<=n;i++){if(visited[i]){count++;}}if(count==n){cout<<minDist[n]<<endl;}else{cout<<-1<<endl;}}