图的应用

图的遍历

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
第一行输入n m代表结点个数和边的个数
下面m行分别输入a b x代表ab之间有权值为x的路径
*/

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 100; 
int mp[maxn][maxn];//二维数组表示邻接矩阵
int vis[maxn];

// 初始化
void init()
{
    for(int i = 0;i<maxn;i++)
    {
        vis[i] = 0;
    }
}
// 利用邻接矩阵存储无向图

// 访问当前结点为x 深度遍历
void dfs(int x)
{
    cout << x << " ";
    vis[x] = 1;// 代表已经访问
    for(int i = 0;i<n;i++)
    {
        // 这里需要注意的是这个i和x的关系 别写错了是<x,i>
        if(mp[x][i]!=0 && vis[i]==0) // 存在路径 且未访问
        {
            dfs(i);// 然后深度遍历该结点的邻居
        }
    }
}

// 根据这个结点进行广度搜索
// 再次基础上 可以具体算出来和源点的距离
// 也可每次pop队列中的所有元素 这样就可以求出每一层的具体结点数
void bfs(int root)
{
    init();
    queue<int>q;
    q.push(root);
    vis[root] = 1;
    int d[maxn];//代表和源点的距离
    d[root] = 0;//自身和自身距离为0
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        cout << front <<" " << d[front] <<"\n";
        for(int i = 0;i<maxn;i++)
        {
            if(mp[front][i] != 0 && vis[i] == 0)// 当前结点存在通路 且未访问
            {
                q.push(i);
                d[i] = d[front] + 1;//比他的发源地多一个距离
                vis[i] = 1;
            }
        }
    }
}

int main()
{
    cin >> n >> m;//代表点的个数和边的个数
    for(int i = 0;i<m;i++)
    {
        int a,b,x;
        cin >> a >> b >> x;
        mp[a][b] = x;
        mp[b][a] = x;
    }
    init();
    dfs(0);
    bfs(0);
    return 0;
}
/*
6 8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1 
3 2 2
3 4 3
4 5 3
*/

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
第一行输入n m代表结点个数和边的个数
下面m行分别输入a b x代表ab之间有权值为x的路径
*/

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int inf = 0x3fffffff;
const int maxn = 100; 
int vis[maxn];
/*
利用邻接表来建立图 从而实现Bell-Ford

*/
struct Node{
    int id;
    int val;// 因为这里虽然是一个结点 但是是头节点指向该结点 存在边权
    // 因为邻接表的实际含义是存储邻居的 故而彼此的弧也很好判断
    Node* next;
    Node(int _id,int _val) : id(_id),val(_val),next(NULL){}
};
Node *head[maxn];// 这里建立的是头节点顺序存储的 里面每一个对象是其邻居结点
// 而head[i]代表的是结点i的头指针 每次增加完元素 指针也会变化 

// 结点ab之间增加一个权值为x的边 作为无向图 应该是彼此的邻居
void add(int a,int b,int x)
{
    Node * p = new Node(b,x);
    p->next = head[a];//采用头插法 里面的顺序和插入的相同
    head[a] = p;
    
    Node *q = new Node(a,x);// 无向图 边是双向的
    q->next = head[b];
    head[b] = q;
}

// 根据邻接矩阵 深层遍历
void DFS(int v){
    
    cout << v;
    vis[v] = 1;
    // 遍历v的邻居
    Node *p = head[v];
    while(p!=NULL){
        int nw = p->id;
        if(vis[nw]==0){
            
            DFS(nw);
        }
        p = p->next;
    }
}

int main()
{
    cin >> n >> m;//代表点的个数和边的个数
    for(int i = 0;i<m;i++)
    {
        int a,b,x;
        cin >> a >> b >> x;
        add(a,b,x);
    }
    DFS(0);
    return 0;
}
/*
6 8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1 
3 2 2
3 4 3
4 5 3
*/

计算强连通分量的个数

Kosaraju算法步骤：

  • 第一步：对原图 G 进行深度优先搜索（DFS），并记录节点的完成时间（即每个节点访问结束的时间）。
  • 第二步：构造图 G 的转置 ，即将所有边的方向反转。
  • 第三步：按照第一步中记录的完成时间从大到小的顺序，对 进行DFS，每次DFS生成的一棵树就是一个强连通分量。

