图（Graph）

  • 李艳生
  • 湖北师范大学
  • 物理与电子科学学院
  • 2020年春季

回顾

  • 树（父子关系的节点集合）

  • 二叉树（最多只有两个子节点）

  • 数组（随机访问，顺序存储）

  • 字典Map (键值对)

引入

1.png

交通网络

引入

3.jpg

通信网络

图的概念

  • 图是网络结构的抽象模型。
  • 图是一组由边连接的节点（或顶点）。

图的概念

  • 一个图G = (V, E)由以下元素组成。
    • V：一组顶点
    • E：一组边，连接V中的顶点

4.png

图的概念

  • 相邻顶点: 由一条边连接在一起的顶点
  • 度: 其相邻顶点的数量
  • 路径: 顶点v1, v2, …, vk的一个连续序列，其中vi和vi+1是相邻的。

4.png

图的概念

  • 环：第一个顶点和最后一个顶点相同的路径
  • 连通： 如果图中每两个顶点间都存在路径

4.png

图的概念

  • 有向图： 边是有方向的
  • 无向图： 边是没有方向的

5.png

图的概念

  • 加权图：边被赋予了权值

6.png

图的表示

  • 邻接矩阵
  • 邻接表

图的表示

  • 邻接矩阵

7.png

图的表示

  • 邻 接 表

8.png

图的创建

  • 邻接表方式创建
class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected;
    this.vertices = []; //顶点列表
    this.adjList = new Map(); //顶点表示键，邻接顶点列表表示值
  }
}

图的创建

  • 向图中添加一个新的顶点
addVertex(v) {
    if (!this.vertices.includes(v)) {
      this.vertices.push(v);
      //将新加顶点的邻接顶点列表初始为空数组
      this.adjList.set(v, []); 
    }
}

图的创建

  • 向图中添加一个新的边
addEdge(a, b) {
    if (!this.adjList.get(a)) {
      this.addVertex(a);
    }
    if (!this.adjList.get(b)) {
      this.addVertex(b);
    }
    this.adjList.get(a).push(b);
    if (this.isDirected !== true) {
      this.adjList.get(b).push(a);
    }
}

图的创建

getVertices() {
    return this.vertices;
}

getAdjList() {
    return this.adjList;
}

图的创建

  • 转字符串
toString() {
    let s = '';
    for (let i = 0; i < this.vertices.length; i++) {
      s += `${this.vertices[i]} -> `;
      const neighbors = this.adjList.get(this.vertices[i]);
      for (let j = 0; j < neighbors.length; j++) {
        s += `${neighbors[j]} `;
      }
      s += '\n';
    }
    return s;
}

图的使用

const graph = new Graph();

const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];

for (let i = 0; i < myVertices.length; i++) {
   graph.addVertex(myVertices[i]);
}

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());

图的遍历

  • 广度优先搜索（breadth-first search，BFS）
  • 深度优先搜索（depth-first search，DFS）
广度优先搜索 队列 将顶点存入队列,最先入队列的顶点先被探索
深度优先搜索 栈 将顶点存入栈,顶点是沿着路径被探索的，存在新的相邻顶点就去访问

图的遍历

  • 白色：表示该顶点还没有被访问。
  • 灰色：表示该顶点被访问过，但并未被探索过。
  • 黑色：表示该顶点被访问过且被完全探索过。
const Colors = {   
    WHITE: 0,   
    GREY: 1,   
    BLACK: 2 
}; 

const initializeColor = vertices => {   
    const color = {};   
    for (let i = 0; i < vertices.length; i++) {     
        color[vertices[i]] = Colors.WHITE;   
    }   
    return color; 
};

广度优先搜索

9.png

广度优先搜索

BFS.gif

广度优先搜索

  • 创建一个队列Q。
  • 标注v为被发现的（灰色），并将v入队列Q。
  • 如果Q非空，则运行以下步骤：
    • 将u从Q中出队列；
    • 标注u为被发现的（灰色）；
    • 将u所有未被访问过的邻点（白色）入队列；
    • 标注u为已被探索的（黑色）。

广度优先搜索

const breadthFirstSearch = (graph, startVertex, callback) => {  
    const vertices = graph.getVertices();   
    const adjList = graph.getAdjList();   
    const color = initializeColor(vertices);
    const queue = new Queue();
    queue.enqueue(startVertex);
    while (!queue.isEmpty()) {
        const u = queue.dequeue();
        const neighbors = adjList.get(u);
        color[u] = Colors.GREY;
        for (let i = 0; i < neighbors.length; i++){
            const w = neighbors[i];
            if(color[w] === Colors.WHITE) {
                color[w] = Colors.GREY;
                queue.enqueue(w);
            }
        }
        color[u] = Colors.BLACK;
        if (callback) {       
            callback(u);     
        } 
    }
}

