图的概念和用途

图的概念和用途

• 图由边的集合和顶点的集合组成。比如每一个城市就是一个顶点，每一条道路就是一条边。

• 图的常见应用包括社交网络分析、网络拓扑、路径搜索、推荐系统、路由算法等。

• 顶点也有权重，也称为成本。如果一个图的顶点对是有序的，则称之为有向图。在对有向图中的顶点排序后，便可以在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。流程图就是有向图的一个例子。

• 如果图是无序的，则称之为无序图或无向图。

• 从一个顶点走到另一个顶点的这组边称为路径。路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间的边的数量表示。指向自身顶点组成的路径称为环，环的长度为 0。

• 圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图，只要没有重复顶点的圈就是一个简单圈，除了第一个和最后一个顶点以外，路径的其他顶点有重复的圈称为平凡圈。

• 如果两个顶点之间有路径，那么这两个顶点之间就是强连通的。如果有向图的所有顶点都是强连通的，那么这个有向图也是强连通的。

• 图和邻接表

邻接表适合表示稀疏图，即顶点较少但是边数量较多的图。

• 图和邻接矩阵

邻接表适合表示稠密图，即顶点较多且边数量也较多的图。

• 图遍历

图的代码实现

function Graph(v) {
  this.vertices = v; // 顶点
  this.edges = 0; // 边的数量
  this.adj = []; // 邻接表
  this.marked = []; // 存储顶点的状态，是否被访问过
  // 创建二维数组，邻接表是一个二维数组
  for (var i = 0; i < this.vertices; i++) {
    this.adj[i] = [];
    this.marked[i] = false;
  }
  this.shortestPath = []; // 用一个数组来记录最短路径所有的边
  this.hasPath = hasPath; // 判断是否有路径
  this.findShortestPath = findShortestPath; // 寻找最短路径
  this.addEdge = addEdge; // 添加边
  this.showGraph = showGraph; // 打印图
  this.dfs = dfs; // 深度优先搜索
  this.bfs = bfs; // 广度优先搜索
}

