10.md

图

图是什么

1. 图由边的集合和顶点的集合组成，连接顶点的“道路”称为边
2. 图的顶点如果是有序的，可以称为有向图，如果图的顶点是无序的，称为无序图
3. 图中的一系列顶点构成路径，路径中所有的顶点由边连接，路径的长度用用第一个顶点到最后一个顶点之间边的数量表示，指向自身的顶点的路径称为环
4. 圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同，有向图和无向图，只要没有重复边和重复点的圈，就是一个简单圈
5. 如果两个顶点之间有路径，那么这两个顶点就是强连通，如果有向图所有顶点都是强连通的，那么这个有向图也是强连通
6. 邻接法：将边存储为由顶点的相邻顶点构成的数组，并以此顶点作为索引

邻接法图的实现

• 代码

function Graph(v) {
  this.vertices = v;
  this.edges = 0;
  this.store = [];
  this.add = add;
  this.show = show;
  this.initMarked = initMarked;
  for (var i = 0; i < v; i++) {
    this.store[i] = [];
  }
  this.marked = [];
  this.dfs = dfs;
  this.bfs = bfs;
  this.edgeTo = [];
  this.shortestPath = shortestPath;
}
var add = function(v, w) {
  this.store[v].push(w);
  this.store[w].push(v);
  this.edges++;
};

var show = function() {
  var store = this.store;
  for (var i = 0; i < store.length; i++) {
    var arr = [];
    for (var j = 0; j < store[i].length; j++) {
      arr.push(store[i][j]);
    }
    console.log(i, arr);
  }
};
// 深度优先
var dfsArr = [];
var dfs = function(v) {
  this.marked[v] = true;
  if (v !== undefined) {
    dfsArr.push(v);
  }
  for (var i = 0; i < this.store[v].length; i++) {
    var w = this.store[v][i];
    if (!this.marked[w]) {
      this.dfs(w);
    }
  }
};
var initMarked = function() {
  for (var i = 0; i < this.vertices; i++) {
    this.marked[i] = false;
  }
};
// 广度优先
var bfsArr = [];
var bfs = function(v) {
  var queue = [];
  this.marked[v] = true;
  queue.push(v);
  while (queue.length > 0) {
    var w = queue.shift();
    if (w !== undefined) {
      bfsArr.push(w);
    }
    for (var i = 0; i < this.store[w].length; i++) {
      var n = this.store[w][i];
      if (!this.marked[n]) {
        // 最短路径用，广度优先可以忽略
        this.edgeTo[n] = w;
        this.marked[n] = true;
        queue.push(n);
      }
    }
  }
};
// 广度优先最短路径
var shortestPath = function(v) {
  var start = 0;
  var arr = [];
  if (!this.marked[v]) {
    return [];
  }
  for (var i = v; i != start; i = this.edgeTo[i]) {
    arr.push(i);
  }
  return start + "->" + arr.reverse().join("->");
};
var graph = new Graph(6);
graph.add(5, 2);
graph.add(5, 0);
graph.add(4, 0);
graph.add(4, 1);
graph.add(2, 3);
graph.add(3, 1);
graph.show();
graph.initMarked();
graph.dfs(0);
console.log("dfs:", dfsArr);
graph.initMarked();
graph.bfs(0);
console.log("bfs:", bfsArr);
console.log("广度优先最短路径:", graph.shortestPath(3));
// 图的结构
// 0 [ 5, 4 ]
// 1 [ 4, 3 ]
// 2 [ 5, 3 ]
// 3 [ 2, 1 ]
// 4 [ 0, 1 ]
// 5 [ 2, 0 ]
// dfs: [ 0, 5, 2, 3, 1, 4 ]
// bfs: [ 0, 5, 4, 2, 1, 3 ]
// 广度优先最短路径: 0->5->2->3

• 效果图：

;

拓扑排序

• 拓扑排序是什么

1. 拓扑排序是一个有向无环图（DAG）
2. 拓扑排序满足两个条件：每个顶点只出现一次，若存在顶点 A 到顶点 B 的路径，那么在序列中顶点 A 要出现在顶点 B 前面

• 拓扑排序的实现

1. 在 DAG 选择一个没有前驱（入度为 0）的顶点，push 到队列中
2. 删除该顶点和以它为起点的有向边
3. 重复 1，2，直到队列为空

;

• 实现

function Graph(v) {
  this.vertices = v;
  this.store = [];
  this.queue = [];
  this.indegree = [];
  this.add = add;
  this.topSort = topSort;
  for (var i = 0; i < this.vertices; i++) {
    this.indegree[i] = 0;
    this.store[i] = [];
  }
}
var add = function(v, w) {
  this.store[v].push(w);
  this.indegree[w]++;
};
// 1. 在DAG图中找到一个没有前驱的顶点，push到队列中
// 2. 从图中删除该顶点和所有以他为起点的有向边
// 3. 重复1，2，直到DAG为空
function topSort() {
  var result = [];
  var queue = [];
  for (var i = 0; i < this.vertices; i++) {
    if (this.indegree[i] === 0) {
      // 步骤1:在DAG图中选择一个没有前驱的顶点，push到队列中
      queue.push(i);
    }
  }
  // 重复1，2，直到DAG为空
  while (queue.length > 0) {
    // 步骤2:从图中删除该顶点和所有以他为起点的有向边
    var v = queue.shift();
    if (v !== undefined) {
      result.push(v);
    }
    for (var i = 0; i < this.store[v].length; i++) {
      var n = this.store[v][i];
      --this.indegree[n];
      if (this.indegree[n] === 0) {
        queue.push(n);
      }
    }
  }
  return result;
}

var graph = new Graph(6);
graph.add(5, 2);
graph.add(5, 0);
graph.add(4, 0);
graph.add(4, 1);
graph.add(2, 3);
graph.add(3, 1);
console.log("拓扑排序:", graph.topSort());
// 拓扑排序: [ 4, 5, 2, 0, 3, 1 ]