摘要：但是一個偏序關(guān)系，如果我們默認，先出現(xiàn)的排在前面，那么我們就能比較，的關(guān)系了。對于算法的每個節(jié)點，我們都有一個發(fā)現(xiàn)時間，一個訪問時間，當運行完成時，對于圖中的任意一條邊，都有所以拓撲排序的次序與頂點的完成時間恰好相反。

1.1. 偏序

設(shè)R是集合A上的一個二元關(guān)系，若R滿足下列三個性質(zhì)則稱R為A上的偏序關(guān)系
自反性：對任意x∈A，有∈R
反對稱性：對任意的x,y∈A,如果∈R,且∈R,則必有x=y
傳遞性：對任意x,y,z∈A，若∈R,∈R,則必有∈R

通俗解釋：自然數(shù)之間的"大于等于"是一個偏序關(guān)系，例如自然數(shù)的一個子集A={1,2,3}
"大于等于"的一個子集R={<1,1>,<2,2>,<3,3>,<3,2>,<2,1>,<3,1>}對于自反的解釋是1=1,2=2,3=3;對于反對稱性，<3,2>,<2,1>,<3,1>∈R，但關(guān)系R中不存在元素<2,3>,<1,2><1,3>因為2<3,1<2,1<3，對于傳遞<3,2>,<2,1>∈R即3>2,2>1所以3>1即<3,1>∈R

1.2. 全序

全序是偏序的一個子集，即集合中任意兩個元素之間都有明確的"序"的關(guān)系也就是下面的性質(zhì)
完全性：集合中任意兩個元素之間都有明確的"序"的關(guān)系，由此可見完全性包含了自反性，任意就包含了元素和元素自己

通俗解釋：是偏序但不是全序，設(shè)集合A={1,2,3,b},b=2i+1;由于b是一個復(fù)數(shù)，所以其它的三個元素都不可以和它來比較大小

1.3. 算法的穩(wěn)定性

如果我們要對下列數(shù)組的元素按照index的大小進行排序 [{id:a,index:1},{id:b,index:1},{id:c,index:2}]，我們設(shè)第一個為A，第二個為B,第三個為C, 我們應(yīng)該如何確定A和B之間的順序呢？
由于A，B的index值相同，但A和B確實是不同的元素，因此我們無法確定他們的先后順序，即A和B不可比較，所以在A，B，C三個元素組成的關(guān)系不具備全序關(guān)系。但是一個偏序關(guān)系，如果我們默認，先出現(xiàn)的排在前面，那么我們就能比較A，B的關(guān)系了。我們排序就有C,A,B

穩(wěn)定的算法：是對于存在上述情況的元素總能按照元素出現(xiàn)的先后順序排列的算法

不穩(wěn)定的算法：是對于上述情況，不能保證先出現(xiàn)的排在前面由此我們說，直接插入排序，冒泡排序，歸并排序，基數(shù)排序是穩(wěn)定的而shell排序，堆排序，快速排序直接選擇排序是不穩(wěn)定的

說明：本文圖的構(gòu)建方法及DFS算法可以參考 BFS,DFS 算法原理及js實現(xiàn)

我們每天早上起床后穿衣的過程可以分為很多步驟，例如，穿內(nèi)褲，穿褲子，穿內(nèi)褲必須在穿褲子之前，同樣的穿襪子必須在穿鞋子之前等等，戴手表和其它的任何一個動作之間都沒有明顯的關(guān)系，因此放在這個線性序列中的哪里都無所謂

2.1. 拓撲排序定義

對于一個有向無環(huán)圖G來說，拓撲排序就是對圖G中的所有節(jié)點的一次線性排序，該排序滿足如下條件，如果圖G中包含邊(u,v)，則節(jié)點u一定在v的前面，可以將拓撲排序看作是將圖的所有節(jié)點在一條直線上水平排開

3.1. 算法原理

對于一個有向無環(huán)AOV(頂點表示活動，邊表示優(yōu)先關(guān)系)圖，我們重復(fù)執(zhí)行以下兩個步驟，直到不存在入度為0的頂點為止

