西南交通大学【算法分析与设计实验1】

实验1.4 有向图拓扑排序

实验目的

（1）掌握算法的自然语言描述法，流程图绘制方法以及伪代码描述方法。

（2）理解算法的执行过程。

（3）掌握算法的编程实现方法、调试方法及测试方法。

实验任务

按照实验教程上图1-6的伪代码，实现基于深度优先（DFS）的有向图拓扑排序算法。具体要求如下：

（1）阅读并理解该伪代码。

（2）根据测试用例，分析该算法的执行过程。

（3）用C++语言实现该算法，并针对测试用例，将程序运行结果和手工分析结果进行对比验证。

（4）撰写实验报告，实验报告内容包括实验目的、实验任务、实验环境、实验步骤、实验结果和实验总结等部分。

实验步骤及结果

实验预习

根据测试用例分析算法的执行过程

（1）测试用例1

从顶点1开始，按照字典序进行DFS，给出每一步TS-Visit的中间结果。

初始状态

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	False	False	False
Visited	False	False	False	False	False
δ	0	0	0	0	0

第1次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	False	False	False
Visited	False	False	False	False	False
δ	0	0	0	0	0

第2次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	False	False	False	False
Visited	False	False	False	False	False
δ	0	0	0	0	0

第3次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	False	False
Visited	False	False	False	False	False
δ	0	0	0	0	0

第4次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	True	False
Visited	False	False	False	False	False
δ	0	0	0	0	0

返回第4次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	True	False
Visited	False	False	False	False	True
δ	0	0	0	0	5

返回第3次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	False	False
Visited	False	False	False	True	True
δ	0	0	0	4	5

第5次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	False	False
Visited	False	False	False	True	True
δ	0	0	0	4	5

返回第5次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	True	False	False	False
Visited	False	False	False	True	True
δ	0	0	0	4	5

返回第2次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	True	False	False	False	False
Visited	False	True	False	True	True
δ	0	3	0	4	5

返回第1次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	False	False	False
Visited	True	True	False	True	True
δ	2	3	0	4	5

第6次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	False	False	False
Visited	True	True	False	True	True
δ	2	3	0	4	5

第7次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	True	False	False
Visited	True	True	False	True	True
δ	2	3	0	4	5

返回第7次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	True	False	False
Visited	True	True	False	True	True
δ	2	3	0	4	5

返回第6次调用TS-Visit

	顶点1	顶点2	顶点3	顶点4	顶点5
Stacked	False	False	False	False	False
Visited	True	True	True	True	True
δ	2	3	1	4	5

最终的拓扑排序结果：

3 1 2 4 5

（2）测试用例2

最终的拓扑排序结果：

6 1 4 3 5 2

伪代码中 if v is marked stacked 如果为真，表示什么意思？

答：正常程序不会出现if v is marked stacked为真的情况，伪代码中 if v is marked stacked 如果为真表示此图中出现了环。

用C/C++语言实现该算法

算法要求的输入格式为：

第一行是两个整数 n m，分别表示图的顶点数和边数，顶点从 1 到 n编号；其后有 m 行，每行两个整数，分别表示每条有向边的起始顶点和结束顶点。

例：测试用例 1 对应的输入如下：

5 5

1 2

2 4

2 5

3 4

4 5

算法要求的输出格式为：

按照拓扑排序排好的顶点编号，编号之间用一个空格分割。

源代码：

#include <iostream>
#define MAX_VERTEX_N 20 // 最大节点数+1
using namespace std;
// 判断是否有环
int flag = 0;
// 图的类型
typedef enum
{
    DG, // 有向图
    DN, // 有向网
    UDG, // 无向图
    UDN // 无向网
}GraphKind;
// 边节点
typedef struct ArcNode
{
    int adjvex; // 数据域
    struct ArcNode *nextarc; // 下一个邻接点
}ArcNode;
// 节点
typedef struct
{
    int data; // 数据域
    ArcNode *firstarc; // 第一个邻接点
}VNode, AdjList[MAX_VERTEX_N];
// 图
typedef struct
{
    AdjList vexs; // 节点数组
    int vex_num; // 节点数
    int arc_num; // 弧数
    GraphKind kind; // 图类型
} ALGraph;
// 输入数据创建邻接表
void CreateUDN(ALGraph &G)
{
    // 节点个数 弧个数
    int v_num, a_num;
    cin>>v_num>>a_num;
    G.vex_num = v_num;
    G.arc_num = a_num;
    // 初始化图的邻接表的点数组
    for(int i = 1;i <= v_num;++i){
        G.vexs[i].data = i;
        G.vexs[i].firstarc = NULL;
    }
    for(int i = 0;i < a_num;++i){
        // 起始节点 终止节点
        int v1, v2;
        // 定位点邻接的最后一个点节点
        ArcNode *end;
        cin>>v1>>v2;
        ArcNode *temp = new ArcNode;
        temp->adjvex = v2;
        temp->nextarc = NULL;
        end = G.vexs[v1].firstarc;
        // 如果v1还没有邻接点
        if(!end){
            G.vexs[v1].firstarc = temp;
        }else{// 在最后继续邻接
            while (end->nextarc)
            {
                end = end->nextarc;
            }
            end->nextarc = temp;
        }
    }
}
// 访问各个节点
void visit(ALGraph G, int index, int *judge, int *res, int &i){
    // 如果是状态1，则返回
    if(judge[index] == 1){
        flag = 1;
        return;
    }
    // 如果是状态0即未访问
    if(judge[index] == 0){
        judge[index] = 1;
        ArcNode *temp = G.vexs[index].firstarc;
        // 深度搜索
        while (temp)
        {
            visit(G, temp->adjvex, judge, res, i);
            temp = temp->nextarc;
        }
        // 改为已访问状态
        judge[index] = 2;
        // 将节点下标存储在结果数组res中
        res[i] = index;
        i--;
    }
}
// 拓扑排序
void TopologicalSort(ALGraph G){
    int i = G.vex_num;
    int *judge = new int[G.vex_num+1];
    int *res = new int[G.vex_num+1];
    // 初始化判断数组
    for(int j = 1;j <= G.vex_num;++j){
        judge[j] = 0;
    }
    // 从一个未访问节点出发
    for(int j = 1;j <= G.vex_num;++j){
        if(judge[j] == 0){
            visit(G, j, judge, res, i);
        }
    }
    // 输出结果
    if(flag){
        cout<<"此图有环,没有拓扑排序"<<endl;
    }else{
        for(int j = 1;j <= G.vex_num;++j){
            cout<<G.vexs[res[j]].data<<" ";
        }
    }
    delete judge;
    delete res;
}
// 释放创建图时动态申请的内存
void des(ALGraph &G)
{
    for (int i = 1; i <= G.vex_num; ++i)
    {
        ArcNode *p = G.vexs[i].firstarc;
        ArcNode *q = NULL;
        while (p)
        {
            q = p->nextarc;
            delete p;
            p = q;
        }
    }
}
int main(void)
{
    ALGraph G;
    // 创建图
    CreateUDN(G);
    // 进行拓扑排序
    TopologicalSort(G);
    cout<<endl;
    // 释放内存
    des(G);
    system("pause");
    return 0;
}

上机实验

测试用例1

测试用例输入：

9 9

1 2

1 8

2 3

2 8

3 4

5 3

5 6

6 4