跳至主要內容

图

Kpsmart2025年3月7日大约 12 分钟

图

图是由顶点和边组成的非线性数据结构，可以表示复杂的关系网络。本文将介绍如何使用邻接矩阵和邻接表实现图，以及图的遍历算法（深度优先搜索和广度优先搜索）和常见应用。

图的基本概念

图的术语

  • 顶点(Vertex): 图中的基本单位，也称为节点
  • 边(Edge): 连接两个顶点的线
  • 权重(Weight): 边上的数值，表示两个顶点之间的关系强度或距离
  • 路径(Path): 从一个顶点到另一个顶点的顶点序列
  • 环(Cycle): 起点和终点相同的路径
  • 度(Degree): 与顶点相连的边的数量
  • 邻接(Adjacent): 两个顶点之间有边直接连接
  • 连通图(Connected Graph): 任意两个顶点之间都存在路径的图
  • 有向图(Directed Graph): 边有方向的图
  • 无向图(Undirected Graph): 边没有方向的图
  • 加权图(Weighted Graph): 边有权重的图
  • 非加权图(Unweighted Graph): 边没有权重的图

图的类型

  1. 无向图: 边没有方向，A到B的边也意味着B到A的边
  2. 有向图: 边有方向，A到B的边不一定意味着B到A的边
  3. 加权图: 边有权重，表示两个顶点之间的关系强度或距离
  4. 非加权图: 边没有权重，只表示两个顶点之间是否有连接
  5. 连通图: 任意两个顶点之间都存在路径
  6. 非连通图: 存在至少一对顶点之间没有路径
  7. 完全图: 任意两个顶点之间都有边连接
  8. 二分图: 顶点可以分为两个不相交的集合，每条边连接的两个顶点分别属于这两个集合

图的表示方法

邻接矩阵

邻接矩阵是一个二维数组，用于表示顶点之间的连接关系。对于有n个顶点的图，邻接矩阵是一个n×n的矩阵。

class Graph {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.matrix = [];
    
    // 初始化邻接矩阵
    for (let i = 0; i < numVertices; i++) {
      this.matrix[i] = Array(numVertices).fill(0);
    }
  }
  
  // 添加边（无向图）
  addEdge(v1, v2, weight = 1) {
    if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
      this.matrix[v1][v2] = weight;
      this.matrix[v2][v1] = weight; // 对于无向图，两个方向都要设置
    }
  }
  
  // 添加有向边
  addDirectedEdge(from, to, weight = 1) {
    if (from >= 0 && from < this.numVertices && to >= 0 && to < this.numVertices) {
      this.matrix[from][to] = weight;
    }
  }
  
  // 移除边
  removeEdge(v1, v2) {
    if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
      this.matrix[v1][v2] = 0;
      this.matrix[v2][v1] = 0; // 对于无向图，两个方向都要设置
    }
  }
  
  // 移除有向边
  removeDirectedEdge(from, to) {
    if (from >= 0 && from < this.numVertices && to >= 0 && to < this.numVertices) {
      this.matrix[from][to] = 0;
    }
  }
  
  // 检查两个顶点之间是否有边
  hasEdge(v1, v2) {
    if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
      return this.matrix[v1][v2] !== 0;
    }
    return false;
  }
  
  // 获取顶点的所有邻接顶点
  getNeighbors(vertex) {
    const neighbors = [];
    if (vertex >= 0 && vertex < this.numVertices) {
      for (let i = 0; i < this.numVertices; i++) {
        if (this.matrix[vertex][i] !== 0) {
          neighbors.push(i);
        }
      }
    }
    return neighbors;
  }
  
  // 打印邻接矩阵
  printMatrix() {
    for (let i = 0; i < this.numVertices; i++) {
      console.log(this.matrix[i].join(' '));
    }
  }
}

邻接表

邻接表使用数组和链表（或数组）来表示图。对于每个顶点，都有一个链表来存储与其相邻的顶点。

class Graph {
  constructor(numVertices) {
    this.numVertices = numVertices;
    this.adjList = new Map();
    
    // 初始化所有顶点的邻接表
    for (let i = 0; i < numVertices; i++) {
      this.adjList.set(i, []);
    }
  }
  
