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

学习背景

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

最后编辑于：2020.03.31 10:38:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,544评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,430评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,764评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,193评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,216评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,182评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,063评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,917评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,329评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,543评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,722评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,425评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,019评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,671评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,825评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,729评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,614评论 2赞 353

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

学习背景

概念

图的两种存储结构

图的两种遍历方法

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

推荐阅读更多精彩内容