// 添加边，参数是两个顶点
function addEdge(v, w) {
  this.adj[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}

// 打印图，其实就是打印邻接表
function showGraph() {
  for (var i = 0; i < this.vertices; i++) {
    var edges = "";
    for (var j = 0; j < this.vertices; j++) {
      // 判断两个顶点之间是否有边
      if (this.adj[i][j]) {
        edges += this.adj[i][j] + " ";
      }
    }
    console.log(i + "->" + edges);
  }
}

// 深度优先搜索
function dfs(v) {
  // 标记初始顶点已经被访问过
  this.marked[v] = true;
  // 如果该顶点在邻接表中有值，说明图中有与之相连的边，可以打印该顶点
  if (this.adj[v]) {
    console.log("深度优先搜索结果：顶点 " + v + " 已经被访问过了！");
  }
  // 遍历跟该顶点项相连的其他顶点
  for (var w in this.adj[v]) {
    var current = this.adj[v][w];
    // 如果当前顶点没被访问过
    if (!this.marked[current]) {
      // 递归遍历
      this.dfs(current);
    }
  }
}

// 广度优先搜索
function bfs(v) {
  var queue = []; // 队列
  this.marked[v] = true; // 标记初始顶点已经被访问过
  queue.push(v); // 将访问过的顶点放入队列中
  while (queue.length > 0) {
    var q = queue.shift(); // 逐个出列，并寻找与出列顶点相连的其他顶点
    if (q !== undefined) {
      console.log("广度优先搜索结果：顶点 " + q + " 已经被访问过了！");
    }
    // 遍历与出列顶点相连的其他顶点
    for (var w in this.adj[q]) {
      var current = this.adj[q][w];
      // 如果当前节点没被访问过
      if (!this.marked[current]) {
        this.marked[current] = true; // 标记为以访问
        this.shortestPath[current] = q; // 说明有一条边可以从 current 顶点到 q 顶点
        queue.push(current); // 并将该顶点放入队列中
      }
    }
  }
}

// 判断是否有路径
function hasPath(v) {
  // 如果当前顶点有被访问，说明就有路径
  return this.marked[v];
}

// 寻找最短路径，它的实现是基于广度优先搜索的
function findShortestPath(v) {
  var source = 0;
  if (!this.hasPath(v)) {
    return undefined;
  }
  var path = [];
  for (var i = v; i !== source; i = this.shortestPath[i]) {
    path.push(i);
  }
  path.push(source);
  return path;
}

var graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.showGraph();
// graph.dfs(0);
graph.bfs(0);
var paths = graph.findShortestPath(4); // 寻找从顶点 0 到顶点 4 的最短路径
// 方便展示最短路径
var str = "";
while (paths.length) {
  if (paths.length > 1) {
    str += paths.pop() + "->";
  } else {
    str += paths.pop();
  }
}
console.log(str);

图的另一种实现

var Queue = function() {
  var items = [];
  //入队
  this.enqueue = function(element) {
    items.push(element);
  };
  // 出队
  this.dequeue = function() {
    return items.shift();
  };
  //查看队列头
  this.front = function() {
    return items[0];
  };
  //检查队列是否为空
  this.isEmpty = function() {
    return items.length === 0;
  };
  //队列大小
  this.size = function() {
    return items.length;
  };
};
/*
 * 图
 * 1、可用于实现地图、社交网络等
 * 2、有向图和无向图
 * 3、表示图结构的方式：邻接矩阵、邻接表
 * 4、图遍历：广度优先和深度优先
 * 5、每个节点有三种状态：未发现、已发现、已探索
 */
var Graph = function() {
  var vertices = []; // 图的顶点，以数组形式存储每个顶点
  var edges = {}; // 图的边，以对象形式存储每个顶点包含的边

  // 添加顶点
  this.addVertex = function(v) {
    vertices.push(v);
    edges[v] = [];
  };

  // 添加边
  this.addEdge = function(a, b) {
    edges[a].push(b);
    edges[b].push(a);
    console.log(edges);
  };

  // 打印图的邻接表
  this.print = function() {
    var str = "";
    for (var i = 0; i < vertices.length; i++) {
      var vertice = vertices[i];
      str += vertice + " => ";
      var edge = edges[vertice];
      for (var j = 0; j < edge.length; j++) {
        str += edge[j] + " ";
      }
      str += "\n";
    }
    console.log(str);
  };

  // 广度优先遍历，white为未发现，grey为已发现，black为已探索
  var initColor = function() {
    // 将所有顶点的颜色置为白色，表示未发现
    var color = {};
    for (var i = 0; i < vertices.length; i++) {
      color[vertices[i]] = "white";
    }
    return color;
  };
  this.bfs = function(v, callback) {
    var color = initColor();
    var queue = new Queue();
    queue.enqueue(v);
    while (!queue.isEmpty()) {
      var currVertice = queue.dequeue(); // 顶点出列
      var currEdge = edges[currVertice]; // 存储该顶点相关的边
      for (var i = 0; i < currEdge.length; i++) {
        // 遍历该顶点相关的所有边
        var nextVertice = currEdge[i]; // 与该顶点相连的其他所有顶点
        if (color[nextVertice] == "white") {
          // 未发现的顶点全部入列，并标识为已发现
          queue.enqueue(nextVertice);
          color[nextVertice] = "grey";
        }
      }
      color[currVertice] = "black"; // 遍历结束后将该顶点标识为已探索
      if (callback) {
        // 回调函数
        callback(currVertice);
      }
    }
  };

  // 带最短路径的广度优先算法
  this.BFS = function(v, callback) {
    var color = initColor();
    var queue = new Queue();
    var distance = {}; // 存储某个顶点到其它顶点的距离
    var backPoint = {}; // 存储某个顶点的回溯点
    for (var i = 0; i < vertices.length; i++) {
      distance[vertices[i]] = 0;
      backPoint[vertices[i]] = null;
    }
    queue.enqueue(v);
    while (!queue.isEmpty()) {
      var currVertice = queue.dequeue(); // 顶点出列
      var currEdge = edges[currVertice]; // 存储该顶点相关的边
      for (var i = 0; i < currEdge.length; i++) {
        // 遍历该顶点相关的所有边
        var nextVertice = currEdge[i]; // 与该顶点相连的其他所有顶点
        if (color[nextVertice] == "white") {
          // 未发现的顶点全部入列，并标识为已发现
          queue.enqueue(nextVertice);
          color[nextVertice] = "grey";
          backPoint[nextVertice] = currVertice; // 设置回溯点
          distance[nextVertice] = distance[currVertice] + 1; // 设置距离
        }
      }
      color[currVertice] = "black"; // 遍历结束后将该顶点标识为已探索
      if (callback) {
        // 回调函数
        callback(currVertice);
      }
    }
    return {
      backPoint: backPoint,
      distance: distance
    };
  };

  // 深度优先算法
  var dfs = function(u, color, callback) {
    color[u] = "grey";
    var n = edges[u];
    for (var i = 0; i < n.length; i++) {
      var w = n[i];
      if (color[w] == "white") {
        dfs(w, color, callback);
      }
    }
    color[u] = "black";
    if (callback) {
      callback(u);
    }
  };
  this.DFS = function(v, callback) {
    var color = initColor();
    dfs(v, color, callback);
  };
};
var g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("A", "D");
g.addEdge("C", "D");
g.addEdge("B", "E");
g.addEdge("F", "B");
g.print();

var Stack = function() {
  var items = []; //私有

  // push 栈顶添加元素
  this.push = function(element) {
    items.push(element);
  };
  // pop 移除栈顶元素
  this.pop = function() {
    return items.pop();
  };
  // peek 检查栈顶
  this.peek = function() {
    return items[items.length - 1];
  };

  // 检查栈 是否为空
  this.isEmpty = function() {
    return items.length == 0;
  };

  // 清除栈
  this.clear = function() {
    items = [];
  };

  // 获取栈的大小
  this.size = function() {
    return items.length;
  };

  // 检查items
  this.getItems = function() {
    return items;
  };
};

// 实现最短路径算法：从当前点出发，寻找回溯点。广度优先算法保证了每个顶点的回溯点是最近的。
var paths = g.BFS("A");
var ShortestPath = function(from, to) {
  var currVertice = to;
  var path = new Stack();
  while (currVertice != from) {
    path.push(currVertice);
    currVertice = paths.backPoint[currVertice];
  }
  path.push(currVertice);
  var str = "";
  while (!path.isEmpty()) {
    str += path.pop() + "-";
  }
  str = str.slice(0, str.length - 1);
  console.log(from + "到" + to + "的最短路径为：" + str);
};
ShortestPath("A", "F");

图的深度优先遍历 ✅

// 递归实现，使用记忆化优化
// 每次访问一个节点就立刻沿着它的第一个邻居一路往深处走，走到底之后再回溯访问其他邻居。visited 集合防止重复访问（用于处理有环图）
// 时间复杂度是 O(V+E)，V 是顶点数，E 是边数。每个顶点访问一次，每条边检查一次
// 空间复杂度是 O(V)，visited 最多存 V 个顶点，递归调用栈最深也是 V 层（退化为链状时）
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: [],
  F: []
};