(1)先擇一個入度為0的頂點并輸出

(2)從圖中刪除由該節(jié)點發(fā)出的所有邊

這樣得到的序列就是該圖的拓撲排序，如果途中有環(huán)，則輸出的頂點的數(shù)目小于圖中節(jié)點的數(shù)目

3.2. 算法描述

L一個用來存放已排序頂點的List
S一個用來存放如度為0的頂點List  
當S不為空時執(zhí)行循環(huán)執(zhí)行以下步驟
    從S中移除一個頂點(沒有順序要求，隨意移除)n
    將n插入到L中
    循環(huán)遍歷從n發(fā)出的邊，對于所有的孩子節(jié)點m
        移除邊
        如果m的入度為0，則將m放入S中
如果循環(huán)結(jié)束后圖中還有邊則說明圖中有環(huán)
否則L是拓撲排序的結(jié)果

3.3. 算法的js實現(xiàn)

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-頂點
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = this.INFINITY; //初始為 無窮大
    this.edges = null; //由頂點發(fā)出的所有邊
    this.value = null; //節(jié)點的標識
    this.data = null; //節(jié)點的數(shù)據(jù)
    this.incoming = 0; //節(jié)點的入度
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 為 null 時表示無窮大
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點的位置
    this.sibling = null;
    this.w = null; //保存邊的權(quán)值
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.dict = {}; //字典 用來映射標節(jié)點的識符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點并初始化節(jié)點屬性 value
        for (let value of vertexs) {
            let vertex = Vertex();
            vertex.value = value.value;
            vertex.data = value.data;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.dict[this.graph[i].value] = i;
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: function(edges) {
        for (let field in edges) {
            let index = this.dict[field]; //從字典表中找出節(jié)點在 graph 中的位置
            let vertex = this.graph[index]; //獲取節(jié)點
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創(chuàng)建鏈表，返回鏈表的第一個節(jié)點
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節(jié)點 用在數(shù)組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設(shè)置節(jié)點的入度
    edgeNode.w = edges[index].w; //邊的權(quán)值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實現(xiàn) 回溯
    return edgeNode;
}
// a內(nèi)褲 b襪子 c手表 d褲子 e鞋 f腰帶 g襯衣 h領(lǐng)帶 i 夾克
vertexs = [{value: "a",    data: "內(nèi)褲"}, {value: "b",    data: "襪子"}, 
{value: "c",data: "手表"}, {value: "d",    data: "褲子"}, 
{value: "e",data: "鞋"}, {value: "f",    data: "腰帶"}, 
{value: "g",data: "襯衣"}, {value: "h",    data: "領(lǐng)帶"}, 
{value: "i",data: "夾克"}];

var edges = {
    a: [{id: "d", w: 1 }, {id: "e", w: 1 }],
    b: [{id: "e", w: 1}],
    c: [],
    d: [{id: "e", w: 1 }, {id: "f", w: 1 }],
    e: [],
    f: [{id: "i", w: 1}],
    g: [{id: "f", w: 1 }, {id: "h", w: 1 }],
    h: [{id: "i", w: 1}],
    i: []
}

//kahn算法
function kahn(g) {
    let s = []; //用于存放入度為0的頂點
    let l = []; //用來存放已經(jīng)排好序的頂點
    //初始化set 將圖中所有入度為0的節(jié)點加入到set中
    for(let v of g.graph) {
        if(v.incoming==0)
            s.push(v);
    }
    while(s.length > 0) {
        let u = s.shift();
        l.push(u);
        if (u.edges == null) continue;
        let sibling = u.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            n.incoming = n.incoming - 1; //刪除邊
            if(n.incoming == 0)    s.push(n); //入度為0的放入s
            sibling = sibling.sibling;
        }
    }
    return l;
}

var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);
var r = kahn(g);
console.log(r);

運行結(jié)果

4.1. 算法原理

原理：拓撲排序的次序與頂點的完成時間恰好相反

