1. Toy模板网首页
  2. > Toy博客

数据结构第12周 ：（ 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 ）

10月前 作者：一只可爱的小猴子 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构第12周 ：（ 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 ）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有向无环图的拓扑排序

【问题描述】

由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。由偏序定义得到拓扑有序的操作便是拓扑排序。

拓扑排序的流程如下：

  1. 在有向图中选一个没有前驱的顶点并且输出之；

  2. 从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
在本题中，读入一个有向图的邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法判断此图是否有回路，如果没有回路则输出拓扑有序的顶点序列。

【输入形式】

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

【输出形式】

如果读入的有向图含有回路，请输出“ERROR”，不包括引号。

如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。

请注意行尾输出换行。

【样例输入】

4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0
【样例输出】

3 0 1 2

【说明】请注意采用邻接表存储结构时，链表创建需采用尾插法，以保证后续结点从小到大排列。

在本题中，需要严格的按照题目描述中的算法进行拓扑排序，并在排序的过程中将顶点依次储存下来，直到最终能够判定有向图中不包含回路之后，才能够进行输出。

另外，为了避免重复检测入度为零的顶点，可以通过一个栈结构维护当前处理过程中入度为零的顶点。

#include<iostream>
#include<stdlib.h>
#include<stack>
#define N 50
using namespace std;

typedef struct node
{
    int data;
    struct node * next;
}ArcNode;

typedef struct
{
    int in; //表示该节点的入度
    int vertex; // 该节点的信息
    int flag; //判断该节点是否入栈的标志
    ArcNode * firstedge;
}ALGraph;

ALGraph G[N];
int res[N];

void TopoSort(int limit)
{
    stack<ALGraph*> s;
    int count = 0;
    int i = 0;
    for(i = 0; i < limit; i ++)
    {
        if(G[i].in == 0)
        {
            s.push(&G[i]);
            G[i].flag = 0;
        }
    }
    while(!s.empty())
    {
        ALGraph * pos = s.top();
        s.pop();
        count ++;
        res[count] = pos->vertex;
        ArcNode * p = pos->firstedge;
        while(p != NULL)
        {
            int num = p->data;
            G[num].in --;
            p = p->next;
        }
        for(i = 0 ; i <limit; i ++)
        {
            if(G[i].in == 0 && G[i].flag == 1)
            {
                s.push(&G[i]);
                G[i].flag = 0;
            }
        }
    }
    if(count == limit)
    {
        for(i = 1; i <= limit; i ++)
        {
            cout<<res[i]<<" ";
        }
    }
    else
    {
        cout<<"ERROR";
    }
}

int main()
{
    int NodeNum = 0;
    cin>>NodeNum;
    int i = 0;
    int j = 0;
    for(i = 0; i < NodeNum; i ++) //邻接表初始化
    {
        G[i].in = 0;
        G[i].vertex = i;
        G[i].flag = 1;
        G[i].firstedge = NULL;
    }
    for(i = 0; i < NodeNum; i ++)
    {
        for(j = 0; j < NodeNum; j ++)
        {
            int num;
            cin>>num;
            if(num == 0) continue;
            else
            {
                ArcNode * temp = (ArcNode*)malloc(sizeof(ArcNode));
                temp->data = j;
                temp->next = NULL;
                ArcNode * pos = G[i].firstedge;
                while(1)
                {
                    if(pos == NULL) break;
                    if(pos->next == NULL) break;
                    else
                        pos = pos->next;
                }
                if(pos == NULL)
                {
                    G[i].firstedge = temp;
                }
                else
                {
                    pos->next = temp;
                }
                G[j].in ++;
            }
        }
    }
    TopoSort(NodeNum);
    return 0;
}

拓扑排序和关键路径

【问题描述】若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。
【输入形式】第一行输入两个数字，分别表示顶点数和边数；从第二行开始，输入边的信息，格式为（i，j, weight）
【输出形式】关键路径的总时间（最大路径长度），代表关键活动的边，格式为（顶点1，顶点2），按大小顺序排列
【样例输入】
6 8
0 1 3
0 2 2
1 3 2
1 4 3
2 3 4
2 5 3
3 5 2
4 5 1
【样例输出】

