有向无圈图拓扑排序

【http://www.cnblogs.com/skywang12345/p/3711493.html】
【http://blog.csdn.net/xufeng0991/article/details/41809119】
步骤：
1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)； 
2. 把所有没有依赖顶点的节点放入Q； 
3. 当Q还有顶点的时候，执行下面步骤： 
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)； 
3.2 对n每一个邻接点m(n是起点，m是终点)； 
3.2.1 去掉边<n,m>; 
3.2.2 如果m没有依赖顶点，则把m放入Q; 
算法实现：

#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

// 边
struct Edge{
    int vName;
    int weight;// 权值
    struct Edge* next;
};

// 顶点(链表头)
struct Vertex{
    int vName;
    int in;// 入度
    int out; // 初度
    struct Edge* next;
};

// 有向图
class GraphList
{
public:
    ~GraphList();

    void createGraph();
    void printGraph();
    bool topsortInDegree();
    bool topsortOutDegree();

private:
    // 1. 输入定点数
    void inputVertexCount();
    // 2. 生成定点数组
    void makeVertexArray();
    // 3. 输入边数
    void inputEdgeCount();
    // 4. 输入边的起始点
    void inputEdgeInfo();
    // 5. 添加边节点至对应的链表中
    void addEdgeToList(int vFrom, int weight, int vTo);
private:
    int m_vCount;
    int m_eCount;
    Vertex* m_vVertex;
};

GraphList::~GraphList(){
    for (int i = 0; i < m_vCount; ++i){
        Edge* tmp = m_vVertex[i].next;
        Edge* edge = NULL;
        while(tmp){
            edge = tmp;
            tmp = tmp->next;
            delete edge;
            edge = NULL;
        }
    }
    delete[] m_vVertex;
}

void GraphList::inputVertexCount()
{
    cout << "please input count of vertex:";
    cin >> m_vCount;
}

void GraphList::makeVertexArray()
{
    m_vVertex = new Vertex[m_vCount];
    // 初始化
    for (int i = 0; i < m_vCount; ++i){
        m_vVertex[i].vName = i;
        m_vVertex[i].next = NULL;
        m_vVertex[i].in = 0;
        m_vVertex[i].out = 0;
    }
}

void GraphList::inputEdgeCount()
{
    cout << "please input count of edge:";
    cin >> m_eCount;
}

void GraphList::inputEdgeInfo()
{
    cout << "please input edge information:" << endl;
    for (int i = 0; i < m_eCount; ++i){
        cout << "the edge " << i << ":" << endl;

        // 起点
        int from = 0;
        cout << "From: ";
        cin >> from;

        // 权值
        int weight = 0;
        cout << "Weight:";
        cin >> weight;

        // 终点
        int to = 0;
        cout << "To: ";
        cin >> to;
        cout << endl;

        addEdgeToList(from, weight, to);
    }
}

void GraphList::addEdgeToList(int vFrom, int weight, int vTo)
{
    Edge* edge = new Edge();
    edge->vName = vTo;
    edge->weight = weight;
    edge->next = NULL;
    Edge* tmp = m_vVertex[vFrom].next;
    if (tmp){
        while(tmp->next){
            tmp = tmp->next;
        }
        tmp->next = edge;
    }else{
        m_vVertex[vFrom].next = edge;
    }
    ++m_vVertex[vTo].in;    // 终点入度加1
    ++m_vVertex[vFrom].out; // 起点初度加1
}

void GraphList::printGraph()
{
    for (int i = 0; i < m_vCount; ++i){
        Edge* tmp = m_vVertex[i].next;
        cout << "list:" << m_vVertex[i].vName << "(in:" << m_vVertex[i].in << ")"<< "->";
        while(tmp){
            cout << "(weight:" << tmp->weight << ")";
            cout << tmp->vName << "->";
            tmp = tmp->next;
        }
        cout << "NULL" << endl;
    }
}

bool GraphList::topsortInDegree()
{
    stack<Vertex*> vertexStack;
    queue<Vertex*> vertexQueue;
    int* degree = new int[m_vCount];// 声明一个临时变量，保存入度值，作操作，避免影响原始节点中的数据

    // 1 统计入度为0的点
    for(int i = 0; i < m_vCount; ++i){
        degree[i] = m_vVertex[i].in;
        if(!degree[i]){
            vertexStack.push(&m_vVertex[i]);
        }
    }

    int count = 0;
    while(!vertexStack.empty()){
        // 保存入度为0的点
        Vertex* tmp = vertexStack.top();
        vertexStack.pop();
        vertexQueue.push(tmp);
        ++count;

        // 2 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）
        Edge* edge = tmp->next;
        while(edge){
            Vertex* vertex = &m_vVertex[edge->vName];
            --degree[edge->vName];
            if (!degree[edge->vName]){
                vertexStack.push(vertex);
            }
            edge = edge->next;
        }
    }

    // 判断是否有环
    if (count < m_vCount) {
        return false;
    }

    // 输出排序结果
    while(!vertexQueue.empty()){
        Vertex* tmp = vertexQueue.front();
        vertexQueue.pop();
        cout << tmp->vName << " ";
    }
    cout << endl;

    delete[] degree;

    return true;
}

