数据结构-图

图是一种复杂的非线性结构, 它由边(Edge)和点(Vertex)组成. 一条边连接的两个点成为相邻顶点.

G = (V, E);

图可以分为有向图和无向图

图的表示

图的可以分为两种:

• 邻接矩阵: 使用二位数据来表示点与点之间是否有边, 如arr[i][j]=1表示节点 i 与节点 j 之间有边, arr[i][j]=0就可以表示节点 i 与节点 j 之间没有边.
• 邻接表: 邻接表是图的一种链式存储结构, 这种结构类似于树的子链表, 对于图中的每一个顶点 Vi, 把所有邻接于 Vi 的顶点 Vj 连成一个单链表, 这个单链表就是顶点 Vi 的邻接表, 但量表一般由数组或者字典结构表示.

创建图

function Graph() {
    this.vertices = []; // 顶点集合
    this.edges = new Map(); // 边集合
}
Graph.prototype.addVertex = function(v) {
    // 添加顶点方法
    this.vertices.push(v);
    this.edges.set(v, []);
};
Graph.prototype.addEdge = function(v, w) {
    // 添加边方法
    let vEdge = this.edges.get(v);
    vEdge.push(w);
    let wEdge = this.edges.get(w);
    wEdge.push(v);
    this.edges.set(v, vEdge);
    this.edges.set(w, wEdge);
};
Graph.prototype.toString = function() {
    var s = '';
    for (var i = 0; i < this.vertices.length; i++) {
        s += this.vertices[i] + ' -> ';
        var neighors = this.edges.get(this.vertices[i]);
        for (var j = 0; j < neighors.length; j++) {
            s += neighors[j] + ' ';
        }
        s += '\n';
    }
    return s;
};

图的遍历

深度优先遍历(DFS)

Depth-First-Search, 深度优先遍历, 是搜索算法的一种, 简单的说, 就是从一个节点开始追溯, 直到最后一个节点, 然后回溯, 继续追溯下一条路径. 循环往复.

DFS 是一种盲目搜索算法, 不是最短路径也不是特定路径, 而是一种遍历算法.

大致步骤如下:

1. 访问顶点
2. 一次从未被访问的临界点出发, 进行深度优先遍历, 知道图中有和 v 有路径相同的顶点被访问(如果是树就是访问到叶子节点)
3. 若此时图中还有没有访问的顶点, 则从一个未被访问的顶点出发, 重新进行深度优先遍历, 直到所有顶点都被访问.

Graph.prototype.dfs = function() {
    var marked = [];
    for (var i = 0; i < this.vertices.length; i++) {
        if (!marked[this.vertices[i]]) {
            dfsVisit(this.vertices[i]);
        }
    }

    function dfsVisit(u) {
        let edges = this.edges;
        marked[u] = true;
        console.log(u);
        var neighbors = edges.get(u);
        for (var i = 0; i < neighbors.length; i++) {
            var w = neighbors[i];
            if (!marked[w]) {
                dfsVisit(w);
            }
        }
    }
};

广度优先遍历

Breadth-First-Search, 广度优先遍历是从根节点开始, 沿着图的宽度遍历节点,

Graph.prototype.bfs = function(v) {
    var queue = [],
        marked = [];
    marked[v] = true;
    queue.push(v); // 添加到队尾
    while (queue.length > 0) {
        var s = queue.shift(); // 从队首移除
        if (this.edges.has(s)) {
            console.log('visited vertex: ', s);
        }
        let neighbors = this.edges.get(s);
        for (let i = 0; i < neighbors.length; i++) {
            var w = neighbors[i];
            if (!marked[w]) {
                marked[w] = true;
                queue.push(w);
            }
        }
    }
};

Dijkstra算法

狄克斯特拉算法是从一个顶点到其余各顶点的最短路径算法, 解决的是有权图中最短路径问题.

主要特点是从起点开始, 采用贪心算法的策略, 每次遍历到到起始点距离最近且未访问过的顶点的邻接节点, 直到扩展到终点为止.

注意: 这里我们讨论的是单向单源的图.

// 起点
let node = startNode;
// 构建开销表
let costs = new Map();
for (let i = 0; i < this.vertices.length; i++) {
    const vertice = this.vertices[i];
    if (vertice === node) {
        costs.set(vertice, 0);
    } else {
        costs.set(vertice, Infinity);
    }
}

// 这里添加了一个队列处理所有节点
let resNodes = [node];

while (resNodes.length) {
    // 当前处理的节点
    let curNode = resNodes.shift();
    if (!curNode) {
        continue;
    }
    // 获取所有相邻的节点
    let neighbors = this.edges.get(curNode);
    if (!neighbors) {
        continue;
    }

    for (let i = 0; i < neighbors.length; i++) {
        const neighbor = neighbors[i];

        // 比较最小值
        let minCost = Math.min(
            costs.get(curNode) + neighbor.cost,
            costs.get(neighbor.gnode)
        );
        costs.set(neighbor.gnode, minCost);

        resNodes.push(neighbor.gnode);
    }
}

return costs.get(end[0]);