图相关知识小结

[xszi]

1. 图基础知识

• 由一条边连接在一起的顶点称为相邻顶点。
• 一个顶点的度是其相邻顶点的数量。
• 简单路径要求不包含重复的顶点。举例，ADG是一条简单路径。
• 除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径，比如ADCA（最后一个顶点重新回到A）。
• 如果图中不存在环，则称该图是无环的。
• 如果图中每两个顶点间都存在路径，则该图是连通的。

有向图

• 如果图中每两个顶点间在双向上都存在路径，那该图是强连通的。例如，C和D是强连通的，而A和B不是。

加权图

• 最短路径问题

2. 图的表示

邻接矩阵

• 邻接矩阵一般用二维数组来表示。
• 不是强连通的图（稀疏图）如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费计算机存储空间来表示根本不存在的边。
• 图中顶点可能会改变，二维数组不太灵活，遍历查找效率低。

邻接表

• 可以使用列表（数组），链表，甚至散列表或字典来表示。
• 判断顶点是否还是使用邻接矩阵比较快。

关联矩阵

在关联矩阵中，矩阵的行表示顶点，列表示边。如下图所示，我们使用二维数组来表示两者之间的连通性，如果顶点 v 是 边e的入射点，则 array[v][e] === 1,否则 array[v][e] === 0。

3、创建Graph类

function Graph() {
    var vertices = [];
    var adjList = new Dictionary();

    // 加顶点
    this.addVertex = function(v) {
        vertices.push(v);
        adjList.set(v, []);
    }

    // 加边
    this.addEdge = function(v, w) {
        addList.get(v).push(w);
        addList.get(W).push(v);
    }

    this.toString = function() {
        var s = '';
        for (var i = 0; i <vertices.length; i++) {
            s += vertices[i] + ' -> '
            var neighbors = adjList.get(vertices[i]);
            for (var j = 0; j < neighbors.length; j++) {
                s += neighbors[j] + ' ';
            }
            s += '\n'
        }
    }
    return s;
}

4、图的遍历

图的遍历可以用来：

• 寻找特定的顶点
• 寻找两个顶点之间的路径
• 检查图是否连通
• 检查图是否有环

算法	数据结构	描述
深度优先搜索	栈	通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
广度优先搜索	队列	通过将顶点存入队列中，最先入队列的顶点先被探索