BFS,DFS 算法原理及js实现

刘德刚发布于2019-08-22 11:19 / 1618人阅读

1. 说明

本文所有的算法严格按照《算法导论》，本文将详细的对BFS和DFS进行分析，并提供算法的 js 实现，同时会对创建链表的方式进行优化

2. 图的表示

图的表示分为对顶点集 V 的表示和对边集 E 的表示，这里的重点是如何表示边，边的表示分为邻接矩阵和邻接链表这两种表示方法，邻接矩阵适合表示边稠密的图，其消耗空间为|V|*|V|,如果是无向图，则可以用上三角矩阵或者下三角矩阵来表示，是空间消耗变为|V|*|V|/2，邻接链表适合表示边稀疏的图，其消耗的空间为 O(|V|+|E|),用邻接链表表示图很紧凑，没有空间浪费，用《算法导论》中的原话就是，邻接链表表示图，鲁棒性很高。本文涉及的图，全部用邻接链表表示。

2.1. 本文的算法都是对该图的操作

2.2. 对上图进行邻接链表的转化

从上图可以看到我们将图的分为两部分，顶点和边，我们分别对这两部分进行表示，我们用数组去存放顶点，用链表去描述边。A-E 做为节点的标识。数字表示顶点在数组中的位置。由这幅图可以看到从节点 A 发出的边有两条，分别是 ,和

3. BFS 广度优先搜索

广度优先搜索的思想是，对于图G和给定的节点s，广度优先搜索需要一个辅助的先进先出的队列 Q

将s加入到Q中

将s从Q总移出，用临时变量接受s，如果s没有被访问过，从s出发，发现s的所有邻接节点并放入Q中

访问s

将Q队列的第一个元素移除队列作为新的s执行2-4过程直到队列Q为空

3.1 表示顶点的数据结构

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; //节点的值 默认为空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 为 null 时表示无穷大
}

为了跟踪算法的进展，我们对图进行搜索的时候会对图中的顶点进行涂色，图初始化是顶点全部为白色，当第一次发现某个节点时，我们将他涂为灰色，当对某个节点访问完成后，我们将它涂为黑色。在这里我们看到每个节点都有五个属性，color表示节点的颜色，pi 表示前驱结点，d 表示广度优先搜索中从源节点到当前节点的距离，edges 表示从当前节点发出的所有边，value 表示节点存放的数据

3.2 表示边的数据结构

function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //边所依附的节点的位置
    this.sibling = null;
}

可以看到，边包含两个两个属性，index，和sibling，index表示这条边连接的节点在顶点数组中的位置，sibling只想下一个连接兄弟节点的边。

3.3 表示图的数据结构

function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = []; //存放顶点的数组
}
Graph.prototype = {
    constructor: Graph,
    addNode: function (node) {
        this.graph.push(node);
    },
    getNode: function (index) {
        return this.graph[index];
    }
}

3.4 构建图

//创建 顶点
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//构建由 A 节点发出的边集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//构建有 B 节点发出的边集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//构建由 C 节点发出的边
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//构建由 D 节点发出的边
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//构建由 E 节点发出的边
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//构建由 F 节点发出的边
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//构建图
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

3.5 BFS算法

//广度优先搜索
function BFS(g, s) {
    let queue = []; //辅助队列 Q
    s.color = s.GRAY; //首次发现s涂为灰色
    s.d = 0; //距离为0
    queue.push(s); //将s放入队列 Q
    while (queue.length > 0) { //当队列Q中有顶点时执行搜索
        let u = queue.shift(); //将Q中的第一个元素移出
        if (u.edges == null) continue; //如果从当前顶点没有发出边
        let sibling = u.edges; //获取表示邻接边的链表的头节点
        while (sibling != null) { //当链表不为空
            let index = sibling.index; //当前边所连接的顶点在队列中的位置
            let n = g.getNode(index); //获取顶点
            if (n.color == n.WHITE) { //如果没有被访问过
                n.color = n.GRAY; //涂为灰色
                n.d = u.d + 1; //距离加1
                n.pi = u; //设置前驱节点
                queue.push(n); //将 n 放入队列 Q
            }
            sibling = sibling.sibling; //下一条边
        }
        u.color = u.BLACK; //当前顶点访问结束 涂为黑色
    }
}

3.6 完整代码可粘贴到浏览器控制台运行

//数据结构 邻接链表-顶点
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; //节点的值 默认为空
}
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;
}

//数据结构 图-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
}
Graph.prototype = {
    constructor: Graph,
    //这里加进来的已经具备了边的关系
    addNode: function (node) {
        this.graph.push(node);
    },
    getNode: function (index) {
        return this.graph[index];
    }
}

