欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[数据结构] DS树+图综合练习--拓扑排序

程序员文章站 2022-05-21 16:13:49
...

DS树+图综合练习–拓扑排序

已知有向图,顶点从0开始编号,求它的求拓扑有序序列。
拓扑排序算法:给出有向图邻接矩阵
1.逐列扫描矩阵,找出入度为0且编号最小的顶点v
2.输出v,并标识v已访问
3.把矩阵第v行全清0
重复上述步骤,直到所有顶点输出为止

输入
第一行输入一个整数t,表示有t个有向图
第二行输入n,表示图有n个顶点
第三行起,输入n行整数,表示图对应的邻接矩阵
以此类推输入下一个图的顶点数和邻接矩阵

输出
每行输出一个图的拓扑有序序列

样例输入
2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

样例输出
0 1 3 2 4
4 6 5 1 3 2 0

参考代码

#include<iostream>

using namespace std;

const int MaxLen=20;

class Map
{
private:
    bool Visit[MaxLen];
    int Matrix[MaxLen][MaxLen];
    int Vexnum;
    int Select();
    void Update(int sel);
public:
    Map(){}
    void SetMatrix(int vnum, int mx[MaxLen][MaxLen]);
    void TopoSort();
};

void Map::SetMatrix(int vnum, int mx[MaxLen][MaxLen])
{
    int i, j;
    Vexnum = vnum;
    for(i=0; i<MaxLen; i++)
        for(j=0; j<MaxLen; j++)
            Matrix[i][j] = 0;

    for(i=0; i<Vexnum; i++)
        for(j=0; j<Vexnum; j++)
            Matrix[i][j] = mx[i][j];

    for(i=0; i<Vexnum; i++)
        Visit[i] = false;
}

void Map::TopoSort()
{
    int i, j;
    int flag;
    for(i=0; i<Vexnum; i++)
    {
        int sel = Select();
        cout<<sel<<" ";
        Update(sel);
    }
    cout<<endl;
}

int Map::Select()
{
    int i, j;
    for(i=0; i<Vexnum; i++)
    {
        if(!Visit[i])
        {
            for(j=0; j<Vexnum; j++) //判断该列是否全0,即入度为0
            {
                if(Matrix[j][i]!=0)
                    break;
            }
            if(j==Vexnum)
            {
                Visit[i] = true; //标记该点已访问
                return i; //返回输出
            }
        }
    }
    return -1;
}

void Map::Update(int sel)
{
    int i;
    for(i=0; i<Vexnum; i++)
    {
        Matrix[sel][i] = 0;
    }
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Map test;
        int n;
        int mx[MaxLen][MaxLen];
        cin>>n;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>mx[i][j];
        test.SetMatrix(n, mx);
        test.TopoSort();
    }
    return 0;
}

相关标签: 数据结构