  // 添加边（无向图）
  addEdge(v1, v2, weight = 1) {
    if (this.adjList.has(v1) && this.adjList.has(v2)) {
      this.adjList.get(v1).push({ vertex: v2, weight });
      this.adjList.get(v2).push({ vertex: v1, weight }); // 对于无向图，两个方向都要添加
    }
  }
  
  // 添加有向边
  addDirectedEdge(from, to, weight = 1) {
    if (this.adjList.has(from) && this.adjList.has(to)) {
      this.adjList.get(from).push({ vertex: to, weight });
    }
  }
  
  // 移除边
  removeEdge(v1, v2) {
    if (this.adjList.has(v1) && this.adjList.has(v2)) {
      this.adjList.set(v1, this.adjList.get(v1).filter(edge => edge.vertex !== v2));
      this.adjList.set(v2, this.adjList.get(v2).filter(edge => edge.vertex !== v1));
    }
  }
  
  // 移除有向边
  removeDirectedEdge(from, to) {
    if (this.adjList.has(from)) {
      this.adjList.set(from, this.adjList.get(from).filter(edge => edge.vertex !== to));
    }
  }
  
  // 检查两个顶点之间是否有边
  hasEdge(v1, v2) {
    if (this.adjList.has(v1)) {
      return this.adjList.get(v1).some(edge => edge.vertex === v2);
    }
    return false;
  }
  
  // 获取顶点的所有邻接顶点
  getNeighbors(vertex) {
    if (this.adjList.has(vertex)) {
      return this.adjList.get(vertex).map(edge => edge.vertex);
    }
    return [];
  }
  
  // 打印邻接表
  printList() {
    for (const [vertex, edges] of this.adjList.entries()) {
      const edgeList = edges.map(edge => `${edge.vertex}(${edge.weight})`).join(', ');
      console.log(`${vertex} -> ${edgeList}`);
    }
  }
}

图的遍历算法

深度优先搜索 (DFS)

深度优先搜索是一种图遍历算法，它从一个顶点开始，尽可能深地探索一条路径，直到无法继续为止，然后回溯到上一个顶点，继续探索其他路径。

// 使用邻接表实现DFS
class Graph {
  // ... 前面的代码 ...
  
  // 深度优先搜索
  dfs(startVertex, callback) {
    const visited = new Set();
    
    const dfsHelper = (vertex) => {
      // 标记当前顶点为已访问
      visited.add(vertex);
      
      // 处理当前顶点
      if (callback) {
        callback(vertex);
      }
      
      // 递归访问所有未访问的邻接顶点
      const neighbors = this.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor);
        }
      }
    };
    
    // 从起始顶点开始DFS
    dfsHelper(startVertex);
  }
  
  // 非递归实现的DFS
  dfsIterative(startVertex, callback) {
    const visited = new Set();
    const stack = [startVertex];
    
    while (stack.length > 0) {
      const vertex = stack.pop();
      
      if (!visited.has(vertex)) {
        // 标记当前顶点为已访问
        visited.add(vertex);
        
        // 处理当前顶点
        if (callback) {
          callback(vertex);
        }
        
        // 将所有未访问的邻接顶点压入栈中
        const neighbors = this.getNeighbors(vertex);
        for (let i = neighbors.length - 1; i >= 0; i--) {
          const neighbor = neighbors[i];
          if (!visited.has(neighbor)) {
            stack.push(neighbor);
          }
        }
      }
    }
  }
}

广度优先搜索 (BFS)

广度优先搜索是一种图遍历算法，它从一个顶点开始，先访问所有邻接顶点，然后再访问邻接顶点的邻接顶点，以此类推。

// 使用邻接表实现BFS
class Graph {
  // ... 前面的代码 ...
  