最小生成树

prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
这里和Dij的区别为d[u]代表着两个集合之间的最小值
因此每次在选好一个u时 需要更新d[u]的值 这也就是和dij不同的一点
这里vis是否访问 可以认为是否置于S集合中
*/
int prim(int root){
   
    fill(d,d+maxn,inf);
    d[root] = 0;//自身到自身为0
    int ans = 0;// 存放最小的边权之和 返回的结果
    for(int i = 0;i<n;i++)
    {
        //每次循环在里面找到最小的一个u
        int u = -1;
        int mx = inf;
        for(int j = 0;j<maxn;j++)
        {
            // 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
            if(mx > d[j] && vis[j]==0)
            {
                mx = d[j];
                u = j;
            }
        }
        if(u == -1) return -1;//找不到最小 结束
        vis[u] = 1;//代表已经加入集合
        ans += d[u];
        cout << u <<" ";// 这是依次加入的结点
        //需要更新d的值 以u为中介看看是否可以更新距离
        // 实际上这里就是遍历u的邻居结点 这里是可以优化性能的地方 也可以进行二次比较
  
        for(int v = 0;v<n;v++)
        {
            // v未访问 u可以到v 以u为中介可以使u到达S更近
            // 因为是集合的概念 因此直接修改成mp[u][v]即可
            // 需要注意mp初始化必须其余元素为inf才可
            if(vis[v] == 0 && mp[u][v] != inf && mp[u][v] < d[v]) {
                d[v] = mp[u][v];
                // cout << d[v] <<" ";
            }
        }
    }
    return ans;
}

kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
kruskal 采用边贪心
1.将所有边权排序
2.按边权从小到大测试所有边,如果两个点不在一个连通块,就合并
3.直到边数等于总结点-1 合并完成
而对于边权的排序 则需要结构体排序
利用并查集来判断是否处于同一个连通块
*/
struct edge{
    int u,v;// 首尾结点
    int cost; //边权
}Edge[maxn];

// 根据权值小的排序
bool cmp(edge a,edge b){
    return a.cost < b.cost;
}

int fa[maxn];

// 找x的父亲 路径压缩
int Find(int x)
{
    if(x==fa[x]) return x;
    int t = Find(fa[x]);
    fa[x] = t;
    return t;
}

// 合并两个孩子
int Union(int a,int b)
{
    int Fa = Find(a);
    int Fb = Find(b);
    fa[Fa] = Fb;
}

int kruskal()
{
    sort(Edge,Edge+m,cmp);
    for(int i = 0;i<n;i++){
        fa[i] = i;
    }
    int ans = 0,num = 0;
    //遍历所有边
    for(int i = 0;i<m;i++)
    {
        edge temp = Edge[i];
        int u = temp.u;
        int v = temp.v;
        int cost = temp.cost;
        if(Find(u)!=Find(v)){
            Union(u,v);
            num ++;
            ans += cost;
        }
    }
    if(num != n-1) return -1;
    return ans;
}

最大生成树

顾名思义,生成的权值和要求最大的生成树,只需要在kruskal里面的cmp排序,按照权值大小进行降序即可.

加入一条新边,求最新的最小生成树

假设图G,已知最小生成树T,现在给定一条新加入G的边e,要求求出G+e新图的最小生成树算法.

思路:加入一条新的边,肯定会形成一个环,只需要在新的环中找到最长的一条边就可以,如果该环中存在比新边权值大的边,那新最小生成树的权值一定变小

次小生成树

思路:先求最小生成树,然后枚举图中未加入最小生成树的各边,转换成求解加入一条新边,求最新的最小生成树问题,然后在根据,是严格次小还是次小进行统计.

判断最小生成树是否唯一

原理:假如最小生成树不唯一,只有可能是存在权值相同且为最小的边连通两个集合.换句话说,只需要在kruskal里面判断,假如有两条边权值相同,且都可以将两个相同的连通块进行合并,那生成树一定不是唯一的.