// **************************************************************************
// 流程控制
// **************************************************************************
void GraphList::createGraph()
{
    inputVertexCount();
    makeVertexArray();
    inputEdgeCount();
    inputEdgeInfo();
}

// main.cpp

// test for GraphList
#include "GraphList.h"
#include <cstdlib>

int main()
{
    GraphList graph;
    graph.createGraph();
    graph.printGraph();
    graph.topsort();

    system("pause");

    return 0;
}

//////////////////////////////////////////////////////////////////////////////////

#define MAX 100
// 邻接表
class ListDG
{
    private: // 内部类
        // 邻接表中表对应的链表的顶点
        class ENode
        {
            int ivex;           // 该边所指向的顶点的位置
            ENode *nextEdge;    // 指向下一条弧的指针
            friend class ListDG;
        };

        // 邻接表中表的顶点
        class VNode
        {
            char data;          // 顶点信息
            ENode *firstEdge;   // 指向第一条依附该顶点的弧
            friend class ListDG;
        };

    private: // 私有成员
        int mVexNum;             // 图的顶点的数目
        int mEdgNum;             // 图的边的数目
        VNode *mVexs;            // 图的顶点数组

    public:
        // 创建邻接表对应的图(自己输入)
        ListDG();
        // 创建邻接表对应的图(用已提供的数据)
        ListDG(char vexs[], int vlen, char edges[][2], int elen);
        ~ListDG();

        // 深度优先搜索遍历图
        void DFS();
        // 广度优先搜索（类似于树的层次遍历）
        void BFS();
        // 打印邻接表图
        void print();
        // 拓扑排序
        int topologicalSort();

    private:
        // 读取一个输入字符
        char readChar();
        // 返回ch的位置
        int getPosition(char ch);
        // 深度优先搜索遍历图的递归实现
        void DFS(int i, int *visited);
        // 将node节点链接到list的最后
        void linkLast(ENode *list, ENode *node);
}; 

(01) ListDG是邻接表对应的结构体。 mVexNum是顶点数，mEdgNum是边数；mVexs则是保存顶点信息的一维数组。 
(02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。 
(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

2. 拓扑排序

/*
 * 拓扑排序
 *
 * 返回值：
 *     -1 -- 失败(由于内存不足等原因导致)
 *      0 -- 成功排序，并输入结果
 *      1 -- 失败(该有向图是有环的)
 */
int ListDG::topologicalSort()
{
    int i,j;
    int index = 0;
    int head = 0;           // 辅助队列的头
    int rear = 0;           // 辅助队列的尾
    int *queue;             // 辅组队列
    int *ins;               // 入度数组
    char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
    ENode *node;

    ins   = new int[mVexNum];
    queue = new int[mVexNum];
    tops  = new char[mVexNum];
    memset(ins, 0, mVexNum*sizeof(int));
    memset(queue, 0, mVexNum*sizeof(int));
    memset(tops, 0, mVexNum*sizeof(char));

    // 统计每个顶点的入度数
    for(i = 0; i < mVexNum; i++)
    {
        node = mVexs[i].firstEdge;
        while (node != NULL)
        {
            ins[node->ivex]++;
            node = node->nextEdge;
        }
    }

    // 将所有入度为0的顶点入队列
    for(i = 0; i < mVexNum; i ++)
        if(ins[i] == 0)
            queue[rear++] = i;          // 入队列

    while (head != rear)                // 队列非空
    {
        j = queue[head++];              // 出队列。j是顶点的序号
        tops[index++] = mVexs[j].data;  // 将该顶点添加到tops中，tops是排序结果
        node = mVexs[j].firstEdge;      // 获取以该顶点为起点的出边队列

        // 将与"node"关联的节点的入度减1；
        // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
        while(node != NULL)
        {
            // 将节点(序号为node->ivex)的入度减1。
            ins[node->ivex]--;
            // 若节点的入度为0，则将其"入队列"
            if( ins[node->ivex] == 0)
                queue[rear++] = node->ivex;  // 入队列

            node = node->nextEdge;
        }
    }

    if(index != mVexNum)
    {
        cout << "Graph has a cycle" << endl;
        delete queue;
        delete ins;
        delete tops;
        return 1;
    }

    // 打印拓扑排序结果
    cout << "== TopSort: ";
    for(i = 0; i < mVexNum; i ++)
        cout << tops[i] << " ";
    cout << endl;

    delete queue;
    delete ins;
    delete tops;

    return 0;
}