8

0 2

2 3

3 5

#include<iostream>
#define N 50
#include<stack>
#include<stdlib.h>
using namespace std;

typedef struct node
{
    int NodeId;
    int weight;
    int edgeId;
    struct node * next;
}ArcNode; //邻接结点结构体

typedef struct
{
    int in;
    int out;
    int flag;
    int vertex;
    ArcNode * firstedge;
}ALGraph; //邻接表结构体

ALGraph G[N];
int Relation[N][N];
int VE[N];
int VL[N];
int EE[N];
typedef struct
{
    int Weight;
    int node1;
    int node2;
}point;
point EL[N];
int el[N];
int count = -1;

void MaxPathLen(int limit)
{
    int i = 0;
    stack<ALGraph*> S;

    //用入度来处理正向拓扑排序（填充VE
    for(i = 0; i < limit; i ++)
    {
        if(G[i].in == 0)
        {
            S.push(&G[i]);
            G[i].flag = 0;
        }
    }
    while(!S.empty())
    {
        ALGraph * temp = S.top();
        S.pop();
        ArcNode * p = temp->firstedge;
        while(p != NULL) //弹出的节点的相邻节点的入度减一，填充VE
        {
            G[p->NodeId].in --;
            if(VE[temp->vertex] + p->weight > VE[p->NodeId])
            {
                VE[p->NodeId] = VE[temp->vertex] + p->weight;
                //cout<<p->NodeId<<" "<<VE[p->NodeId]<<endl;
            }
            p = p->next;
        }
        for(i = 0; i < limit; i ++)
        {
            if(G[i].in == 0 && G[i].flag == 1)
            {
                S.push(&G[i]);
                G[i].flag = 0;
            }
        }
    }
    for(i = 0; i < limit; i ++)
    {
        G[i].flag = 1; //将标记初始化
    }
    int max = -1;
    int maxid = 0;
    for(i = 0; i < limit; i ++)
    {
        if(VE[i] > max)
        {
            max = VE[i];
            maxid = i;
        }
    }
    VL[maxid] = max;

    //用出度来处理逆向拓扑排序（填充VL
    for(i = 0; i < limit; i ++)
    {
        if(G[i].out == 0)
        {
            S.push(&G[i]);
            G[i].flag = 0;
        }
    }
    while(!S.empty())
    {
        ALGraph * temp = S.top();
        S.pop();
        for(i = 0; i < limit; i ++)
        {
            if(Relation[temp->vertex][i] == 1)
            {
                G[i].out --;
                Relation[temp->vertex][i] = 0;
                ArcNode * pos = G[i].firstedge;
                while(pos->NodeId != temp->vertex) pos = pos->next;
                if(VL[i] == 0)
                {
                    VL[i] = VL[temp->vertex] - pos->weight;
                }
                if(VL[temp->vertex] - pos->weight < VL[i] )
                {
                    VL[i] = VL[temp->vertex] - pos->weight;
                    //cout<<temp->vertex<<" "<<VL[temp->vertex]<<" "<<pos->weight<<endl;
                }
            }
        }
        for(i = 0; i < limit; i ++)
        {
            if(G[i].out == 0 && G[i].flag == 1)
            {
                S.push(&G[i]);
                G[i].flag = 0;
            }
        }
    }

    //计算EE[N],EL[N]
    for(i = 0; i <= count; i ++)
    {
        int e = EE[i];
        int l = EL[i].node2;
        EE[i] = VE[e];
        el[i] = VL[l] - EL[i].Weight;
    }
    cout<<max<<endl;
    for(i = 0; i <= count; i ++)
    {
        if(EE[i] == el[i])
            cout<<EL[i].node1<<" "<<EL[i].node2<<endl;
    }
}