什么样的边会影响到最小生成树的唯一性呢？

kruskal 求最小生成树 是将所有边权从小到大排序，然后判断当前边的两个端点所在连通块是否连通。如果没有连通，那么这条边就需要拿。 而此时如果有另外一条边，虽然也可以将这两个连通块合并，但是其权值比较大，那么这条边是不会影响到最小生成树的。 所以，只有两个边的权值相同，并且都能将端点的两个连通块合并，这么这两个边选择哪个都行，那么最小生成树就不唯一了。

最短路径

最短路径的求解依据的一个重要性质为:两个节点之间的一条最短路径包含着其他的最短路径,这是一个最优子结构问题,最优子结构可以使用动态规划和贪心政策.

最短路径的子路径也是最短路径,最短路径经过的路径都是节点间最短的路径

最后的最短路径也不能包含权值为正的的环路,因此可认为最后都是简单路径

Dijkstra

1
2
3
4
5
6
7
8
9
// 所有可到达顶点v都必须要未被访问 而且两者之间存在通路 这是一个大前提
for(int j = 0;j<n;j++)
{
    if(vis[v]==0 && mp[u][j] != 0  && dist[j] > dist[u]+mp[u][j])
    {
        dist[j] = dist[u] + mp[u][j];
        //源点到j的最短 更新成源点到u的最短距离 加上u到j的路径长度
    }
}

朴素邻接矩阵做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
解决单源无负权最短路问题
对图G(V,E)设置集合S,存放已经访问的结点
然后每次从集合V-S中选择与起点s的最短距离最小的结点u
访问并加入S
之后令u为中介点 优化起点s与所有可以通过u到达的v之间的距离
执行n次 直到可以包含所有顶点
主要的时间花在了外层循环n次 必须标记每个顶点以访问 无法优化
内层寻找最小的d[u]和优化最短距离 寻找最小的d[u]可以使用优先队列
为O(n*(n+n))
如果使用优先队列加上邻接表 时间复杂度可以实现O(VlogV + E)
*/
void Dij(int root){
    dist[root] = 0;//自身到自身为0
    
    for(int i = 0;i<n;i++)
    {
        //每次循环在里面找到最小的一个u
        int u = -1;
        int mx = inf;
        for(int j = 0;j<maxn;j++)
        {
            // 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
            if(mx > dist[j] && vis[j]==0)
            {
                mx = dist[j];
                u = j;
            }
        }
        if(u == -1) return;//找不到最小 结束
        vis[u] = 1;//代表已经访问
        
        //需要更新dist的值 以u为中介看看是否可以更新距离
        // 实际上这里就是遍历u的邻居结点 这里是可以优化性能的地方 也可以进行二次比较
        for(int j = 0;j<n;j++)
        {
            if(vis[v]==0 && mp[u][j] != 0  && dist[j] > dist[u]+mp[u][j])
            {
                dist[j] = dist[u] + mp[u][j];
                //源点到j的最短 更新成源点到u的最短距离 加上u到j的路径长度
            }
        }
    }
}

实现路径打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

int pre[maxn];
/*
pre[v]表示从源点s到v的最短路径上v的前一个顶点 即前驱的编号
每次优化d[v]变得更小的方案是让u作为从s到v的最短路径前一个结点
*/
void Dij(int root){
    dist[root] = 0;//自身到自身为0
    
    for(int i = 0;i<n;i++)
    {
        //每次循环在里面找到最小的一个u
        int u = -1;
        int mx = inf;
        for(int j = 0;j<maxn;j++)
        {
            // 这里需要判断这个结点是否访问过呢 肯定需要 不然一直选择起点
            if(mx > dist[j] && vis[j]==0)
            {
                mx = dist[j];
                u = j;
            }
        }
        if(u == -1) return;//找不到最小 结束
        vis[u] = 1;//代表已经访问
        
        //需要更新dist的值 以u为中介看看是否可以更新距离
        // 实际上这里就是遍历u的邻居结点
        for(int v = 0;v<n;v++)
        {
            if(mp[u][v] != 0  && dist[v] > dist[u]+mp[u][v])
            {
                dist[v] = dist[u] + mp[u][v];
                //源点到v的最短 更新成源点到u的最短距离 加上u到v的路径长度
                pre[v] = u;// 到达v的最短路径前一个为u
            }
        }
    }
}
/*
打印从s到v的路径 利用递归来寻找
pre[v]代表的是v的前驱结点
这个结构很有意思 因为对于图而言 具有一个子问题性质
就是假如a~b~c中a~c是最短路 则a~b也是最短路
因此实际上有很多最短路径都是在树的同一分支上 因此每次只需要从底层结点向上追溯即可
按道理来说 一个for循环也可以解决
*/