對于拓撲排序，我們要做的是保證對于任意一條邊（u,v），節(jié)點u一定出現(xiàn)在節(jié)點v前面。
對于DFS算法的每個節(jié)點，我們都有一個發(fā)現(xiàn)時間d，一個訪問時間f，當DFS運行完成時，對于圖中的任意一條邊（u,v），都有 u.f>v.f,所以拓撲排序的次序與頂點的完成時間恰好相反。

當DFS在圖上運行時，探索到任意一條邊（u,v）時，u為灰色，所以v要么是白色，要么是黑色，如果v是白色，則v一定早于u被訪問，即 u.f>v.f，當v為黑色時，此時v已經(jīng)被訪問過，而u還為灰色，即u沒有被訪問，所以v依然早于u被訪問，仍有 u.f>v.f，由此可見上述結(jié)論成立

4.2. js實現(xiàn)

基于以上結(jié)論，我們用DFS實現(xiàn)拓撲排序，只需要在節(jié)點 的f被設(shè)置值即節(jié)點被訪問后，將其加入一個后進先出隊列中（調(diào)用unshift方法始終向數(shù)組的頭部添加新元素）L中，當DFS運行結(jié)束后，L中的元素就是經(jīng)過拓撲排序的結(jié)果

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-頂點
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = this.INFINITY; //初始為 無窮大
    this.edges = null; //由頂點發(fā)出的所有邊
    this.value = null; //節(jié)點的標識
    this.data = null; //節(jié)點的數(shù)據(jù)
    this.incoming = 0;
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 為 null 時表示無窮大
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點的位置
    this.sibling = null;
    this.w = null; //保存邊的權(quán)值
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.dict = {}; //字典 用來映射標節(jié)點的識符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點并初始化節(jié)點屬性 value
        for (let value of vertexs) {
            let vertex = Vertex();
            vertex.value = value.value;
            vertex.data = value.data;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.dict[this.graph[i].value] = i;
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: function(edges) {
        for (let field in edges) {
            let index = this.dict[field]; //從字典表中找出節(jié)點在 graph 中的位置
            let vertex = this.graph[index]; //獲取節(jié)點
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創(chuàng)建鏈表，返回鏈表的第一個節(jié)點
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節(jié)點 用在數(shù)組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設(shè)置節(jié)點的入度
    edgeNode.w = edges[index].w; //邊的權(quán)值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實現(xiàn) 回溯
    return edgeNode;
}
// a內(nèi)褲 b襪子 c手表 d褲子 e鞋 f腰帶 g襯衣 h領(lǐng)帶 i 夾克
vertexs = [{value: "a", data: "內(nèi)褲"}, {value: "b",   data: "襪子"}, 
{value: "c",data: "手表"}, {value: "d",   data: "褲子"}, 
{value: "e",data: "鞋"}, {value: "f",    data: "腰帶"}, 
{value: "g",data: "襯衣"}, {value: "h",   data: "領(lǐng)帶"}, 
{value: "i",data: "夾克"}];

var edges = {
    a: [{id: "d", w: 1 }, {id: "e", w: 1 }],
    b: [{id: "e", w: 1}],
    c: [],
    d: [{id: "e", w: 1 }, {id: "f", w: 1 }],
    e: [],
    f: [{id: "i", w: 1}],
    g: [{id: "f", w: 1 }, {id: "h", w: 1 }],
    h: [{id: "i", w: 1}],
    i: []
}

function DFS(g) {
    let t = 0;
    let l =[];
    for (let v of g.graph) {
        if (v.color == v.WHITE) DFSVisit(g, v);
    }
    function DFSVisit(g, v) {
        t = t + 1;
        v.d = t;
        v.color = v.GRAY;
        let sibling = v.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.pi = v;
                DFSVisit(g, n); //先縱向找
            }
            sibling = sibling.sibling; //利用遞歸的特性來回溯
        }
        v.color = v.BLACK;
        t = t + 1;
        v.f = t; //設(shè)置完成時間
        l.unshift(v); //拓撲排序的次序與頂點的完成時間恰好相反
    }
    console.log(l)
}

var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);
DFS(g);

運行結(jié)果