广度优先搜索

const printVertex = (value) => console.log('Visited vertex: ' + value);
breadthFirstSearch(graph, myVertices[0], printVertex);

深度优先搜索

10.png

深度优先搜索

DFS.gif

深度优先搜索

  • 要访问顶点v，照如下步骤做：
    • 标注v为被发现的（灰色）；
    • 对于v的所有未访问（白色）的邻点w，访问顶点w；
    • 标注v为已被探索的（黑色）。

深度优先搜索

const depthFirstSearch = (graph, callback) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(vertices);
    for (let i = 0; i < vertices.length; i++) { // {2}
        if (color[vertices[i]] === Colors.WHITE) { // {3}
            depthFirstSearchVisit(vertices[i], color, adjList, callback); // {4}
        }
    }
};
const depthFirstSearchVisit = (u, color, adjList, callback) => {
    color[u] = Colors.GREY; // {5}
    if (callback) { // {6}
        callback(u);
    }
    const neighbors = adjList.get(u); // {7}
    for (let i = 0; i < neighbors.length; i++) { // {8}
        const w = neighbors[i]; // {9}
        if (color[w] === Colors.WHITE) { // {10}
            depthFirstSearchVisit(w, color, adjList, callback); // {11}
        }
    }
    color[u] = Colors.BLACK; // {12}
};

深度优先搜索

depthFirstSearch(graph, printVertex);

任务

用邻接表创建下图，并分别用BFS和DFS两种方法遍历下图。

11.png

问题引入

  • 在n个城市建设光纤网络,任意两个城市之间都可以通信,各个城市之间铺设光缆的费用不同,使建设成本最低？

连通图

  • 在无向图中，若任意两个顶点与都有路径相通，则称该无向图为连通图

生成树

  • 连通图的生成树是一个极小连通子图
  • 它含有图中全部n个顶点
  • 但只有构成一棵树的n-1条边
  • 如果生成树中再添加一条边，则必定含环。
  • 可对应多个生成树

最小生成树

  • 无向加权图的所有生成树中，权值之和最小的生成树，称为最小生成树

12.png

无向加权图邻接矩阵

12.png

var graph = [
[0, 2, 4, 0, 0, 0],
[2, 0, 2, 4, 2, 0],
[4, 2, 0, 0, 3, 0],
[0, 4, 0, 0, 3, 2],
[0, 2, 3, 3, 0, 2],
[0, 0, 0, 2, 2, 0]];

最小生成树

  • Prim算法
  • Kruskal算法

Kruskal算法

  • 加边法
  • 初始最小生成树边数为0
  • 每迭代一次就选择一条的最小权值边，且该边两个顶点不属于同一棵树
  • 加入到最小生成树的边集合里，直到n-1条边止

Kruskal算法

  • 设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，并将不属于同一棵树边加入TE。

Kruskal算法

13.png

Kruskal算法

const INF = Number.MAX_SAFE_INTEGER;