//广度优先搜索
function BFS(g, s) {
    let queue = [];
    s.color = s.GRAY;
    s.d = 0;
    queue.push(s);
    while (queue.length > 0) {
        let u = queue.shift();
        if (u.edges == null) continue;
        let sibling = u.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.color = n.GRAY;
                n.d = u.d + 1;
                n.pi = u;
                queue.push(n);
            }
            sibling = sibling.sibling;
        }
        u.color = u.BLACK;
        console.log(u);
    }
}

//创建 顶点
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//构建由 A 节点发出的边集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//构建有 B 节点发出的边集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//构建由 C 节点发出的边
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//构建由 D 节点发出的边
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//构建由 E 节点发出的边
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//构建由 F 节点发出的边
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//构建图
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

BFS(g, vB);

顶点的访问顺序为 B->A->E->C->D->F

4. DFS 深度优先搜索

特点
深度优先搜索一般默认的源点有多个，搜索时的前驱子图会构成一个深度优先森林，这是依据深度优先搜索的搜索结果的使用深度优先搜索算法常常作为另一个算法的一个子程序被使用深度优先搜索在节点中增加了一个发现的时间戳，一个访问的时间戳，通常能帮助我们推断算法的行为，在d-f之间是灰色，在f之后是黑色，时间戳为1到2*|v|之间的整数

算法思想
只要有可能，就在图中尽量“深入”，总是对最近才发现的节点v的出发边进行探索，知道该节点的所有出发边都被发现为止。一旦v的所有发出的边都被发现，搜索则“回溯”到v的前驱节点，该过程一直持续到源节点可达的所有节点都被发现为止，如果还有未发现的节点，则深度优先搜索将从这些未被发现的节点中任选一个作为新的源节点，并重复同样的搜索过程

4.1 算法数据结构

深度优先搜索的数据结构只有在表示顶点时稍有不同，其它的都相同，这里给出表示顶点的数据结构

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始为 白色
    this.pi = null; //初始为 无前驱
    this.d = null; //时间戳 发现时
    this.f = null; //时间戳 邻接链表扫描完成时
    this.edges = null; //由顶点发出的所有边
    this.value = null; //节点的值 默认为空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
}

可以看到顶点数据结构中的多了一个f，同时d的含义也发生了变化d和f作为发现和访问完成的时间戳，取值为从1到2*|v|

4.2 DFS算法

function DFS(g) {
    let t = 0; //时间戳
    for (let v of g.vertexs) { //让每个节点都作为一次源节点
        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;
    }
}

4.3 DFS完整代码

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始为 白色
    this.pi = null; //初始为 无前驱
    this.d = null; //时间戳 发现时
    this.f = null; //时间戳 邻接链表扫描完成
    this.edges = null; //由顶点发出的所有边
    this.value = null; //节点的值 默认为空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
}

//数据结构 图-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertexs = [];
}
Graph.prototype = {
    constructor: Graph,
    addNode: function (node) {
        this.vertexs.push(node);
    },
    getNode: function (index) {
        return this.vertexs[index];
    }
}

//这里 t 作为全局变量和参数时结果不一样 因为 js 对于基本类型的参数采用的是值捕获，对于对象类型的参数采用的是引用捕获
function DFS(g) {
    let t = 0;
    for (let v of g.vertexs) {
        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;
        console.log(v);
    }
}

//数据结构 邻接链表-边
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //边所依附的节点的位置
    this.sibling = null;
}

//创建 顶点
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//构建由 A 节点发出的边集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//构建有 B 节点发出的边集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//构建由 C 节点发出的边
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//构建由 D 节点发出的边
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//构建由 E 节点发出的边
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//构建由 F 节点发出的边
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//构建图
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

DFS(g);

节点访问顺序为 F->C->E->B->D->A

5. 对构建链表的方式进行优化

我们发现构建图的操作过于繁琐，于是想简化图的构建方式，简化后如下

var vertexs = ["A", "B", "C", "D", "E", "F"];
var edges = {
    A: [{ id: "B", w: 1 }, { id: "D", w: 2 }],
    B: [{ id: "A", w: 3 }, { id: "E", w: 3 }, { id: "C", w: 7 }],
    C: [{ id: "B", w: 5 }, { id: "E", w: 3 }, { id: "F", w: 4 }],
    D: [{ id: "A", w: 2 }],
    E: [{ id: "B", w: 3 }, { id: "C", w: 7 }, { id: "F", w: 3 }],
    F: [{ id: "C", w: 6 }, { id: "E", w: 9 }]
}
var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);

