JavaScript数据结构——图的实现

  • 时间:
  • 浏览:0
  • 来源:大发快3_快3在线稳定计划_大发快3在线稳定计划

  在计算机科学中,图是两种网络形态学 的抽象模型,它是一组由边连接的顶点组成。有另有一有三个小 图G = (V, E)由以下元素组成:

  • V:一组顶点
  • E:一组边,连接V中的顶点

  下图表示了有另有一有三个小 图的形态学 :

  在介绍咋样用JavaScript实现图以前,当他们 儿先介绍有些和图相关的术语。

  如上图所示,由第两根边连接在同去的顶点称为相邻顶点,A和B是相邻顶点,A和D是相邻顶点,A和C是相邻顶点......A和E是不相邻顶点。有另有一有三个小 顶点的是其相邻顶点的数量,A和其它有另有一有三个小 顶点相连,好多好多 A的度为3,E和其它有另有一有三个小 顶点相连,好多好多 E的度为2......路径是一组相邻顶点的连续序列,如上图饱饱含 路径ABEI、路径ACDG、路径ABE、路径ACDH等。简单路径要求路径中不饱饱含 重复的顶点,原应着着将的最后有另有一有三个小 顶点打上去,它也是有另有一有三个小 简单路径。之类路径ADCA是有另有一有三个小 环,它全是有另有一有三个小 简单路径,原应着着将路径中的最后有另有一有三个小 顶点A打上去,不到它好多好多 我有另有一有三个小 简单路径。原应着着图中不发生环,则称该图是无环的。原应着着图中任何有另有一有三个小 顶点间都发生路径,则该图是连通的,如上图好多好多 我有另有一有三个小 连通图。原应着着图的边不到方向,则该图是无向图,上图所示为无向图,反之则称为有向图,下图所示为有向图:

  在有向图中,原应着着有另有一有三个小 顶点间在双向上都发生路径,则称这有另有一有三个小 顶点是强连通的,如上图中C和D是强连通的,而A和B是非强连通的。原应着着有向图中的任何有另有一有三个小 顶点间在双向上都发生路径,则该有向图是强连通的,非强连通的图也称为稀疏图

  此外,图还可算是加权的。前面当他们 儿看到的图全是未加权的,下图为有另有一有三个小 加权的图:

  还可否想象一下,前面当他们 儿介绍的树和链表也属于图的两种特殊形式。图在计算机科学中的应用十分广泛,之类当他们 儿还可否搜索图中的有另有一有三个小 特定顶点或第两根特定的边,原应着着寻找有另有一有三个小 顶点间的路径以及最短路径,检测图中算是发生环等等。

  发生多种不同的办法来实现图的数据形态学 ,下面介绍几种常用的办法。

邻接矩阵

  在邻接矩阵中,当他们 儿用有另有一有三个小 二维数组来表示图中顶点之间的连接,原应着着有另有一有三个小 顶点之间发生连接,则这有另有一有三个小 顶点对应的二维数组下标的元素的值为1,好多好多 我为0。下图是用邻接矩阵办法表示的图:

  原应着着是加权的图,当他们 儿还可否将邻接矩阵中二维数组里的值1改成对应的加权数。邻接矩阵办法发生有另有一有三个小 缺点,原应着着图是非强连通的,则二维数组中会有好多好多 的0,这表示当他们 儿使用了好多好多 的存储空间来表示根本不发生的边。好多好多 我缺点好多好多 我当图的顶点发生改变时,对于二维数组的修改会变得不太灵活。

邻接表

  图的另外两种实现办法是邻接表,它是对邻接矩阵的两种改进。邻接表由图中每个顶点的相邻顶点列表所组成。如下图所示,当他们 儿还可否用数组、链表、字典或散列表来表示邻接表。

关联矩阵

  当他们 儿还还可否用关联矩阵来表示图。在关联矩阵中,矩阵的行表示顶点,列表示边。关联矩阵通常用于边的数量比顶点多的状况下,以节省存储空间。如下图所示为关联矩阵办法表示的图:

  下面当他们 儿重点看下咋样用邻接表的办法表示图。当他们 儿的Graph类的骨架如下,它用邻接表办法来实现无向图:

class Graph {
    constructor () {
        this.vertices = []; // 用来存放图中的顶点
        this.adjList = new Dictionary(); // 用来存放图中的边
    }

    // 向图中打上去有另有一有三个小

新顶点
    addVertex (v) {}