  // 广度优先搜索
  bfs(startVertex, callback) {
    const visited = new Set();
    const queue = [startVertex];
    visited.add(startVertex);
    
    while (queue.length > 0) {
      const vertex = queue.shift();
      
      // 处理当前顶点
      if (callback) {
        callback(vertex);
      }
      
      // 将所有未访问的邻接顶点加入队列
      const neighbors = this.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
}

图的应用算法

最短路径算法 - Dijkstra算法

Dijkstra算法用于找到图中一个顶点到其他所有顶点的最短路径。

class Graph {
  // ... 前面的代码 ...
  
  // Dijkstra算法
  dijkstra(startVertex) {
    // 初始化距离和前驱顶点
    const distances = {};
    const previous = {};
    const unvisited = new Set();
    
    // 初始化所有顶点的距离为无穷大
    for (let i = 0; i < this.numVertices; i++) {
      distances[i] = i === startVertex ? 0 : Infinity;
      previous[i] = null;
      unvisited.add(i);
    }
    
    while (unvisited.size > 0) {
      // 找到未访问顶点中距离最小的顶点
      let minVertex = null;
      let minDistance = Infinity;
      
      for (const vertex of unvisited) {
        if (distances[vertex] < minDistance) {
          minVertex = vertex;
          minDistance = distances[vertex];
        }
      }
      
      // 如果没有可达的顶点，则退出循环
      if (minVertex === null || distances[minVertex] === Infinity) {
        break;
      }
      
      // 从未访问集合中移除当前顶点
      unvisited.delete(minVertex);
      
      // 更新邻接顶点的距离
      const neighbors = this.adjList.get(minVertex);
      for (const { vertex: neighbor, weight } of neighbors) {
        if (unvisited.has(neighbor)) {
          const distance = distances[minVertex] + weight;
          
          if (distance < distances[neighbor]) {
            distances[neighbor] = distance;
            previous[neighbor] = minVertex;
          }
        }
      }
    }
    
    return { distances, previous };
  }
  
  // 获取从起点到终点的最短路径
  getShortestPath(startVertex, endVertex) {
    const { distances, previous } = this.dijkstra(startVertex);
    
    if (distances[endVertex] === Infinity) {
      return { distance: Infinity, path: [] };
    }
    
    const path = [];
    let current = endVertex;
    
    while (current !== null) {
      path.unshift(current);
      current = previous[current];
    }
    
    return { distance: distances[endVertex], path };
  }
}

最小生成树 - Kruskal算法

Kruskal算法用于找到图的最小生成树，即连接所有顶点的边的权重之和最小的子图。

class Graph {
  // ... 前面的代码 ...
  
  // Kruskal算法
  kruskal() {
    // 创建边的列表
    const edges = [];
    
    // 收集所有边
    for (const [vertex, edges] of this.adjList.entries()) {
      for (const { vertex: to, weight } of edges) {
        // 对于无向图，只添加一次边
        if (vertex < to) {
          edges.push({ from: vertex, to, weight });
        }
      }
    }
    
    // 按权重排序边
    edges.sort((a, b) => a.weight - b.weight);
    
    // 初始化并查集
    const parent = {};
    const rank = {};
    
    // 初始化每个顶点的父节点为自身
    for (let i = 0; i < this.numVertices; i++) {
      parent[i] = i;
      rank[i] = 0;
    }
    
    // 查找函数（带路径压缩）
    const find = (x) => {
      if (parent[x] !== x) {
        parent[x] = find(parent[x]);
      }
      return parent[x];
    };
    
    // 合并函数（按秩合并）
    const union = (x, y) => {
      const rootX = find(x);
      const rootY = find(y);
      
      if (rootX === rootY) {
        return;
      }
      
      if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
      } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else {
        parent[rootY] = rootX;
        rank[rootX]++;
      }
    };
    
    // 存储最小生成树的边
    const mstEdges = [];
    let mstWeight = 0;
    
    // 遍历所有边
    for (const { from, to, weight } of edges) {
      // 如果加入这条边不会形成环
      if (find(from) !== find(to)) {
        // 加入这条边到最小生成树
        mstEdges.push({ from, to, weight });
        mstWeight += weight;
        
        // 合并两个连通分量
        union(from, to);
        
        // 如果已经有n-1条边，则最小生成树已完成
        if (mstEdges.length === this.numVertices - 1) {
          break;
        }
      }
    }
    
    return { edges: mstEdges, weight: mstWeight };
  }
}

最小生成树 - Prim算法

Prim算法也用于找到图的最小生成树，但它的工作方式与Kruskal算法不同。

class Graph {
  // ... 前面的代码 ...
  
