基本的图算法:拓扑排序

2016年01月04日 原创
关键词: C++ 数据结构 算法 算法导论
摘要 本文阐述如何使用深度优先搜索来对有向无环图进行拓扑排序。

对于一个有向无环图G=(V,E)来说,其拓扑排序是G中所有节点的一种线性次序,该次序满足如下条件:如果图G包含边(u,v),则节点u在拓扑排序中处于节点v的前面(如果图G包含环路,则不可能排出一个线性次序)。可以将图的拓扑排序看做是将图的所有节点在一条水平线上排开,图的所有有向边都从左指向右。因此,拓扑排序和我们一般来说的按照大小来进行计算的排序是不同的。

下面是拓扑排序的伪代码:

TOPOLOGICAL-SORT(G)
        call DFS(G) to compute finishing times v.f for each vertex v //对G的每一个顶点v计算结束遍历的次数v.f

        as each vertex is finished, insert it onto the front of a linked list //把v.f存储起来

        return the linked list of vertices //返回v.f的集合

下面的c++程序代码对下面的图进行的拓扑排序

下面是C++程序代码:

#include<iostream>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
string nodeNames[] = {
     "C1", "C2", "C3", "C4", "C5"
};
bool visited[5];
int graph[][5] = {
    { 0, 0, 1, 0, 0 },
    { 0, 0, 1, 0, 0 },
    { 0, 0, 0, 1, 1 },
    { 0, 0, 0, 0, 1 },
    { 0, 0, 0, 0, 0 }
};

int dfs(int startPos) {
    int times = 0;
    memset(visited, false, sizeof(visited));
    stack<int> open;
    open.push(startPos);
    times = 0;
    while (open.size() > 0) {
        int curr = open.top();
        open.pop();
        if (visited[curr]) continue;

        for (int i = 0; i < 5; i++) {
            if (graph[curr][i] == 1) {
                open.push(i);
            }
        }
        visited[curr] = true;
        times++;
    }
    return times;
}
class node{
public:
    int pos, times;
    node(int pos = 0, int times = 0) :pos(pos), times(times){}
    bool operator <(const node& n) {
        return times < n.times;
    }
};
int main() {
    vector<node> result;
    int sortResult[5];
    for (int i = 0; i < 5; i++) {
        result.push_back(node(i,dfs(i)));
    }
    for (int i = 0; i < 5; i++) {
        cout << nodeNames[result[i].pos] << endl;
    }

    return 0;
}

运行结果: