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

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

2.1. 拓?fù)渑判蚨x

對(duì)于一個(gè)有向無環(huán)圖G來說，拓?fù)渑判蚓褪菍?duì)圖G中的所有節(jié)點(diǎn)的一次線性排序，該排序滿足如下條件，如果圖G中包含邊(u,v)，則節(jié)點(diǎn)u一定在v的前面，可以將拓?fù)渑判蚩醋魇菍D的所有節(jié)點(diǎn)在一條直線上水平排開

3.1. 算法原理

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

(1)先擇一個(gè)入度為0的頂點(diǎn)并輸出

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

這樣得到的序列就是該圖的拓?fù)渑判颍绻局杏协h(huán)，則輸出的頂點(diǎn)的數(shù)目小于圖中節(jié)點(diǎn)的數(shù)目

3.2. 算法描述

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

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

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

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    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 = {}; //字典 用來映射標(biāo)節(jié)點(diǎn)的識(shí)符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 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é)點(diǎn)在 graph 中的位置
            let vertex = this.graph[index]; //獲取節(jié)點(diǎn)
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設(shè)置節(jié)點(diǎn)的入度
    edgeNode.w = edges[index].w; //邊的權(quán)值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實(shí)現(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的頂點(diǎn)
    let l = []; //用來存放已經(jīng)排好序的頂點(diǎn)
    //初始化set 將圖中所有入度為0的節(jié)點(diǎn)加入到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);

運(yùn)行結(jié)果

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

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    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 = {}; //字典 用來映射標(biāo)節(jié)點(diǎn)的識(shí)符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 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é)點(diǎn)在 graph 中的位置
            let vertex = this.graph[index]; //獲取節(jié)點(diǎn)
            vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, this.graph);
        }
    }
}

//創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
function createLink(index, len, edges, dict, vertexs) {
    if (index >= len) return null;
    let edgeNode = Edge();
    edgeNode.index = dict[edges[index].id]; //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
    vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //設(shè)置節(jié)點(diǎn)的入度
    edgeNode.w = edges[index].w; //邊的權(quán)值
    edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通過遞歸實(shí)現(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è)置完成時(shí)間
        l.unshift(v); //拓?fù)渑判虻拇涡蚺c頂點(diǎn)的完成時(shí)間恰好相反
    }
    console.log(l)
}

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