void printRoad(int s,int v)
{
    if(s==v) {
        cout << s <<" ";
        return;
    }
    printRoad(s,pre[v]);
    cout << v <<" ";
}

新增边权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
常见的操作还有三种 增加第二标准 进行排序选择
1. 给每个边在增加一个边权(比如花费)要求最短路径的基础上 花费最少
2.给每个点增加点权 最短路有多条的时候要求点权最大
3.最短路的路径条数
三种问题都只需要增加一个新的数组来存放新增的边权或点权或最短路径条数
然后只需要在Dij中修改优化d[v]的步骤即可
*/
int cost[maxn][maxn],c[maxn];// 某条边的第二权重 到达某点的总花费
/*
cost[u][v]代表u->v的边权花费
c[u]代表从起点s到顶点u的最小花费
初始化只有c[s]为0 其余皆为inf
*/
for(int v = 0;v<n;v++)
{
    if(mp[u][v] != 0  && vis[v]==0){
     	if(&& dist[v] > dist[u]+mp[u][v]){
            dist[v] = dist[u] + mp[u][v];
            c[v] = c[u] + cost[u][v];
        }else if(dist[v] == dist[u] + mp[u][v] && c[u] + cost[u][v] < c[v]){
            // 满足上述条件 才进行c的更新
            c[v] = c[u] + cost[u][v];
        }   
    }
}

新增点权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
新增点权 
用weight[u]代表结点u具有的点权
数组w[u]代表从起点到u可以收集最大的点权数
初始只有w[u]为weight[s] 其余皆为0
*/
int weight[maxn],w[maxn];
for(int v = 0;v<n;v++)
{
    if(mp[u][v] != 0  && vis[v]==0){
        if(dist[v] > dist[u]+mp[u][v]){
            dist[v] = dist[u] + mp[u][v];
            w[v] = w[u] + weight[v];// 到达了v 因此加上v的权值
        }else if(dist[v] == dist[u] + mp[u][v] && w[u] + weight[v] > w[v]){
            w[v] = w[u] + weight[v];
        }
    }
    
}

求最短路径条数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
求最短路径的条数
增加数组num[u] 从起点到u的最短路径条数
初始化num[s] = 1 其余都为0
当是不等关系 即dist[v] > dist[u]+mp[u][v] 更新num[v]的值
因为这个判断相当于 找到了更短的一个路径 所以理应里面的数据都变化
当dist[v] = dist[u]+mp[u][v] 意味着该中转是第二个最小路
num[v] += num[u] 在已有的基础不变的情况下 加入到达v的路径数
这个思路也能很好体现最优结构思想 只有在之前的状态都更新好了
再运用这些内容的时候 才不会影响后续运算
*/

int num[maxn];
for(int v = 0;v<n;v++)
{
    if(mp[u][v] != 0  && vis[v]==0){
        if(dist[v] > dist[u]+mp[u][v]){
            dist[v] = dist[u] + mp[u][v];
            num [v] = num[u];  //继承上一个结点的最短路径个数
        }else if(dist[v] == dist[u] + mp[u][v]){//同为最短路 原有基础上叠加次数
            num[v] += num[u];
        }
    }
    
}

尽管有上述的更新操作,但是其中是存在局限性的,假如求解的内容不满足最优子结构,就不可以使用上述修改思路,因此可以使用Dij+DFS