我们想用这种方式初始化一个图，w为边的权值

这里的改进只是针对图的构建，所有无论时BFS,还是DFS，表示顶点和边的数据结构都没有变，只有对表示图的数据结构 Graph进行改进

5.1 改进之后的Graph

//数据结构图-G

//数据结构 图-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.refer = new Map(); //字典 用来映射标节点的识符和数组中的位置
}
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;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.refer.set(this.graph[i].value,i);
        }
    },
    //建立图中 边 的关系
    initEdge: (function(){
        //创建链表，返回链表的第一个节点
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //边连接的节点 用在数组中的位置表示 参照字典
            edgeNode.w = edges[index].w; //边的权值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通过递归实现 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //从字典表中找出节点在 graph 中的位置
                let vertex = this.graph[index]; //获取节点
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }())
}

5.2 改进之后的BFS完整代码

DFS相同

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; //节点的值 默认为空
}
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.refer = new Map(); //字典 用来映射标节点的识符和数组中的位置
}
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;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.refer.set(this.graph[i].value,i);
        }
    },
    //建立图中 边 的关系
    initEdge: (function(){
        //创建链表，返回链表的第一个节点
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //边连接的节点 用在数组中的位置表示 参照字典
            edgeNode.w = edges[index].w; //边的权值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通过递归实现 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //从字典表中找出节点在 graph 中的位置
                let vertex = this.graph[index]; //获取节点
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }())
}

//广度优先搜索
function BFS(g, s) {
    let queue = [];
    s.color = s.GRAY;
    s.d = 0;
    queue.push(s);
    while (queue.length > 0) {
        let u = queue.shift();
        if (u.edges == null) continue;
        let sibling = u.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.color = n.GRAY;
                n.d = u.d + 1;
                n.pi = u;
                queue.push(n);
            }
            sibling = sibling.sibling;
        }
        u.color = u.BLACK;
        console.log(u)
    }
}

var vertexs = ["A", "B", "C", "D", "E", "F"];
var edges = {
    A: [{ id: "B", w: 1 }, { id: "D", w: 2 }],
    B: [{ id: "A", w: 3 }, { id: "E", w: 3 }, { id: "C", w: 7 }],
    C: [{ id: "B", w: 5 }, { id: "E", w: 3 }, { id: "F", w: 4 }],
    D: [{ id: "A", w: 2 }],
    E: [{ id: "B", w: 3 }, { id: "C", w: 7 }, { id: "F", w: 3 }],
    F: [{ id: "C", w: 6 }, { id: "E", w: 9 }]
}
//构建图
var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);
//调用BFS
BFS(g, g.graph[1]);

6. 总结

着重体会

1 如何用邻接链表表示图的边

2 如何用递归的特性实现回溯

超融合服务器服务器托管矩阵dfs算法购物车实现原理 js ddos攻击原理及防范人工智能原理及应用

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/92176.html

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

roadtogeek 2019-08-23 16:33 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
js版本的BFS&DFS

摘要：队列栈队列是先进先出，后进后出，常用的操作是取第一个元素尾部加入一个元素。栈是后进先出，就像一个垃圾桶，后入的垃圾先被倒出来。遍历中间过程，每一个节点入栈的时候是灰色的，出栈的时候是黑色的。 0. 前言广度优先搜索(BFS)和深度优先搜索(DFS)，大家可能在oj上见过，各种求路径、最短路径、最优方法、组合等等。于是，我们不妨动手试一下js版本怎么玩。 1.队列、栈队列是先进先出，...

刘福 2019-08-22 16:49 评论0 收藏0
拓扑排序原理分析及js实现

摘要：但是一个偏序关系，如果我们默认，先出现的排在前面，那么我们就能比较，的关系了。对于算法的每个节点，我们都有一个发现时间，一个访问时间，当运行完成时，对于图中的任意一条边，都有所以拓扑排序的次序与顶点的完成时间恰好相反。 1. 偏序和全序的概念 1.1. 偏序设R是集合A上的一个二元关系，若R满足下列三个性质则称R为A上的偏序关系自反性：对任意x∈A，有∈R反对称性：对任意的x,y∈A...

QiShare 2019-08-22 11:23 评论0 收藏0
PHP面试：常见查找算法一篇说透

摘要：我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。预警在本篇文章中，将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂，所以篇幅可能较长，大伙可以先Mark下来，每天抽时间看一点理解一点。本文配套的Github Repo，欢迎各位老铁star，会一直更新的。开篇和排序类似，搜索或者叫做...

付永刚 2019-07-01 10:47 评论0 收藏0