const dfsGraph = (graph, start) => {
  const visited = new Set();

  const dfs = (node) => {
    // if (visited.has(node)) return; // 已经进函数了才返回，多了一层函数调用开销
    visited.add(node);
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) { // 提前过滤，不进无用的递归
        dfs(neighbor);
      }
    }
  };

  dfs(start);
};

dfsGraph(graph, "A"); // A B D E C F

图的广度优先遍历 ✅

// 用队列逐层展开，先访问距起点近的节点
// 入队时就标记 visited，确保每个节点只入队一次，不会重复处理。用头指针代替 shift() 避免数组整体搬移的性能损耗
// 时间复杂度是 O(V+E)，每个顶点入队一次、出队一次，每条边最多检查两次（无向图）
// 空间复杂度是 O(V)，visited 和队列最多存 V 个顶点
const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: [],
  F: []
};

const bfsGraph = (graph, start) => {
  const visited = new Set();
  const queue = [start];
  let head = 0;

  while (head < queue.length) {
    // const node = queue.shift(); // 优化前时间复杂度为 O(V²+E)
    const node = queue[head++];

    // if (visited.has(node)) continue; // visited 在出队时才标记，导致同一节点可能被多次入队
    // visited.add(node);

    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) { // 提前过滤，入队时就标记，节点只入队一次
        visited.add(node);
        queue.push(neighbor);
      }
    }
  }
};

bfsGraph(graph, "A"); // A B C D E F

克隆图 ✅

题目地址 (opens new window)

// 使用 DFS 实现
// 时间复杂度是 O(V + E)，每个节点入栈一次，每条边遍历一次（无向图每条边检查两次）
// 空间复杂度是 O(V)，visited 存 V 个映射，栈最深 V 层（退化为链状时）
var cloneGraph = function(node) {
  if (node === null) return null;

  const visited = new Map();
  const stack = [node];
  const clone = new Node(node.val, []);

  visited.set(node, clone);

  while (stack.length) {
    const cur = stack.pop();
    const cloneCur = visited.get(cur);

    for (const neighbor of cur.neighbors) {
      if (!visited.has(neighbor)) {
        const cloneNeigbor = new Node(neighbor.val, []);
        visited.set(neighbor, cloneNeigbor);
        stack.push(neighbor);
      }
      cloneCur.neighbors.push(visited.get(neighbor));
    }
  }

  return clone;
};