    // 向图中打上去a和b有另有一有三个小

顶点之间的边
    addEdge (a, b) {}
}

  在Graph类中,当他们 儿用数组vertices来保存图中的所有顶点,用字典(请参考《JavaScript数据形态学 ——字典和散列表的实现》一文中的Dictionary类)adjList来保存图中每有另有一有三个小 顶点到相邻顶点的关系列表,在字典中,顶点被作为键值。请参考前面当他们 儿给出的邻接表的示意图。好多好多 我在Graph类中,当他们 儿提供有另有一有三个小 办法,办法addVertex()用来向图中打上去有另有一有三个小 新顶点,办法addEdge()用来向图中打上去给定的顶点a和顶点b之间的边。让当他们 儿来看下这有另有一有三个小 办法的实现。

addVertex (v) {
    if (!this.vertices.includes(v)) {
        this.vertices.push(v);
        this.adjList.set(v, []);
    }
}

  要打上去有另有一有三个小 新顶点,首不难 判断该顶点在图中算是原应着着发生了,原应着着原应着着发生则不到打上去。原应着着不发生,就在vertices数组中打上去有另有一有三个小 新元素,好多好多 我在字典adjList中打上去有另有一有三个小 以该顶点作为key的新元素,值为空数组。

addEdge (a, b) {
    // 原应着着图中不到顶点a,先打上去顶点a
    if (!this.adjList.has(a)) {
        this.addVertex(a);
    }
    // 原应着着图中不到顶点b,先打上去顶点b
    if (!this.adjList.has(b)) {
        this.addVertex(b);
    }

    this.adjList.get(a).push(b); // 在顶点a中打上去指向顶点b的边
    this.adjList.get(b).push(a); // 在顶点b中打上去指向顶点a的边
}

  addEdge()办法也很简单,首不难 确保给定的有另有一有三个小 顶点a和b在图中都要发生,原应着着不发生,则调用addVertex()办法进行打上去,好多好多 我分别在字典中找到键值为顶点a和键值为顶点b的元素,在对应的值中打上去有另有一有三个小 新元素。

  下面是Graph类的详细代码,其中的toString()办法是为了当他们 儿测试用的,它的发生全是都要的。

  对于本文一刚开始了给出的图,当他们 儿打上去下面的测试用例:

let graph = new Graph();
let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
myVertices.forEach((v) => {
    graph.addVertex(v);
});
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());

  下面是测试结果:

A -> B C D 
B -> A E F 
C -> A D G 
D -> A C G H 
E -> B I 
F -> B 
G -> C D 
H -> D 
I -> E 

  还可否看到,与示意图是相符合的。

  和树之类,当他们 儿也还可否对图进行遍历,以访问图中的所有顶点。图的遍历办法分为两种:广度优先(Breadth-First Search,BFS)和深层优先(Depth-First Search,DFS)。对图的遍历还可否用来寻找特定的顶点或有另有一有三个小 顶点之间的最短路径,以及检查图算是连通、图中算是饱含 环等。

  在接下来要实现的算法中,当他们 儿按照如下的约定对图中的顶点进行遍历,每个顶点最多访问两次:

  • 白色:表示该顶点未被访问。
  • 灰色:表示该顶点被访问过,但未被探索。
  • 黑色:表示该顶点被访问好多好多 我被探索过。

广度优先

  广度优先算法会从指定的第有另有一有三个小 顶点刚开始了遍历图,先访问这个 顶点的所有相邻顶点,好多好多 我再访问哪几种相邻顶点的相邻顶点,以此类推。最终,广度优先算法会先广后深地访问图中的所有顶点。下面是广度优先遍历的示意图:

  原应着着当他们 儿采用邻接表的办法来存储图的数据,对于图的每个顶点,全是有另有一有三个小 字典与之对应,字典的键值为顶点的值,字典的内容为与该顶点相邻的顶点列表。基于这个 数据形态学 ,当他们 儿还可否考虑将所有顶点的邻接顶点存入队列,好多好多 我依次出理 队列中的顶点。下面是具体的遍历步骤:

  1. 将刚开始了顶点存入队列。
  2. 遍历刚开始了顶点的所有邻接顶点,原应着着哪几种邻接顶点不到被访问过(颜色为白色),则将它们标记为被访问(颜色为灰色),好多好多 我加入队列。
  3. 将刚开始了顶点标记为被出理 (颜色为黑色)。
  4. 循环出理 队列中的顶点,直到队列为空。

  下面是该算法的具体实现:

