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

1.1. 偏序

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

通俗解釋：自然數之間的"大于等于"是一個偏序關系，例如自然數的一個子集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，但關系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. 全序

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

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

1.3. 算法的穩定性

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

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

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

說明：本文圖的構建方法及DFS算法可以參考 BFS,DFS 算法原理及js實現

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

2.1. 拓撲排序定義

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

3.1. 算法原理

對于一個有向無環AOV(頂點表示活動，邊表示優先關系)圖，我們重復執行以下兩個步驟，直到不存在入度為0的頂點為止

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

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

這樣得到的序列就是該圖的拓撲排序，如果途中有環，則輸出的頂點的數目小于圖中節點的數目

3.2. 算法描述

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

3.3. 算法的js實現

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

//數據結構 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節點的位置
    this.sibling = null;
    this.w = null; //保存邊的權值
}

//數據結構 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.dict = {}; //字典 用來映射標節點的識符和數組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進來的已經具備了邊的關系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創建圖的 節點
    initVertex: function(vertexs) {
        //創建節點并初始化節點屬性 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;
        }
    },
    //建立圖中 邊 的關系
    initEdge: function(edges) {
        for (let field in edges) {
            let index = this.dict[field]; //從字典表中找出節點在 graph 中的位置
            let vertex = this.graph[index]; //獲取節點
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創建鏈表，返回鏈表的第一個節點
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節點 用在數組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設置節點的入度
    edgeNode.w = edges[index].w; //邊的權值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實現 回溯
    return edgeNode;
}
// a內褲 b襪子 c手表 d褲子 e鞋 f腰帶 g襯衣 h領帶 i 夾克
vertexs = [{value: "a",    data: "內褲"}, {value: "b",    data: "襪子"}, 
{value: "c",data: "手表"}, {value: "d",    data: "褲子"}, 
{value: "e",data: "鞋"}, {value: "f",    data: "腰帶"}, 
{value: "g",data: "襯衣"}, {value: "h",    data: "領帶"}, 
{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 = []; //用來存放已經排好序的頂點
    //初始化set 將圖中所有入度為0的節點加入到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);

運行結果

4.1. 算法原理

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

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

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

4.2. js實現

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

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

//數據結構 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節點的位置
    this.sibling = null;
    this.w = null; //保存邊的權值
}

//數據結構 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.dict = {}; //字典 用來映射標節點的識符和數組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進來的已經具備了邊的關系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創建圖的 節點
    initVertex: function(vertexs) {
        //創建節點并初始化節點屬性 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;
        }
    },
    //建立圖中 邊 的關系
    initEdge: function(edges) {
        for (let field in edges) {
            let index = this.dict[field]; //從字典表中找出節點在 graph 中的位置
            let vertex = this.graph[index]; //獲取節點
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創建鏈表，返回鏈表的第一個節點
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節點 用在數組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設置節點的入度
    edgeNode.w = edges[index].w; //邊的權值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實現 回溯
    return edgeNode;
}
// a內褲 b襪子 c手表 d褲子 e鞋 f腰帶 g襯衣 h領帶 i 夾克
vertexs = [{value: "a", data: "內褲"}, {value: "b",   data: "襪子"}, 
{value: "c",data: "手表"}, {value: "d",   data: "褲子"}, 
{value: "e",data: "鞋"}, {value: "f",    data: "腰帶"}, 
{value: "g",data: "襯衣"}, {value: "h",   data: "領帶"}, 
{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; //設置完成時間
        l.unshift(v); //拓撲排序的次序與頂點的完成時間恰好相反
    }
    console.log(l)
}

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

運行結果