  // Prim算法
  prim(startVertex = 0) {
    // 初始化距离、前驱顶点和已访问集合
    const distances = {};
    const previous = {};
    const visited = new Set();
    
    // 初始化所有顶点的距离为无穷大
    for (let i = 0; i < this.numVertices; i++) {
      distances[i] = i === startVertex ? 0 : Infinity;
      previous[i] = null;
    }
    
    // 存储最小生成树的边
    const mstEdges = [];
    let mstWeight = 0;
    
    while (visited.size < this.numVertices) {
      // 找到未访问顶点中距离最小的顶点
      let minVertex = null;
      let minDistance = Infinity;
      
      for (let i = 0; i < this.numVertices; i++) {
        if (!visited.has(i) && distances[i] < minDistance) {
          minVertex = i;
          minDistance = distances[i];
        }
      }
      
      // 如果没有可达的顶点，则退出循环
      if (minVertex === null || distances[minVertex] === Infinity) {
        break;
      }
      
      // 将当前顶点加入已访问集合
      visited.add(minVertex);
      
      // 如果不是起始顶点，则将边加入最小生成树
      if (minVertex !== startVertex) {
        mstEdges.push({
          from: previous[minVertex],
          to: minVertex,
          weight: distances[minVertex]
        });
        mstWeight += distances[minVertex];
      }
      
      // 更新邻接顶点的距离
      const neighbors = this.adjList.get(minVertex);
      for (const { vertex: neighbor, weight } of neighbors) {
        if (!visited.has(neighbor) && weight < distances[neighbor]) {
          distances[neighbor] = weight;
          previous[neighbor] = minVertex;
        }
      }
    }
    
    return { edges: mstEdges, weight: mstWeight };
  }
}

拓扑排序

拓扑排序用于有向无环图(DAG)，它将图中的顶点排序成一个线性序列，使得对于图中的每条有向边(u, v)，顶点u在序列中都出现在顶点v之前。

class Graph {
  // ... 前面的代码 ...
  
  // 拓扑排序（使用DFS）
  topologicalSort() {
    const visited = new Set();
    const stack = [];
    
    const dfsTopological = (vertex) => {
      visited.add(vertex);
      
      const neighbors = this.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsTopological(neighbor);
        }
      }
      
      // 在回溯时将顶点加入栈中
      stack.unshift(vertex);
    };
    
    // 对每个未访问的顶点执行DFS
    for (let i = 0; i < this.numVertices; i++) {
      if (!visited.has(i)) {
        dfsTopological(i);
      }
    }
    
    return stack;
  }
  
  // 检测图中是否有环（使用DFS）
  hasCycle() {
    const visited = new Set();
    const recursionStack = new Set();
    
    const hasCycleUtil = (vertex) => {
      // 将顶点加入已访问集合和递归栈
      visited.add(vertex);
      recursionStack.add(vertex);
      
      // 递归访问所有邻接顶点
      const neighbors = this.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        // 如果邻接顶点未访问，则递归检查
        if (!visited.has(neighbor)) {
          if (hasCycleUtil(neighbor)) {
            return true;
          }
        } 
        // 如果邻接顶点在递归栈中，则存在环
        else if (recursionStack.has(neighbor)) {
          return true;
        }
      }
      
      // 回溯时从递归栈中移除顶点
      recursionStack.delete(vertex);
      return false;
    };
    
    // 对每个未访问的顶点执行DFS
    for (let i = 0; i < this.numVertices; i++) {
      if (!visited.has(i) && hasCycleUtil(i)) {
        return true;
      }
    }
    
    return false;
  }
}

图的应用示例

社交网络分析

// 创建社交网络图
const socialNetwork = new Graph(6);

// 添加好友关系（无向边）
socialNetwork.addEdge(0, 1); // 用户0和用户1是好友
socialNetwork.addEdge(0, 2);
socialNetwork.addEdge(1, 3);
socialNetwork.addEdge(2, 3);
socialNetwork.addEdge(3, 4);
socialNetwork.addEdge(4, 5);

// 打印社交网络
console.log("社交网络关系:");
socialNetwork.printList();

// 查找用户的所有好友
console.log("用户3的所有好友:", socialNetwork.getNeighbors(3));

// 查找两个用户之间的关系路径（使用BFS）
console.log("用户0到用户5的关系路径:");
const path = [];
socialNetwork.bfs(0, (vertex) => {
  path.push(vertex);
  if (vertex === 5) {
    return true; // 找到目标用户，停止搜索
  }
  return false;
});
console.log(path);

