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

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;
}