图论基础-1.查找所有路径

作者: 倩倩_a570 | 来源:发表于2020-03-28 22:58 被阅读0次

图论基础-1.查找所有路径
UI学习笔记2 --- AI 基础
python -networkx 基本知识
webpack笔记
idea 实用快捷键持续更新
文件批量加锁
查找文件
linux常用的shell命令
图论基础
图论基础

学习背景

53685A7D-8753-4F2F-A8D6-DB24C846A29A.png

工作中某块需求涉及到查找两点之间全部路径的需求，尝试利用图的算法来解决这一问题。
目标：找出途中从开始到结束节点中间的所有路径

概念

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点），任何二元关系都可以用图来表示。
一个图G=(V, E)由以下兀素组成：

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

概念图.png

由一条边连接在一起的顶点称为相邻顶点比如，A和B是相邻的
一个顶点的度是其相邻顶点的数量比如，A和其他三个顶点相连接，因此，A的度为3
路径是顶点v1, v2, ...vk的一个连续序列以上图为例，其中包含路径A B E I 和 A C D G。

图的两种存储结构

乍看起来，图和树或者二叉树很像，我们可能会尝试用树的方式来创建一个图类，用节点来表示每个顶点。但这种情况下，如果用基于对象的方式去处理就会有问题，因为图可能增长到非常大。用对象来表示图很快会变得效率低下，所以我们要考虑表示顶点或边的其他方案。

用例：

// 顶点个数
var point = 10;
// 相连节点
var line = [
  [1, 2], [1, 5], [1, 9], [2, 8],[3, 7], [4, 5],[5, 8], [5, 9],[7, 9], [8, 7], [9, 1], [9, 2]
];

1.邻接矩阵：（Adjacency Matrix）适用于稠密图（完全图）

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。

function MatrixGraph(n, direction) {
  this.n = n;
  this.m = 0;
  this.direction = false;
  this.g = Array(n)
    .fill(1)
    .map(() => {
      return Array(n)
        .fill(1)
        .map(() => {
          return 0;
        });
    });
}
MatrixGraph.prototype.addEdge = function(x, y) {
  if (x < this.n && y < this.n && !this.hasEdge(x, y)) {
    this.g[x][y] = 1;
    this.m++;
  }
};

MatrixGraph.prototype.printG = function() {
  let sum = "";
  console.log("this.g: ", this.g);
  this.g.forEach((item, i) => {
    item.forEach(p => {
      sum += `  ${p}`;
    });
    sum += `\n`;
  });
  console.log(sum);
};

MatrixGraph.prototype.hasEdge = function(x, y) {
  return this.g[x][y];
};

 var graph = new DenseGraph(point, false);
 line.forEach(item => {
   graph.addEdge(item[0], item[1]);
 });
 graph.printG()；
 
  // 生成的邻接矩阵：
  // 0  0  0  0  0  0  0  0  0  0
  // 0  0  1  0  0  1  0  0  0  1
  // 0  0  0  0  0  0  0  0  1  0
  // 0  0  0  0  0  0  0  1  0  0
  // 0  0  0  0  0  1  0  0  0  0
  // 0  0  0  0  0  0  0  0  1  1
  // 0  0  0  0  0  0  0  0  0  0
  // 0  0  0  0  0  0  0  0  0  1
  // 0  0  0  0  0  0  0  1  0  0
  // 0  1  1  0  0  0  0  0  0  0

2.邻接表（Adjacency Lists）适用于稀疏图

邻接表是图的一种链式存储结构，对于图G中的每个顶点Vi，把所有邻接于Vid 顶点Vj连成一个单链表，这个单链表称为顶点Vi的邻接表

function ChainGraph(n, direction) {
  this.n = n;
  this.m = 0;
  this.direction = false;
  this.g = {};
}
ChainGraph.prototype.addEdge = function(x, y) {
  if (!this.hasEdge(x, y)) {
    this.g[x] ? this.g[x].push(y) : (this.g[x] = [y]);
    this.m++;
  }
};
ChainGraph.prototype.printG = function() {
  let sum = "";
  Object.keys(this.g).forEach((key, i) => {
    sum += key + ":";
    this.g[key].forEach(p => {
      sum += `  ${p}`;
    });
    sum += `\n`;
  });
  console.log(sum);
};