int main()
{
    int NodeNum;
    int EdgeNum;
    cin>>NodeNum>>EdgeNum;
    int i, j;
    for(i = 0; i < NodeNum; i ++)
    {
        VE[i] = 0;
        VL[i] = 0;
    }
    for(i = 0; i < EdgeNum; i ++)
    {
        EE[i] = 0;
        el[i] = 0;
        EL[i].Weight = 0;
        EL[i].node1 = 0;
        EL[i].node2 = 0;
    }
    for(i = 0; i < NodeNum; i ++) //表的初始化
    {
        G[i].in = 0;
        G[i].out = 0;
        G[i].flag = 1;
        G[i].vertex = i;
        G[i].firstedge = NULL;
    }
    for(i = 0; i < NodeNum; i ++)
    {
        for(j = 0; j < NodeNum; j ++)
        {
            Relation[i][j] = 0;
        }
    }
    i = EdgeNum;
    while(i --) //表的填充
    {
        int node1;
        int node2;
        int w;
        cin>>node1>>node2>>w;
        Relation[node2][node1] = 1;
        ArcNode * temp = (ArcNode *)malloc(sizeof(ArcNode));
        temp->NodeId = node2;
        temp->weight = w;
        temp->next = NULL;
        count ++;
        EE[count] = node1;
        EL[count].node1 = node1;
        EL[count].node2 = node2;
        EL[count].Weight = w;
        temp->edgeId = count;
        G[node1].out ++;
        G[node2].in ++;
        ArcNode * pos = G[node1].firstedge;
        if(pos == NULL)
        {
            G[node1].firstedge = temp;
        }
        else
        {
            while(1)
            {
                if(pos->next == NULL) break;
                else
                    pos = pos->next;
            }
            pos->next = temp;
        }
    }
    MaxPathLen(NodeNum);

    return 0;
}

确定比赛名次

【问题描述】

此题为ACM竞赛真题，更强大的测试数据请自行前往以下链接进行代码提交验证。Problem - 1285 (hdu.edu.cn)

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

【输入形式】

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

【输出形式】

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

【样例输入】

4 3

1 2

2 3

4 3

【样例输出】

1 2 4 3

【样例说明】

符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

#include<iostream>
#define N 50
#include<stdlib.h>
#include<stack>
using namespace std;

typedef struct node
{
    int nodeId;
    struct node * next;
}ArcNode;

typedef struct
{
    int in;
    int flag;
    int advtex;
    ArcNode * firstedge;
}ALGraph;

ALGraph G[N];

int main()
{
    int NodeNum;
    int EdgeNum;
    cin>>NodeNum>>EdgeNum;
    int i = 0;
    for(i = 1; i <= NodeNum; i ++)
    {
        G[i].advtex = i;
        G[i].in = 0;
        G[i].flag = 1;
        G[i].firstedge = NULL;
    }
    i = EdgeNum;
    while(i --)
    {
        int node1;
        int node2;
        cin>>node1>>node2;
        G[node1].advtex = node1;
        G[node2].in ++;
        ArcNode * pos = G[node1].firstedge;
        ArcNode * temp = (ArcNode*)malloc(sizeof(ArcNode));
        temp->nodeId = node2;
        temp->next = NULL;
        if(pos == NULL)
            G[node1].firstedge = temp;
        else
        {
            while(1)
            {
                if(pos->next == NULL)
                    break;
                else
                    pos = pos->next;
            }
            pos->next = temp;
        }
    }
    stack<ALGraph*> S;
    for(i = 1; i <= NodeNum; i ++)
    {
        if(G[i].in == 0)
        {
            S.push(&G[i]);
            G[i].flag = 0;
            break;
        }
    }
    while(!S.empty())
    {
        ALGraph * p = S.top();
        S.pop();
        cout<<p->advtex<<" ";
        ArcNode * pos = p->firstedge;
        while(pos != NULL)
        {
            G[pos->nodeId].in --;
            pos = pos->next;
        }
        for(i = 1; i <= NodeNum; i ++)
        {
            if(G[i].in == 0 && G[i].flag == 1)
            {
                S.push(&G[i]);
                G[i].flag = 0;
                break;
            }
        }
    }
    return 0;
}

