拓扑排序

#include <iostream>
using namespace std;

#define MAX_VERTEX_NUM    20
struct adjVertexNode
{
    int adjVertexPosition;
    adjVertexNode * next;
};
struct VertexNode
{
    char data [ 2 ];
    adjVertexNode * list;
    int indegree;
};
struct Graph
{
    VertexNode VertexNode [ MAX_VERTEX_NUM ];
    int vertexNum;
    int edgeNum;
};

void CreateGraph ( Graph & g)
{
     int i , j , edgeStart , edgeEnd;
     adjVertexNode * adjNode;
     cout << "Please input vertex and edge num (vnum enum):" << endl;
     cin >> g . vertexNum >> g . edgeNum;
     cout << "Please input vertex information (v1) /n note: every vertex info end with Enter" << endl;
     for ( i = 0; i < g . vertexNum; i ++)
     {
         cin >> g . VertexNode [ i ]. data; // vertex data info.
         g . VertexNode [ i ]. list = NULL;
         g . VertexNode [ i ]. indegree = 0;
     }
     cout << "input edge information(start end):" << endl;
     for ( j = 0; j < g . edgeNum; j ++)
     {
         cin >> edgeStart >> edgeEnd;
         adjNode = new adjVertexNode;
         adjNode -> adjVertexPosition = edgeEnd - 1; // because array begin from 0, so it is j-1
         adjNode -> next = g . VertexNode [ edgeStart - 1 ]. list;
         g . VertexNode [ edgeStart - 1 ]. list = adjNode;
         //每增加一条边，则边的End顶点的入度加1
         g . VertexNode [ edgeEnd - 1 ]. indegree ++;
     }
}

void PrintAdjList( const Graph & g)
{
    cout << "The adjacent list for graph is:" << endl;
    for ( int i = 0; i < g . vertexNum; i ++)
    {
        cout << g . VertexNode [ i ]. data << "->";
        adjVertexNode * head = g . VertexNode [ i ]. list;
        if ( head == NULL)
            cout << "NULL";
        while ( head != NULL)
        {
            cout << head -> adjVertexPosition + 1 << " ";
            head = head -> next;
        }
        cout << endl;
    }
}

VertexNode & FindZeroIndegree( Graph & g)
{
    for ( int i = 0; i < g . vertexNum; i ++)
    {
        if ( g . VertexNode [ i ]. indegree == 0)
            return g . VertexNode [ i ];
    }
    return g . VertexNode [ 0 ];
}
void TopSort( Graph & g)
{
    cout << "The topsort is:" << endl;
    for ( int i = 0; i < g . vertexNum; i ++)
    {
        VertexNode & v = FindZeroIndegree( g);
        if ( v . indegree != NULL)
            cout << "The graph has cycle, can not do topsort" << endl;
        // print graph as topsort.
        cout << v . data << " ";
        // for each vertex w adjacent to v, --indegree
        adjVertexNode * padjv = v . list;
        while ( padjv != NULL)
        { //！！这个算法这里破坏了原图中的入度信息。最后入度均为1
            g . VertexNode [ padjv -> adjVertexPosition ]. indegree --;
            padjv = padjv -> next;
        }
        //避免入度信息均为零FindZeroIndegree找到删除的顶点，将删除的顶点入度置为1
        v . indegree ++;
    }
    cout << endl;
}

void DeleteGraph( Graph & g)
{
    for ( int i = 0; i < g . vertexNum; i ++)
    {
        adjVertexNode * tmp = NULL;
        while( g . VertexNode [ i ]. list != NULL)
        {
            tmp = g . VertexNode [ i ]. list;
            g . VertexNode [ i ]. list = g . VertexNode [ i ]. list -> next;
            delete tmp;
            tmp = NULL;
        }
    }
}
int main( int argc , const char ** argv)
{
    Graph g;
    CreateGraph( g);
    PrintAdjList( g);
    TopSort( g);
    DeleteGraph( g);

    return 0;
}