算法-拓扑排序

拓扑排序的大致思路就是对一个有向无圈图顶点进行排序，找到任意一个入度（至于入度，我的话来说就是有多少个点指向自己）为0的顶点，显示该顶点，然后删除该点及其边，即该点所指向的其他顶点的入度都减1，然后同样方向对剩余部分处理。

拓扑排序的用途，使得如果存在一条从vi到vj的路径，那么排序中vj在vi的后面；暂时还没用到，以后可能会用；参考用书《数据结构与算法分析》，不得不说c++的容器的确方便了许多；

#include <iostream>
#include <queue>
#include <list>
#include <iterator>
#include <vector>
#define MAX 500
using namespace std;

typedef struct TableEntry
{
    list<int> mylist;
    int indegree;//入度
}adjacency_list;

int numvertex;
adjacency_list graph[MAX];
vector<int> topnum;

void graph_init()
{
    int v;
    for(int i=0; i<numvertex; i++)//初始化图数据
    {
        graph[i].indegree = 0;
    }
    for(int i=0; i<numvertex; i++)
    {
        cout << "输入" << i << "的邻接点" << endl;
        while(cin >> v)
        {
            graph[i].mylist.push_back(v);
            graph[v].indegree++;
        }
        cin.clear();
    }
}

void topsort()
{
    int counter = 0;
    int v;
    list<int>::iterator it;
    queue<int> myqueue;
    for(int i=0; i<numvertex; i++)
    {
        if(graph[i].indegree == 0)//入度为0则入队
            myqueue.push(i);
    }
    while(!myqueue.empty())
    {
        v = myqueue.front();
        counter++;
        myqueue.pop();//依次出队
        topnum.push_back(v);//出队元素放入vector
        for(it=graph[v].mylist.begin(); it!=graph[v].mylist.end(); it++)//删除出队顶点和他的边，即出队元素邻接点入度均减1
        {
            if(--graph[*it].indegree == 0)//入度为0则入队
                myqueue.push(*it);
        }
    }
    if(counter != numvertex)
        cout << "error,图含有圈!" << endl;

}

int main()
{
    cout << "输入顶点数量" << endl;
    cin >> numvertex;
    graph_init();
    topsort();
    for(int i=0; i<topnum.size(); i++)
        cout << topnum[i] << " ";
    cout  << endl;
    return 0;
}