割点

【问题描述】

求一个无向连通图的割点。割点的定义是：若删除此结点和与其相关联的边，无向图不再连通。

ACM竞赛中有一些涉及到连通分量、割点、割边、缩点等知识点相关的题目，做完此题大家可自行前往以下链接查看并思考类似的题目，自行提交代码验证。Problem - 4587 (hdu.edu.cn)

【输入形式】

第一行是顶点个数及边的条数，后续每一行是每条边的两端关联的两个顶点

【输出形式】

割点，若没有割点，则输出NO

【样例输入】

7 8

A B

A D

B C

C D

C G

D E

D F

E F

【样例输出】

C D

【样例输入】

5 7

A B

B C

B D

A D

C D

A E

E C

【样例输出】

NO文章来源地址https://www.toymoban.com/news/detail-477757.html

#include<iostream>
#define N 50
using namespace std;

int R[N][N];
int Dfn[N];
int Low[N];
int root = 0;
bool res[N];
int timestamp = 0;
int NodeNum; //节点个数
int RelationNum; //边的条数

void Tarjan(int p)
{
    Dfn[p] = Low[p] = ++ timestamp;
    int i = 0;
    int cnt = 0;
    for(i = 0; i < NodeNum; i ++)
    {
        if(R[p][i] == 1)
        {
            if(Dfn[i] == 0)
            {
                Tarjan(i);
                Low[p] = min(Low[p], Low[i]);
                if(Dfn[p] <= Low[i])
                {
                    cnt ++;
                    if(p != root || cnt >= 2)
                    {
                        res[p] = 1;
                    }
                }
            }
            else
                Low[p] = min(Low[p], Dfn[i]);
        }
    }
}

int main()
{
    cin>>NodeNum>>RelationNum;

    int i, j;
    for(i = 0; i < NodeNum; i ++)
    {
        for(j = 0; j < NodeNum; j ++)
        {
            R[i][j] = 0;
        }
    }

    i = RelationNum;
    while(i --)
    {
        char node1;
        char node2;
        cin>>node1>>node2;
        int n1 = int(node1) - 65;
        int n2 = int(node2) - 65;
        R[n1][n2] = R[n2][n1] = 1;
    }

    for(root = 0; root < NodeNum; root ++)
    {
        if(Dfn[root] == 0) Tarjan(root);
    }
    bool IsGe = false;
    for(i = 0; i < NodeNum; i ++)
    {
        if(res[i])
        {   cout<<char(i + 'A')<<" ";
            IsGe = true;
        }
    }
    if(IsGe == false) cout<<"NO";

    return 0;
}