// 计算用户的影响力（度中心性）
const calculateInfluence = (graph, vertex) => {
  return graph.getNeighbors(vertex).length;
};

for (let i = 0; i < 6; i++) {
  console.log(`用户${i}的影响力:`, calculateInfluence(socialNetwork, i));
}

地图路径规划

// 创建城市地图
const cityMap = new Graph(6);

// 添加道路（加权无向边）
// 顶点代表城市，边代表道路，权重代表距离
cityMap.addEdge(0, 1, 5);  // 城市0到城市1的距离为5公里
cityMap.addEdge(0, 2, 3);
cityMap.addEdge(1, 3, 6);
cityMap.addEdge(1, 2, 2);
cityMap.addEdge(2, 3, 4);
cityMap.addEdge(2, 4, 2);
cityMap.addEdge(3, 4, 1);
cityMap.addEdge(3, 5, 8);
cityMap.addEdge(4, 5, 3);

// 打印城市地图
console.log("城市地图:");
cityMap.printList();

// 查找两个城市之间的最短路径
const { distance, path } = cityMap.getShortestPath(0, 5);
console.log(`从城市0到城市5的最短距离: ${distance}公里`);
console.log(`最短路径: ${path.join(' -> ')}`);

// 查找连接所有城市的最小生成树（最小道路网络）
const { edges, weight } = cityMap.kruskal();
console.log("最小道路网络:");
for (const { from, to, weight } of edges) {
  console.log(`城市${from} - 城市${to}: ${weight}公里`);
}
console.log(`总长度: ${weight}公里`);

任务调度

// 创建任务依赖图（有向图）
const taskGraph = new Graph(6);

// 添加任务依赖关系（有向边）
// 顶点代表任务，边表示依赖关系（from依赖to）
taskGraph.addDirectedEdge(0, 1); // 任务0依赖任务1
taskGraph.addDirectedEdge(0, 2);
taskGraph.addDirectedEdge(1, 3);
taskGraph.addDirectedEdge(2, 3);
taskGraph.addDirectedEdge(3, 4);
taskGraph.addDirectedEdge(4, 5);

// 打印任务依赖关系
console.log("任务依赖关系:");
taskGraph.printList();

// 检查是否有循环依赖
if (taskGraph.hasCycle()) {
  console.log("存在循环依赖，无法完成所有任务");
} else {
  // 获取任务的执行顺序（拓扑排序）
  const executionOrder = taskGraph.topologicalSort();
  console.log("任务执行顺序:", executionOrder.join(' -> '));
}

图的性能分析

不同表示方法的时间复杂度比较

操作邻接矩阵邻接表
添加顶点O(V²)O(1)
添加边O(1)O(1)
移除顶点O(V²)O(V + E)
移除边O(1)O(E)
查找边O(1)O(V)
获取所有邻接顶点O(V)O(E)
存储空间O(V²)O(V + E)

其中，V是顶点数量，E是边的数量。

图算法的时间复杂度

算法邻接矩阵邻接表
DFSO(V²)O(V + E)
BFSO(V²)O(V + E)
Dijkstra（不使用优先队列）O(V²)O(V² + E)
Dijkstra（使用优先队列）O(V² log V)O((V + E) log V)
KruskalO(E log E)O(E log E)
Prim（不使用优先队列）O(V²)O(V² + E)
Prim（使用优先队列）O(V² log V)O((V + E) log V)
拓扑排序O(V²)O(V + E)

邻接矩阵与邻接表的选择

  • 邻接矩阵：

    • 优点：查找和修改边的操作时间复杂度为O(1)
    • 缺点：空间复杂度为O(V²)，对于稀疏图浪费空间
    • 适用场景：边较多的稠密图，频繁查询两个顶点之间是否有边

  • 邻接表：

    • 优点：空间复杂度为O(V + E)，对于稀疏图节省空间
    • 缺点：查找特定边的时间复杂度为O(V)
    • 适用场景：边较少的稀疏图，需要快速获取顶点的所有邻接顶点

总结

图是一种非常重要的数据结构，广泛应用于各种场景：

  1. 社交网络：用户之间的关系网络
  2. 地图导航：城市之间的道路网络
  3. 网络拓扑：计算机网络中的节点连接
  4. 任务调度：任务之间的依赖
  5. 推荐系统：物品或用户之间的相似性网络