const kruskal = graph => {
    const { length } = graph; //邻接矩阵
    const parent = [];//生成树，父子结点，边
    let ne = 0;
    let a; let b; let u; let v;
    const cost = initializeCost(graph); //复制邻接矩阵
    while (ne < length - 1) { // 找n-1条边
        //在cost矩阵中找权值最小的边
        for (let i = 0, min = INF; i < length; i++) {
            for (let j = 0; j < length; j++) {
                if (cost[i][j] < min) {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        //判断最小权值边的两个顶点是否属于同一棵树，有相同的根结点
        //找u的根结点
        u = find(u, parent); 
        //找v的根结点
        v = find(v, parent); 
        //如果u,v根结点不相同，则该边加入最小生成树
        if (union(u, v, parent)) {
            ne++;
        }
        cost[a][b] = cost[b][a] = INF; //去除该边
    }
    return parent;
}
//复制矩阵
const initializeCost = (graph) => {
    let ret = [];
    for(let i = 0; i < graph.length; i++){
        ret[i] = [];
        for(let j = 0; j < graph[i].length; j++){
            ret[i][j] = graph[i][j];
        }
    }
    return ret;
}
//找根结点
const find = (i, parent) => {   
    while (parent[i]) {     
        i = parent[i];   
    }   
    return i; 
};

//判断两个顶点是否属于同一棵树
const union = (i, j, parent) => {
    if (i !== j) {
        parent[j] = i; //i作为j的父结点
        return true;
    }
    return false;
};

Prim算法

  • 加点法
  • 每次迭代选择权值最小的边对应的点，加入到最小生成树中。
  • 算法从某一个顶点开始，直到最小生成树n个顶点为止。

Prim算法

  • 设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={ }，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

Prim算法

14.png

Prim算法

const INF = Number.MAX_SAFE_INTEGER;

const prim = graph => {
    const parent = []; //每个顶点的父结点
    const key = []; //最短边的权值
    const visited = []; //访问过顶点设置为true
    const { length } = graph; //顶点数
    //初始化
    for (let i = 0; i < length; i++) {
        key[i] = INF;
        visited[i] = false;
    }
    //开始顶点
    key[0] = 0;
    parent[0] = -1;
    //找所有的顶点
    for (let i = 0; i < length; i++) { 
        //找到key最小结点索引
        const u = minKey(key, visited); 
        visited[u] = true; 
        for (let v = 0; v < length; v++) {
            if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) { // {6}
                //设置v的父结点
                parent[v] = u; 
                //更新v的权值
                key[v] = graph[u][v]; 
            }
        }
    }
    return parent; 
};

//找key且对应的visited为flase的最小值索引
const minKey = (key, visited) => {
    let min = INF;
    let minIndex = -1;
    for (let v = 0; v < key.length; v++) {
        if (visited[v] === false && key[v] <= min) {
            min = key[v];
            minIndex = v;
        }   
    }
    return minIndex;
};

问题引入

  • 从A城市到B城市，距离最短怎么走？时间最短怎么走？费用最少怎么走？

最短路径

  • 单源点的最短路径
  • 每一对顶点之间的最短路径

有向加权图邻接矩阵

15.png

var graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 2, 4, 2, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 2],
[0, 0, 0, 3, 0, 2],
[0, 0, 0, 0, 0, 0]];

单源点最短路径

  • 给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。

单源点最短路径

  • Dijkstra算法
    • 设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。

Dijkstra算法

  • 每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。

$$ dist[j] = Min\{dist[i]\} $$ dist[j] + arcs[j][k] < disk[k]时 $$ dist[k] = dist[j] + arcs[j][k] $$

Dijkstra算法

const INF = Number.MAX_SAFE_INTEGER;

const dijkstra = (graph, src) => {
    const dist = []; //dist[i]存储src到i的最短路径的长度
    const visited = [];//设置访问过顶点为true
    const { length } = graph;//顶点数
    //初始化
    for (let i = 0; i < length; i++) { 
        dist[i] = INF;
        visited[i] = false;
    }
    //源点
    dist[src] = 0; 

    for (let i = 0; i < length - 1; i++) { 
        const u = minDistance(dist, visited);
        visited[u] = true;
        for (let v = 0; v < length; v++) {
            if (!visited[v] &&
            graph[u][v] !== 0 &&
            dist[u] !== INF &&
            dist[u] + graph[u][v] < dist[v]) { 
                dist[v] = dist[u] + graph[u][v]; 
            }
        }
    }
    return dist;
};

const minDistance = (dist, visited) => {
    let min = INF;
    let minIndex = -1;
    for (let v = 0; v < dist.length; v++) {
        if (visited[v] === false && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
};

每对顶点之间的最短路径

  • 给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。

每对顶点之间的最短路径

  • Floyd算法
    • 对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

Floyd算法

  • dist(k)[i][j]是从vi到vj的中间顶点的序号不大于k的最短路径的长度

16.png

Floyd算法

const floyd = graph => {
    const dist = [];
    const { length } = graph;
    for (let i = 0; i < length; i++) {
        dist[i] = [];
        for (let j = 0; j < length; j++) {
            if (i === j) {
                dist[i][j] = 0; 
            } else if ((graph[i][j] === 0) && (i !== j)) {
                dist[i][j] = Infinity; 
            } else {
                dist[i][j] = graph[i][j]; 
            }   
        }
    }
    for (let k = 0; k < length; k++) { 
        for (let i = 0; i < length; i++) {
            for (let j = 0; j < length; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) { // {6}
                    dist[i][j] = dist[i][k] + dist[k][j]; // {7}
                }
            }
        }
    }
    return dist;
};

任务

  • 利用prim和kruskal算法求解下图最小生成树。

12.png

任务

  • 求解下图顶点A到其它各顶点的最短路径以及各顶点之间的最短路径。

15.png