day58 第十一章：图论part08

news/2025/2/24 11:30:35

拓扑排序精讲

关键：

先找到入度为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才能有t
        cin >> 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的指向的文件入度-1
                if(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.更新minDist
        for(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;
    }
    
    
}