Dij+DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*基本思路为 先在Dij算法中记录下所有最短路径 只考虑距离 然后再这些所有的路径中选择出一个第二尺标最优的路径
主要作用在于当不满足子结构的前提或者标尺的数量过多 容易写混
需要注意的是里面的vector<int> pre[maxn];对于这个pre数组的递归
会形成一棵递归树 而遍历这棵递归树的方法就是DFS

*/
for(int v = 0;v<n;v++)
{
    if(mp[u][v] != 0 && vis[v]==0){
        if(dist[v] > dist[u]+mp[u][v])
        {
            dist[v] = dist[u] + mp[u][v];
            //源点到v的最短 更新成源点到u的最短距离 加上u到v的路径长度
            pre[v].clear();// 每次更新最短路都需要重置数组
            pre[v].push_back(u);// 到达v的最短路径前一个为u
        }else if(dist[v] == dist[u]+mp[u][v]){
            pre[v].push_back(u);//相等条件 添加路径
        }
    }
}



// 根据形成的pre数组 打印出所有路径 递归打印
int optValue;//第二尺度
int st = 0;// 路径起点 也是叶子节点
vector <int> path,temp;//最优路线和临时路线
void printRoad(int v)  //v为当前访问结点
{
    if(v==st){//递归边界 达到叶子结点 
        temp.push_back(st);
        
        // 这里存在一系列的比较和赋值 根据最终的比较来
        
        for(auto i : temp){
            cout << i <<" ";
        }
        temp.pop_back();
        return;
    }
    temp.push_back(v);
    for(int i = 0 ;i < pre[v].size();i++){
        printRoad(pre[v][i]); //递归其前驱节点
    }
    temp.pop_back();
}