let Colors = {
    WHITE: 0,
    GREY: 1,
    BLACK: 2
};

let initializeColor = vertices => {
    let color = {};
    vertices.forEach(v => color[v] = Colors.WHITE);
    return color;
};

let breadthFirstSearch = (graph, startVertex, callback) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let queue = new Queue();

    queue.enqueue(startVertex);

    while (!queue.isEmpty()) {
        let u = queue.dequeue();
        adjList.get(u).forEach(n => {
            if (color[n] === Colors.WHITE) {
                color[n] = Colors.GREY;
                queue.enqueue(n);
            }
        });


        color[u] = Colors.BLACK;
        if (callback) callback(u);
    }
};

  breadthFirstSearch()办法接收有另有一有三个小 graph对象,图的数据通过该对象传入。参数startVertex指定了遍历的起始顶点。回调函数callback规定了要咋样出理 被遍历到的顶点。

  首先通过initializeColor()函数将所有的顶点标记为未被访问过(颜色为白色),哪几种颜色保发生以顶点值为key的color对象中。图的vertices和adjList属性还可否通过getVertices()和getAdjList()办法得到,好多好多 我构造有另有一有三个小 队列queue(有关队列类Queue请参考《JavaScript数据形态学 ——队列的实现与应用》),按照中间描述的步骤对图的顶点进行遍历。

  在前面当他们 儿给出的测试用例的基础上,打上去下面的代码,来看看breadthFirstSearch()办法的执行结果:

breadthFirstSearch(graph, 'A', value => console.log(`visited vertex: ${value}`));

  参数graph为前面测试用例中Graph类的实例,也好多好多 我当他们 儿用来保存图的数据的对象,'A'被作为遍历的起始顶点,在回调函数中,打印一行文本,用来展示顶点被遍历的顺序。下面是测试结果:

visited vertex: A
visited vertex: B
visited vertex: C
visited vertex: D
visited vertex: E
visited vertex: F
visited vertex: G
visited vertex: H
visited vertex: I

  尝试将'I'作为起始顶点,看看执行结果:

visited vertex: I
visited vertex: E
visited vertex: B
visited vertex: A
visited vertex: F
visited vertex: C
visited vertex: D
visited vertex: G
visited vertex: H

  为了方便理解,当他们 儿将顶点I塞进 最中间。从顶点I刚开始了,首先遍历到的是它的相邻顶点E,好多好多 我是E的相邻顶点B,其次是B的相邻顶点A和F,A的相邻顶点C和D,C的相邻顶点G(D原应着着被遍历过了),最后是D的相邻顶点H(C和G原应着着被遍历过了)。

寻找最短路径

  前面展示了广度优先算法的工作原理,当他们 儿还可否使用它做更多的事情,之类在有另有一有三个小 图G中,从顶点v刚开始了到其它所有顶点间的最短距离。当他们 儿考虑一下咋样用BFS来实现寻找最短路径。

  假设有另有一有三个小 相邻顶点间的距离为1,从顶点v刚开始了,在其路径上每经过有另有一有三个小 顶点,距离加1。下面是对breadthFirstSearch()办法的改进,用来返回从起始顶点刚开始了到其它所有顶点间的距离,以及所有顶点的前置顶点。

let BFS = (graph, startVertex) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let queue = new Queue();
    let distances = {};
    let predecessors = {};

    queue.enqueue(startVertex);

    // 初始化所有顶点的距离为0,前置节点为null
    vertices.forEach(v => {
        distances[v] = 0;
        predecessors[v] = null;
    });

    while (!queue.isEmpty()) {
        let u = queue.dequeue();
        adjList.get(u).forEach(n => {
            if (color[n] === Colors.WHITE) {
                color[n] = Colors.GREY;
                distances[n] = distances[u] + 1;
                predecessors[n] = u;
                queue.enqueue(n);
            }
        });


        color[u] = Colors.BLACK;
    }

    return {distances, predecessors};
};

  在BFS()办法中,当他们 儿定义了有另有一有三个小 对象distances和predecessors,用来保存从起始顶点出发到其它所有顶点的距离以及哪几种顶点的前置顶点。BFS()办法不都要callback回调函数,原应着着它会自行输出最终结果。与breadthFirstSearch()办法的逻辑之类,只不过在刚开始了的以前将所有顶点的距离初始化为0,前置顶点初始化为null,好多好多 我在遍历的过程中,重新设置顶点的distances值和predecessors值。当他们 儿仍然将顶点A作为起始顶点,来看看测试结果:

console.log(BFS(graph, 'A'));
{
  distances: { A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 },
  predecessors: {
    A: null,
    B: 'A',
    C: 'A',
    D: 'A',
    E: 'B',
    F: 'B',
    G: 'C',
    H: 'D',
    I: 'E'
  }
}

  如你所见,distances为从顶点A刚开始了到其它所有顶点的最短距离(相邻顶点间的距离为1),predecessors记录了所有顶点的前置顶点。以BFS()办法的返回结果为基础,通过下面的代码,当他们 儿还可否得出从顶点A刚开始了到其它所有顶点的最短路径:

let shortestPathA = BFS(graph, 'A');
let startVertex = 'A';
myVertices.forEach(v => {
    let path = new Stack();
    for (let v2 = v; v2 !== startVertex; v2 = shortestPathA.predecessors[v2]) {
        path.push(v2);
    }

    path.push(startVertex);
    let s = path.pop();
    while (!path.isEmpty()) {
        s += ` - ${path.pop()}`;
    }

    console.log(s);
});

  其中的Stack类还可否参考《JavaScript数据形态学 ——栈的实现与应用》。下面是对应的执行结果:

A
A - B
A - C
A - D
A - B - E
A - B - F
A - C - G
A - D - H
A - B - E - I

   以上当他们 儿说的全是未加权的图,对于加权的图,广度优先算法并全是最最少的。下面给出了另外几种最短路径算法:

Dijkstra - 寻找从指定顶点到其它所有顶点的最短路径的贪心算法。

Floyd-Warshall - 计算图中所有最短路径的动态规划算法。

Kruskal - 求解加权无向连通图的最小生成树(MST)的贪心算法。

Prime - 求解加权无向连通图的最小生成树(MST)的贪心算法。

深层优先

  深层优先算法从图的第有另有一有三个小 顶点刚开始了,沿着这个 顶点的第两根路径递归查找到最后有另有一有三个小 顶点,好多好多 我返回并探查路径上的其它路径,直到所有路径都被访问到。最终,深层优先算法会先深后广地访问图中的所有顶点。下面是深层优先遍历的示意图:

  当他们 儿仍然采用和广度优先算法一样的思路,一刚开始了将所有的顶点初始化为白色,好多好多 我沿着路径递归探查其余顶点,当顶点被访问过,将颜色改为灰色,原应着着顶点被探索过(出理 过),则将颜色改为黑色。下面是深层优先算法的具体实现:

let depthFirstSearchVisit = (u, color, adjList, callback) => {
    color[u] = Colors.GREY;
    if (callback) callback(u);

    adjList.get(u).forEach(n => {
        if (color[n] === Colors.WHITE) {
            depthFirstSearchVisit(n, color, adjList, callback);
        }
    });

    color[u] = Colors.BLACK;
};