ChainGraph.prototype.hasEdge = function(x, y) {
  if (!this.g[x]) this.g[x] = [];
  if (!this.g[y]) this.g[y] = [];
  return this.g[x] && this.g[x].includes(y);
};

var graph = new SparseGraph(point, false);
line.forEach(item => {
    graph.addEdge(item[0], item[1]);
  });
  graph.printG();
//生成的邻接表：
//0
//1  2  5  9
//2  8
//3  7
//4  5
//5  8  9
//6
//7  9
//8  7
//9  1  2

图的两种遍历方法

和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：

深度优先搜索（Depth-First Search，DFS)

深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是：
a) 假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过。
b)然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到。
c) 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

ChainGraph.prototype.deepFirstSearch = function() {
  // 存放遍历结果
  var pointList = [];
  const dfs = arr => {
    arr.forEach(key => {
      if (pointList.includes(key)) return;
      pointList.push(key);
      dfs(this.g[key]);
    });
  };
  dfs(Object.keys(this.g));
  console.log(pointList); //["A", "B", "D", "I", "C", "E", "G", "F", "H"]
};

广度优先搜索（Breadth-First Search，BFS)

广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是：
a) 首先访问出发点Vi
b) 接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，Vi3，…，Vit并均标记为已访问过。
c) 然后再按照Vi1，Vi2，… ，Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。

SparseGraph.prototype.breadthFirstSearch = function() {
  // 存放遍历结果
  var pointList = [];
  var pendingList = [Object.keys(this.g)[0]];
  const bfs = () => {
    var curPoint = pendingList.shift();
    if (!pointList.includes(curPoint)) pointList.push(curPoint);

    pendingList = pendingList.concat(this.g[curPoint]);
    if (pendingList.length) bfs();
  };
  bfs();
  console.log(pointList); //["A", "B", "C", "D", "E", "F", "I", "G", "H"]
};

找出开始到结束节点的所有通路

1.将图抽象成用例

var point = 10;
// 相连节点
var line = [
  [1, 2], [1, 5], [1, 9], [2, 8],[3, 7], [4, 5],[5, 8], [5, 9],[7, 9], [8, 7], [9, 1], [9, 2]
];

2生成邻接矩阵

  // 0  0  0  0  0  0  0  0  0  0
  // 0  0  1  0  0  1  0  0  0  1
  // 0  0  0  0  0  0  0  0  1  0
  // 0  0  0  0  0  0  0  1  0  0
  // 0  0  0  0  0  1  0  0  0  0
  // 0  0  0  0  0  0  0  0  1  1
  // 0  0  0  0  0  0  0  0  0  0
  // 0  0  0  0  0  0  0  0  0  1
  // 0  0  0  0  0  0  0  1  0  0
  // 0  1  1  0  0  0  0  0  0  0

3获取所有路径

DenseGraph.prototype.getAllPath = function() {
  const newBilityPath = [];
  const getPath = (path, arr) => {
    let has = false;
    const newPath = [...path];

    for (let i = 0; i < arr.length; i++) {
      if (arr[i]) {
        //有连接
        if (has) {
          newPath.pop();
        }
        newPath.push(i);
        getPath(newPath, this.g[i]);
        has = true;
      }
    }
    if (!has) {
      newBilityPath.push(newPath);
    }
  };
  // 路径查找
  getPath([0], this.g[0]);
  console.log("newBilityPath: ", newBilityPath);
};

graph.getAllPath(); 
//0: (4) [0, 1, 3, 8]
//1: (5) [0, 2, 4, 6, 8]
//2: (5) [0, 2, 5, 7, 8]

参考文档：
https://juejin.im/post/5de7c053518825125d1497e2
https://juejin.im/post/5a32688b5188254dd9366d6a
不使用递归的生成路径方法：https://juejin.im/entry/5d849fb45188255a8b635058