《数据结构与算法》——拓扑排序

luciferzf

拓扑排序：
建立一个有向图，我们称之为AOV图。我们需要将AOV图中每个点进行排序，按照入度的多少的顺序。我们用栈结构来储存点，首先我们先将入度为0的点压入栈中，然后把压入栈中的点从AOV图中删除，与其相邻的点的度减一。
在代码实现的过程中，我们使用数组来储存每个点，用链表的方式来储存每个点的出度。当进行遍历的时候，我们将所有入度为0的点压入栈中，然后把改点的出度的点的入度减一。循环至所有点都被压入栈中。

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

int stack[1000];
int N;

class graph
{
public:
        int low;
        graph *np=NULL;
};

class VERTEX
{
public:
        int power=0;
        graph *np = NULL;
};

void Input(VERTEX vertex[])
{
        int a, b;
        printf("input the edge of graph and end with double -1:\n");
        cin >> a >> b;
        graph *cp=NULL;
        while (a != -1)
        {
                if (vertex[a].np == NULL)
                {
                        vertex[a].np = new graph;
                        cp = vertex[a].np;
                }
                else
                {
                        cp->np = new graph;
                        cp = cp->np;
                }
                cp->low = b;
                vertex[b].power++;
                cin >> a >> b;
        }
}

void print(VERTEX vertex[])
{
        for (int i = 0; i < N; i++)
        {
                printf("%d",stack[i]);
                if (i != N-1)
                {
                        printf("——>");
                }
                else
                {
                        cout << endl;
                }
        }
}

int main()
{
        int count=0;
        cout << "input the numbers of the vertexes:";
        cin >> N;
        int edge=0;
        cout<<"input the numbers of the edge:";
        cin>>edge;
        VERTEX vertex[edge];
        Input(vertex);
        graph *cp;
        while (count < N)
        {
                int precount = count;
                for (int i = 1; i <= N; i++)
                {
                        if (vertex[i].power == 0)
                        {
                                stack[count++] = i;
                                vertex[i].power = -1;
                        }
                }
                while (precount != count)
                {
                        cp = vertex[stack[precount]].np;
                        while (cp != NULL)
                        {
                                vertex[cp->low].power--;
                                cp = cp->np;
                        }
                        precount++;
                }
        }
        print(vertex);
        system("PAUSE");
}