拓扑排序

节点的度

度：与节点相连的边的条数
入度：有向图中，指向当前节点的边的条数
出度：有向图中，从当前节点发出的边的条数

AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先级，这样的有向图为顶点表示活动的网，称为AOV(Activity On Vertex Network)网

定义

将一个有向无环图G的所有顶点排成一个线性序列，使得有向无环图G的边集中的任意一条边<u,v>，始终满足u出现在v的前面

构造

在有向无环图中找到一个没有前驱（入度为0）的节点入栈
将栈顶节点出栈，然后从图中将此节点删除，并删除以该节点为尾的弧
重复操作
如果所有节点都已经输出，则结束，否则重复1

实现(邻接矩阵)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1000;
const int mod = 1e9 + 7;
int g[N][N], indgr[N], res[N];
void topsort(int n){
  int k =0;
  for (int i =1;i<=n;i++){
    for (int j = 1;j<=n;j++){ // 寻找入度为0的点
      if(!indgr[j]){
        res[i]=j; // 记录已经处理的点
        indgr[j]--; // 删除入读为0的点
        k=j;
        break;
      }
    }
    for (int j = 1;j<=n;j++){
      if (g[k][j]==1){
        g[k][j]=0; // 删除对应边 可省略，因为拓扑排序只看入度
        indgr[j]--; // 入读-1
      }
    }
  }
}
void solve() {
  // 视频中第一个例题
  int n, m;
  while(~scanf("%d %d", &n, &m)){
    int x, y;
    memset(indgr, 0, sizeof indgr);
    memset(g, 0, sizeof g);
    for (int i = 1;i<=m;i++){
      scanf("%d %d",&x,&y);
      if (!g[x][y]) {
        g[x][y]=1;
        indgr[y]++;
      }
      topsort(n);
      for (int i = 1;i<=n;i++){
        if (i<n) printf("%d ", res[i]);
        else printf("%d\n", res[i]);
      }
    }
  }
 
}
int main()
{
  //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

注意：

编号大的节点优先输出：寻找入度0的点时倒序遍历
如何判断有环：不存在入度为0的点

实现(邻接表)

对于稀疏图，使用邻接矩阵会浪费大量空间，我们可以使用邻接表

#include <bits/stdc++.h>
using namespace std;

// 邻接表节点结构
struct node{
    int x; // 节点编号
    int w; // 权值
    node* next;
    node(int x_, int w_){
        this->x = x_;
        this->w = w_;
        next = nullptr;
    }
};

vector<node*> head;      // 邻接表头节点数组
vector<int> in_degree;   // 记录每个节点的入度

// 添加有向边
void add_edge(int u, int v, int w){
    node* a = head[u];
    node* b = new node(v,w);
    b->next = a->next;
    a->next = b;
    in_degree[v]++;      // 目标节点入度加1
}	

// 拓扑排序
vector<int> topological_sort(int n) {
    vector<int> result;          // 存储拓扑序列结果
    queue<int> q;               // 存储入度为0的节点
    
    // 将所有入度为0的节点入队
    for(int i = 1; i <= n; i++) {
        if(in_degree[i] == 0) {
            q.push(i);
        }
    }
    
    // 不断取出入度为0的节点，更新其邻接点的入度
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        result.push_back(cur);   // 将当前节点加入结果序列
        
        // 遍历当前节点的所有邻接点
        node* p = head[cur]->next;
        while(p) {
            in_degree[p->x]--;   // 将邻接点的入度减1
            // 如果入度减为0，则入队
            if(in_degree[p->x] == 0) {
                q.push(p->x);
            }
            p = p->next;
        }
    }
    return result;
}

int main(){
    int n, m;
    cin >> n >> m;              // 输入节点数和边数
    
    // 初始化
    head.resize(n+1);
    in_degree.resize(n+1, 0);
    for(int i = 0; i <= n; i++){
        head[i] = new node(i,0);
    }
    
    // 输入边的信息
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
    }
    
    // 执行拓扑排序
    vector<int> topo = topological_sort(n);
    
    // 判断是否存在环并输出结果
    if(topo.size() < n) {
        cout << "图中存在环，无法进行拓扑排序" << endl;
    } else {
        for(int x : topo) {
            cout << x << " ";
        }
        cout << endl;
    }
    
    return 0;
}

关键路径

AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动持续时间，这种有向图的边表示活动的网，称为AOE（Activity On Edge Network）网

ETV与LTV

ETV：表示事件最早发生的时间(earliest time of vertex)

注意：考虑到多线程操作，事件最早发生时间应该是多个同步事件完成时间的最大值

LTV：表示事件最晚发生的时间(latest time of vertex)

注意：同理，事件最晚发生时间应该是减去多个同步事件完成时间后的最小值

红魔咖啡馆

【图论】拓扑排序