Bell-Ford

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0;i<n-1;i++) //执行n-1轮操作 n为定点数
{
	for(each edge u->v){
        /*
        	在这里的松弛操作普遍有两种写法 当然两种结果都是正确的 侧重点不同
        	一种是d[v] = min(d[v],d[u]+length[u->v]) 
        	这种操作会频繁的干扰d数组,虽然最终结果是正确的,但是无法判断具体边的个数
        	另一种为d[v] = min(d[v],last[u]+length[u->v])
        	复制前一次操作的d数组
        	相比上面,他的优点在于,可以手动限制经过边的最大值,但是带来的牺牲就是时间会增加
        */
    	if(d[u] + length[u->v] < d[v]){ // 以u为中介点可以使d[v]减小
            d[v] = d[u] + length[u->v]; //松弛操作
        }  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
代码比较好写 但是思路并不是很简单
因为每层遍历实际上就会形成一层到达的结点 然后每次遍历一层结点都会进行松弛
(好牵强hhh)
*/

bool Ford(int s)// 表示源点
{
    fill(d,d+n,inf);
    d[s] = 0;//自身到自身的距离为0
    
    for(int i = 0;i<n-1;i++) //执行n-1轮 
    {
        for(int u = 0;u<n;u++)// 每轮遍历所有边(根据点来找所有边)
        {
            //找u的邻居
            Node *p = head[u];
            while(p!=NULL){
                int v = p->id;
                int dis = p->val;
                if(d[u] + dis < d[v]){ //以u作为中介到达v的距离更小
                    d[v] = dis + d[u];  // 松弛操作
                }
                p = p->next;
            }
        }
    }
    
    for(int u = 0;u<n;u++)// 每轮遍历所有边(根据点来找所有边)
    {
        //找u的邻居
        Node *p = head[u];
        while(p!=NULL){
            int v = p->id;
            int dis = p->val;
            if(d[u] + dis < d[v]){ //以u作为中介到达v的距离更小
                return false;// 如果还能松弛 说明存在负闭环
            }
            p = p->next;
        }
    }
    return true;
}

SPFA

SPFA是Bell-Ford的一个优化,优化的方面在,首先遍历n-1轮操作肯定变不了,在每次想要遍历所有边的时候,实际上是很浪费的,因为每次更新的只是d中的部分值,因此当只有某个顶点u的d[u]发生了改变,从他出发的边的邻接点v的d[v]值才有可能改变,因此在每次的松弛操作中,假如被松弛了,就放入队列中,而将每次遍历所有边的操作改为遍历这个节点的所有邻居节点,但是带来的一个问题就是,无法像last数组那样进行距离的限制,

时间方面非常的优秀,可以达到O(kE),经常优于优化Dij,最坏情况退化成O(VE)和Bell-Ford一样

统计最短路径条数

和Dij不同的是,同一个节点会访问多次,因此不能依据Dij中写,需要设置前驱数组setpre[MAXN],当遇到一条和已有最短路长度相同的时候就重新进行计算最短路径条数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i = 0;i<n-1;i++){ // 循环n-1次
	for(int u = 0;u<n;u++){ // 每个边都需要访问一次
        for(int j = 0;j<Adj[u].size();j++){
            int v = Adj[u][j].v;//邻接点
            int val = Adj[u][j].val;//边权
            
        	if(d[u] + val < d[v]){ //以u为中介可以令d[v]减小
                d[v] = d[u] + val;// 覆盖权值
                num[v] = num[u]; // 路径数也覆盖
                pre[v].clear();
                pre[v].insert(u);//清空前驱并加入u
            }else if(d[u] + val == d[v]){ //路径相等情况 需要重新计算
                pre[v].insert(u);
                num[v] = 0;
                // 遍历路径重新计算最短路径条数
                for(auto it = pre[v].begin();it!=pre[v].end();it++){
                    num[v] += num[*it];
                }
                
            }
        
        }
    }
}

Floyd

有向无环图描述表达式

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 有向图的拓扑排序
#include<bits/stdc++.h>
using namespace std;

map<int, vector<int> >mp;
int in[1000];
int out[1000];//表示入度和出度 
vector<int> ans;
vector<int> tail;

int n,m;

void topsort()
{
    //先找入度为0 其实可以认为这些都是起点
    stack<int>st;
    for(int i = 1;i<=n;i++)
    {
        if(in[i]==0)
        {
            st.push(i);
            ans.push_back(i);
        }
    }
    
    while(!st.empty())
    {
        int top = st.top();
        st.pop();
        // 以当前结点为起点的一系列点的入度都要减一 相当于解除限制了 如果为0就再添加进去
        for(int i = 0;i<mp[top].size();i++)
        {
            int tem = mp[top][i];
            in[tem]--;
            if(in[tem]==0)
            {
                st.push(tem);
                ans.push_back(tem);
            }
        }
    }
}

int main()
{
    // 顶点个数和边的个数
    cin >> n >> m;
    for(int i = 0;i<m;i++)
    {
        int u,v;
        cin >> u >> v;
        mp[u].push_back(v);
        in[v]++;
    }
    topsort();
    for(int i = 0;i<ans.size();i++)
    {
        cout << ans[i] <<" ";
    }
    return 0;
}/*
5 7
1 2
1 4
2 3
2 4
3 5
4 3
4 5
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void topsort()
{
    int num = 0;
    queue<int>q;// 存放度为0的结点
    for(int i = 0;i<n;i++)
    {
        if(degree[i]==0)
        {
            q.push(i);
            num ++;
        }
    }
    while(!q.empty()){
        int front = q.front();
        cout << front <<" ";
        q.pop();
        for(int i = 0;i<n;i++){//将该结点的所有出边的入度减1
            if(mp[front][i]!=0){
                degree[i]--;
                if(degree[i]==0)// 入度为0才可以入队
                {
                    q.push(i);
                    num++;
                }
            }
        }
    }

    if(num == n) cout << "\n拓扑排序成功!\n";
    else cout << "\n拓扑排序失败\n";
    
}

关键路径

最长的一个路径是关键路径,需要求解每个活动的最早发生时间和最晚发生时间,只有当两者是相等的才是关键活动,所有由关键活动组成的路径为关键路径

专业课 > 数据结构 > 图
#最小生成树 #拓扑排序 #最短路径 #关键路径
图的应用
https://rain_dew.gitee.io/2024/04/20/专业课/数据结构/6.图/6.4 图的应用/
Author
Wang yulu
Posted on
April 20, 2024
Licensed under