到了这里，关于数据结构第12周 ：（ 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 ）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 有向无环图的应用—描述表达式、AOV网、AOE网

    有向无环图的应用—描述表达式、AOV网、AOE网

    目录 一、有向无环图描述表达式 二、拓扑排序 相关概念  实现方法  算法代码  补充 三、关键路径 相关概念  算法步骤  补充  四、总结图的应用我们都学了什么 有向无环图 ：若一个有向图中不存在环，则称为有向无环图，简称DAG图。  对于一个表达式 ( (a+b)* ( b*(c+d)

    2024年02月12日
    浏览(46)
  • 有向无环图——AOV网(拓扑排序)

    有向无环图——AOV网(拓扑排序)

    有向无环图： 无环的有向图，简称 DAG 图(Directed Acycline Graph) 有向无环图常用来描述一个工程或系统的进行过程。（通常吧计划、施工、生产、程序流程等当成是一个工程） 一个工程可以分为若干个 子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成 AOV网

    2024年02月11日
    浏览(85)
  • 【海量数据挖掘/数据分析】之 贝叶斯信念网络（贝叶斯信念网络、有向无环图、贝叶斯公式、贝叶斯信念网络计算实例）

    【海量数据挖掘/数据分析】之 贝叶斯信念网络（贝叶斯信念网络、有向无环图、贝叶斯公式、贝叶斯信念网络计算实例）

    目录 【海量数据挖掘/数据分析】之 贝叶斯信念网络（贝叶斯信念网络、有向无环图、贝叶斯公式、贝叶斯信念网络计算实例） 一、贝叶斯信念网络 1 . 属性关联 : 贝叶斯信念网络 允许数据集样本属性 之间存在依赖关系 ; 2 . 贝叶斯信念网络 表示方法 : 二、概率图模型 : 马尔

    2024年02月12日
    浏览(53)
  • 【数据结构——有向图】有环无环判定、拓扑排序（DFS、BFS）

    【数据结构——有向图】有环无环判定、拓扑排序（DFS、BFS）

    有向图（Directed Graph），也被称为有向图形或方向图，是一种图的类型。在有向图中，图中的边具有方向，从一个顶点指向另一个顶点。 在有向图中，每个顶点表示一个实体，而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(50)
  • 数据结构：有向完全图和无向完全图的边数

    数据结构：有向完全图和无向完全图的边数

    一个拥有n个结点的无向完全图的边数为：n×(n−1)÷2 具体的解释： 比如我们有一个拥有4个结点的无向完全图， 我们首尾依次连接，共有4条边。 然后我们选择其他的两条边来连线。 又多出了2条边。一共有4 + 2 = 6条边。 我们来分析一下具体的过程，首先如果为n个结点的话，

    2024年02月11日
    浏览(41)
  • 数据结构几种常见图的邻接矩阵的画法（有向图带权值，有向图不带权值，无向图带权值，无向图不带权值）

    数据结构几种常见图的邻接矩阵的画法（有向图带权值，有向图不带权值，无向图带权值，无向图不带权值）

    这不马上要期末考试了，复习的时候突然发现了有好几种图的邻接矩阵需要画，在网上找了半天结果发现也没有特别详细的总结，所以经过总结写一下吧，希望对有需要的人，有点帮助吧！！！！（如有不对还请见谅！！！！！~~~~~~） 1，有向图带权值   2.有向图不带权值

    2024年02月13日
    浏览(54)
  • 数据结构（12）Dijkstra算法JAVA版：图的最短路径问题

    数据结构（12）Dijkstra算法JAVA版：图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径，即最少步数，使用BFS+贪心算法来求解最短路径，比较好实现，此处不做展开讨论。 有权图的最短路径，不考虑权重为负数的情况，因为权重为负

    2024年02月06日
    浏览(48)
  • 教学计划编制问题(数据结构 有向图 拓扑排序)

    教学计划编制问题(数据结构 有向图 拓扑排序)

     本文对以下教学计划编制问题的解决作出实现，主要使用c语言(带一点cpp)，开发环境为codeblocks 17.12,希望对各位读者有所帮助。（源码和数据文件可在主页获取，同时还有使用视频文件压缩包,数据文件需要和exe在同一目录下，结合某读者的意见同时放到github了 ) 地址如下

    2024年02月09日
    浏览(56)

  • 数据结构|连通图、完全图、无向图、有向图的边数计算问题

    完全图 也称简单完全图。一个图任意两个顶点之间都有边的话，该图就称为完全图。 连通图（一般都是指无向图） 如果图中任意俩顶点都连通，则该图为连通图。 有向图 由点和弧所构成的图（ 强连通图必然是有向图，因为强连通和弱连通的概念只在有向图中存在 ） 无向

    2023年04月08日
    浏览(47)
  • 数据结构--图的存储结构

    数据结构--图的存储结构

    第九话  数据结构之图的存储 文章目录 一、了解什么是图 二、图的定义和基本术语 三、存储结构之邻接矩阵 1.邻接矩阵的介绍 2.邻接矩阵的创建 3.主函数中实现 四、存储结构之邻接表 1.邻接表的介绍 2.邻接表的创建 3.在主函数中实现 五、总结 一切尽在图结构 图的应用非

    2024年02月07日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包