let depthFirstSearch = (graph, callback) => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);

    vertices.forEach(v => {
        if (color[v] === Colors.WHITE) {
            depthFirstSearchVisit(v, color, adjList, callback);
        }
    });
};

  具体执行步骤为:

  1. 将图中所有顶点的颜色初始化为白色。
  2. 遍历顶点,此时A作为第有另有一有三个小 顶点,它的颜色为白色,于是调用函数depthFirstSearchVisit(),并将顶点A、color、graph.adjList作为参数传入。
  3. 在depthFirstSearchVisit()函数实物,原应着着顶点A被访问过了,好多好多 将颜色设置为灰色,并执行callback回调函数(原应着着发生),好多好多 我遍历A的邻接顶点B、C、D。
  4. B未被访问过,颜色为白色,好多好多 将B作为参数递归调用depthFirstSearchVisit()函数。B设置为灰色,callback('B')。遍历B的邻接节点E和F。
  5. E未被访问过,颜色为白色,好多好多 将E作为参数递归调用depthFirstSearchVisit()函数。E设置为灰色,callback('E')。遍历E的邻接节点I。
  6. I未被访问过,颜色为白色,好多好多 将I作为参数递归调用depthFirstSearchVisit()函数。I设置为灰色,callback('I')。I不到邻接节点,好多好多 我将I设置为黑色。递归返回到5。
  7. E不到其它邻接节点,将E设置为黑色。递归返回到4。
  8. 遍历B的好多好多 我邻接节点F,F未被访问过,颜色为白色,好多好多 将F作为参数递归调用depthFirstSearchVisit()函数。F设置为灰色,callback('F')。F不到邻接节点,好多好多 我将F设置为黑色。递归返回到4。
  9. B的所有邻接节点都被访问过了,将B设置为黑色。递归返回到3。
  10. 访问A的第三个小邻接节点C,C未被访问过,颜色为白色,好多好多 将C作为参数递归调用depthFirstSearchVisit()函数。C设置为灰色,callback('C')。遍历C的邻接节点D、G。
  11. D未被访问过,颜色为白色,好多好多 将D作为参数递归调用depthFirstSearchVisit()函数。D设置为灰色,callback('D')。遍历D的邻接节点G和H。
  12. G未被访问过,颜色为白色,好多好多 将G作为参数递归调用depthFirstSearchVisit()函数。G设置为灰色,callback('G')。G不到邻接节点,好多好多 我将G设置为黑色。递归返回到11。
  13. 遍历D的好多好多 我邻接节点H,H未被访问过,颜色为白色,好多好多 将H作为参数递归调用depthFirstSearchVisit()函数。H设置为灰色,callback('H')。H不到邻接节点,好多好多 我将H设置为黑色。递归返回到11。
  14. D的所有邻接节点都被访问过了,将D设置为黑色。递归返回到10。
  15. 遍历C的好多好多 我邻接节点G,原应着着G原应着着被访问过,对C的邻接节点的遍历刚开始了。将C设置为黑色。递归返回到3。
  16. 访问A的最后有另有一有三个小 邻接节点D,原应着着D原应着着被访问过,对A的邻接节点的遍历刚开始了。将A设置为黑色。
  17. 好多好多 我对剩余的节点进行遍历。原应着着剩余的节点都被设置为黑色了,好多好多 系统应用应用程序刚开始了。

  对应的测试用例及执行结果如下:

depthFirstSearch(graph, value => console.log(`visited vertex: ${value}`));
visited vertex: A
visited vertex: B
visited vertex: E
visited vertex: I
visited vertex: F
visited vertex: C
visited vertex: D
visited vertex: G
visited vertex: H

  为了便于理解,当他们 儿将整个遍历过程用下面的示意图来展示:

  前面说过,深层优先算法的数据形态学 是栈,然而这里当他们 儿并不到使用栈来存储任何数据,好多好多 我使用了函数的递归调用,觉得 递归也是栈的两种表现形式。另外有些,原应着着图是连通的(即图中任何有另有一有三个小 顶点之间都发生路径),当他们 儿还可否对上述代码中的depthFirstSearch()办法进行改进,只都要对图的起始顶点刚开始了遍历一次就还可否了,而不都要遍历图的所有顶点,原应着着从起始顶点刚开始了的递归就还可否覆盖图的所有顶点。

拓扑排序

  前面展示了深层优先算法的工作原理,当他们 儿还可否使用它做更多的事情,之类拓扑排序(toplogical sorting,也叫做topsort原应着着toposort)。与广度优先算法之类,当他们 儿也对中间的depthFirstSeach()办法进行改进,以说明咋样使用深层优先算法来实现拓扑排序:

let DFSVisit = (u, color, discovery, finished, predecessors, time, adjList) => {
    color[u] = Colors.GREY;
    discovery[u] = ++time.count;

    adjList.get(u).forEach(n => {
        if (color[n] === Colors.WHITE) {
            predecessors[n] = u;
            DFSVisit(n, color, discovery, finished, predecessors, time, adjList);
        }
    });

    color[u] = Colors.BLACK;
    finished[u] = ++time.count;
};

let DFS = graph => {
    let vertices = graph.getVertices();
    let adjList = graph.getAdjList();
    let color = initializeColor(vertices);
    let discovery = {};
    let finished = {};
    let predecessors = {};
    let time = { count: 0 };

    vertices.forEach(v => {
        finished[v] = 0;
        discovery[v] = 0;
        predecessors[v] = null;
    });

    vertices.forEach(v => {
        if (color[v] === Colors.WHITE) {
            DFSVisit(v, color, discovery, finished, predecessors, time, adjList);
        }
    });

    return {discovery, finished, predecessors};
};

  DFS()办法会输出图中每个顶点的发现时间和探索时间,当他们 儿假定时间从0刚开始了,每经过一步时间值加1。在DFS()办法中,当他们 儿用变量discovery,finished,predecessors来保存每个顶点的发现时间、探索时间和前置顶点(这个 和广度优先算法中寻找最短路径中的一致,但最终执行结果会有区别),最终的输出结果中也会反映这有另有一有三个小 值。这里都要注意的是,变量time好的反义词被定义为对象而全是有另有一有三个小 普通的数字,是原应着着当他们 儿都要在函数间传递这个 变量,原应着着好多好多 我作为值传递,函数实物对变量的修改不用影响到它的原始值,好多好多 我当他们 儿好多好多 我都要在函数递归调用的过程中不断记录time的变化过程,好多好多 采用值传递的办法显然不行。好多好多 我当他们 儿将time定义为有另有一有三个小 对象,对象被作为引用传递给函数,好多好多 我在函数实物对它的修改就会反映到原始值上。

  来看看对DFS()办法的测试结果:

{
  discovery: { A: 1, B: 2, C: 10, D: 11, E: 3, F: 7, G: 12, H: 14, I: 4 },
  finished: { A: 18, B: 9, C: 17, D: 16, E: 6, F: 8, G: 13, H: 15, I: 5 },
  predecessors: {
    A: null,
    B: 'A',
    C: 'A',
    D: 'C',
    E: 'B',
    F: 'B',
    G: 'D',
    H: 'D',
    I: 'E'
  }
}

  当他们 儿将结果反映到示意图上,好多好多 我更加直观:

  示意图上每有另有一有三个小 顶点左边的数字是顶点的发现时间,右边的数字是顶点的探索时间,详细完成时间是18,还可否结合前面的深层优先算法遍历过程示意图来看,它们是对应的。同去当他们 儿也看到,深层优先算法的predecessors和广度优先算法的predecessors会有所不同。

  拓扑排序不到应用于有向无环图(DAG)。基于中间DFS()办法的返回结果,当他们 儿还可否对顶点的完成时间(探索时间finished)进行排序,以得到当他们 儿都要的拓扑排序结果。

  原应着着要实现有向图,只都要对前面当他们 儿实现的Graph类的addEdge()办法略加修改,将最后一行删掉。当然,当他们 儿也还可否在Graph类的构造函数中指明是有向图还是无向图,下面是改进后的Graph类:

  好多好多 我当他们 儿对有向图应用DFS算法:

let graph = new Graph();
let myVertices = ['A', 'B', 'C', 'D', 'E', 'F'];
myVertices.forEach((v) => {
    graph.addVertex(v);
});
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');
console.log(DFS(graph));

  下面是返回结果:

{
  discovery: { A: 1, B: 11, C: 2, D: 8, E: 4, F: 3 },
  finished: { A: 10, B: 12, C: 7, D: 9, E: 5, F: 6 },
  predecessors: { A: null, B: null, C: 'A', D: 'A', E: 'F', F: 'C' }
}

  示意图如下:

  对顶点的完成时间进行倒序排序,得到的拓扑排序结果为:B - A - D - C - F - E。

  下一章当他们 儿将介绍咋样用JavaScript来实现各种常见的排序算法。

猜你喜欢

Lyft发布无人驾驶汽车开发数据库,包括5.5万张3D高清图像

IT之家7月29日消息为了有有助于于无人驾驶汽车的发展,Lyft今天发布了一组无人驾驶汽车的开发数据,该公司称这以数据库是这类于数据中规模最为庞大的。它以现有的nuScenes

2020-01-23

隐形守护者全章节全结局怎么达成 全结局达成攻略

隐形守护者全章节全结局要为何达成,每个章节的完全剧情要为何解锁呢,这里亲戚亲戚朋友来看下完全章节剧情的解锁措施 。序章1、选【保持沉默】2、选【都可能性过去了,问这麼多干嘛?

2020-01-23

[区块链] 拜占庭将军问题 [BFT]

背景:拜占庭将军问提什么都人们机会听过,但别问我具体是那此意思。非要 究竟那此是拜占庭将军问提呢?本文从最通俗的故事讲起,并对该问提进行抽象,并告诉朋友拜占庭将军问提为那此在

2020-01-23

传WP9将是智能机和平板通吃系统,2015年发布

微软正忙着在明年推出WindowsPhoneBule(WP8.1)大更新,但现在已传来了有关2015年WindowsPhone9的消息,据称WP9将是并肩支持智能机和平板电脑的

2020-01-23

春天来了,中国乡村最美的花开咯!

春天,初阳灼目,柔风和煦,散去了冬季的凉意,吹来了阵阵花香。大地草长莺飞,中国辽阔的土地之上,七彩的春天序幕拉开,油菜花、桃花、杏花、梨花……你偏爱哪并与否?江西婺源油菜花层层

2020-01-23