React Router
Graphtheory

图的遍历算法

深入理解深度优先搜索（DFS）和广度优先搜索（BFS）算法

图的遍历算法

图的遍历是指访问图中所有顶点的过程，主要有两种经典算法：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种递归的遍历算法，它沿着图的边尽可能深入地访问顶点。

DFS 的基本思想

  1. 从起始顶点开始
  2. 访问当前顶点
  3. 递归访问未访问的邻居顶点
  4. 当无法继续深入时，回溯到上一个顶点

DFS 实现

// 深度优先搜索（递归版本）
function dfsRecursive(graph, start, visited = new Set()) {
  // 访问当前顶点
  console.log(`访问顶点: ${start}`);
  visited.add(start);
  
  // 获取邻居顶点
  const neighbors = graph.getNeighbors(start);
  
  // 递归访问未访问的邻居
  for (const neighbor of neighbors) {
    const neighborVertex = neighbor.to || neighbor;
    if (!visited.has(neighborVertex)) {
      dfsRecursive(graph, neighborVertex, visited);
    }
  }
}

// 深度优先搜索（迭代版本）
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const current = stack.pop();
    
    if (!visited.has(current)) {
      console.log(`访问顶点: ${current}`);
      visited.add(current);
      
      // 将未访问的邻居压入栈中
      const neighbors = graph.getNeighbors(current);
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const neighbor = neighbors[i];
        const neighborVertex = neighbor.to || neighbor;
        if (!visited.has(neighborVertex)) {
          stack.push(neighborVertex);
        }
      }
    }
  }
  
  return visited;
}

DFS 的应用

1. 连通分量检测

// 查找连通分量
function findConnectedComponents(graph) {
  const visited = new Set();
  const components = [];
  
  const vertices = graph.getVertices ? graph.getVertices() : graph.vertices;
  
  for (const vertex of vertices) {
    if (!visited.has(vertex)) {
      const component = [];
      dfsComponent(graph, vertex, visited, component);
      components.push(component);
    }
  }
  
  return components;
}

// DFS 查找连通分量
function dfsComponent(graph, vertex, visited, component) {
  visited.add(vertex);
  component.push(vertex);
  
  const neighbors = graph.getNeighbors(vertex);
  for (const neighbor of neighbors) {
    const neighborVertex = neighbor.to || neighbor;
    if (!visited.has(neighborVertex)) {
      dfsComponent(graph, neighborVertex, visited, component);
    }
  }
}

2. 拓扑排序

// 拓扑排序（仅适用于有向无环图）
function topologicalSort(graph) {
  const visited = new Set();
  const recStack = new Set();
  const result = [];
  
  const vertices = graph.getVertices ? graph.getVertices() : graph.vertices;
  
  for (const vertex of vertices) {
    if (!visited.has(vertex)) {
      if (!dfsTopological(graph, vertex, visited, recStack, result)) {
        throw new Error('图中存在环，无法进行拓扑排序');
      }
    }
  }
  
  return result.reverse();
}

// DFS 拓扑排序
function dfsTopological(graph, vertex, visited, recStack, result) {
  visited.add(vertex);
  recStack.add(vertex);
  
  const neighbors = graph.getNeighbors(vertex);
  for (const neighbor of neighbors) {
    const neighborVertex = neighbor.to || neighbor;
    
    if (!visited.has(neighborVertex)) {
      if (!dfsTopological(graph, neighborVertex, visited, recStack, result)) {
        return false;
      }
    } else if (recStack.has(neighborVertex)) {
      return false; // 发现环
    }
  }
  
  recStack.delete(vertex);
  result.push(vertex);
  return true;
}

3. 路径查找

// 查找从起点到终点的所有路径
function findAllPathsDFS(graph, start, end) {
  const paths = [];
  const visited = new Set();
  
  function dfsPath(current, path) {
    path.push(current);
    visited.add(current);
    
    if (current === end) {
      paths.push([...path]);
    } else {
      const neighbors = graph.getNeighbors(current);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor;
        if (!visited.has(neighborVertex)) {
          dfsPath(neighborVertex, path);
        }
      }
    }
    
    path.pop();
    visited.delete(current);
  }
  
  dfsPath(start, []);
  return paths;
}

广度优先搜索（BFS）

广度优先搜索是一种层次遍历算法，它先访问所有相邻顶点，再访问下一层顶点。

BFS 的基本思想

  1. 从起始顶点开始
  2. 访问当前顶点的所有邻居
  3. 将邻居加入队列
  4. 从队列中取出下一个顶点继续访问

BFS 实现

// 广度优先搜索
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);
    
    console.log(`访问顶点: ${current}`);
    
    // 访问所有邻居
    const neighbors = graph.getNeighbors(current);
    for (const neighbor of neighbors) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visited.has(neighborVertex)) {
        visited.add(neighborVertex);
        queue.push(neighborVertex);
      }
    }
  }
  
  return result;
}

// BFS 带层级信息
function bfsWithLevels(graph, start) {
  const visited = new Set();
  const queue = [{ vertex: start, level: 0 }];
  const levels = new Map();
  
  visited.add(start);
  
  while (queue.length > 0) {
    const { vertex, level } = queue.shift();
    
    if (!levels.has(level)) {
      levels.set(level, []);
    }
    levels.get(level).push(vertex);
    
    console.log(`访问顶点: ${vertex} (层级: ${level})`);
    
    const neighbors = graph.getNeighbors(vertex);
    for (const neighbor of neighbors) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visited.has(neighborVertex)) {
        visited.add(neighborVertex);
        queue.push({ vertex: neighborVertex, level: level + 1 });
      }
    }
  }
  
  return levels;
}

BFS 的应用

1. 最短路径（无权图）

// 无权图的最短路径
function shortestPathBFS(graph, start, end) {
  const visited = new Set();
  const queue = [{ vertex: start, path: [start] }];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const { vertex, path } = queue.shift();
    
    if (vertex === end) {
      return path;
    }
    
    const neighbors = graph.getNeighbors(vertex);
    for (const neighbor of neighbors) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visited.has(neighborVertex)) {
        visited.add(neighborVertex);
        queue.push({
          vertex: neighborVertex,
          path: [...path, neighborVertex]
        });
      }
    }
  }
  
  return null; // 没有路径
}

2. 层级遍历

// 层级遍历（类似树的层序遍历）
function levelOrderTraversal(graph, start) {
  const visited = new Set();
  const queue = [{ vertex: start, level: 0 }];
  const levels = [];
  
  visited.add(start);
  
  while (queue.length > 0) {
    const { vertex, level } = queue.shift();
    
    if (levels.length <= level) {
      levels.push([]);
    }
    levels[level].push(vertex);
    
    const neighbors = graph.getNeighbors(vertex);
    for (const neighbor of neighbors) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visited.has(neighborVertex)) {
        visited.add(neighborVertex);
        queue.push({ vertex: neighborVertex, level: level + 1 });
      }
    }
  }
  
  return levels;
}

3. 社交网络中的朋友推荐

// 基于BFS的朋友推荐
class FriendRecommender {
  constructor(socialGraph) {
    this.graph = socialGraph;
  }
  
  // 推荐朋友（基于共同朋友数量）
  recommendFriends(userId, maxDistance = 2) {
    const visited = new Set();
    const queue = [{ userId, distance: 0 }];
    const recommendations = new Map();
    
    visited.add(userId);
    
    while (queue.length > 0) {
      const { userId: current, distance } = queue.shift();
      
      if (distance > 0 && distance <= maxDistance) {
        const commonFriends = this.getCommonFriendsCount(userId, current);
        if (!recommendations.has(current)) {
          recommendations.set(current, { distance, commonFriends });
        }
      }
      
      if (distance < maxDistance) {
        const friends = this.graph.getFriends(current);
        for (const friend of friends) {
          if (!visited.has(friend)) {
            visited.add(friend);
            queue.push({ userId: friend, distance: distance + 1 });
          }
        }
      }
    }
    
    // 按共同朋友数量排序
    return Array.from(recommendations.entries())
      .sort((a, b) => b[1].commonFriends - a[1].commonFriends)
      .map(([userId, info]) => ({
        userId,
        distance: info.distance,
        commonFriends: info.commonFriends
      }));
  }
  
  // 计算共同朋友数量
  getCommonFriendsCount(user1, user2) {
    const friends1 = new Set(this.graph.getFriends(user1));
    const friends2 = new Set(this.graph.getFriends(user2));
    
    return Array.from(friends1).filter(friend => friends2.has(friend)).length;
  }
}

遍历算法的比较

时间复杂度

// 时间复杂度分析
const timeComplexity = {
  "邻接矩阵": {
    "DFS": "O(V²)",
    "BFS": "O(V²)"
  },
  "邻接表": {
    "DFS": "O(V + E)",
    "BFS": "O(V + E)"
  }
};

console.log("遍历算法时间复杂度:");
console.log(JSON.stringify(timeComplexity, null, 2));

空间复杂度

// 空间复杂度分析
const spaceComplexity = {
  "DFS": {
    "递归": "O(V) - 调用栈深度",
    "迭代": "O(V) - 栈空间"
  },
  "BFS": {
    "队列": "O(V) - 队列大小"
  }
};

console.log("遍历算法空间复杂度:");
console.log(JSON.stringify(spaceComplexity, null, 2));

选择指南

// 算法选择指南
function chooseTraversalAlgorithm(graph, problem) {
  const recommendations = {
    "查找最短路径": "BFS",
    "拓扑排序": "DFS",
    "连通分量": "DFS",
    "层级遍历": "BFS",
    "路径查找": "DFS",
    "环检测": "DFS",
    "朋友推荐": "BFS"
  };
  
  return recommendations[problem] || "根据具体需求选择";
}

实际应用示例

1. 迷宫求解

// 迷宫求解（使用BFS）
class MazeSolver {
  constructor(maze) {
    this.maze = maze;
    this.rows = maze.length;
    this.cols = maze[0].length;
  }
  
  // 检查位置是否有效
  isValid(row, col) {
    return row >= 0 && row < this.rows && 
           col >= 0 && col < this.cols && 
           this.maze[row][col] !== '#';
  }
  
  // 获取邻居位置
  getNeighbors(row, col) {
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const neighbors = [];
    
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (this.isValid(newRow, newCol)) {
        neighbors.push([newRow, newCol]);
      }
    }
    
    return neighbors;
  }
  
  // 求解迷宫
  solve(start, end) {
    const visited = new Set();
    const queue = [{ pos: start, path: [start] }];
    
    visited.add(start.join(','));
    
    while (queue.length > 0) {
      const { pos, path } = queue.shift();
      const [row, col] = pos;
      
      if (row === end[0] && col === end[1]) {
        return path;
      }
      
      const neighbors = this.getNeighbors(row, col);
      for (const neighbor of neighbors) {
        const key = neighbor.join(',');
        if (!visited.has(key)) {
          visited.add(key);
          queue.push({
            pos: neighbor,
            path: [...path, neighbor]
          });
        }
      }
    }
    
    return null; // 没有解
  }
}

// 使用示例
const maze = [
  ['S', '.', '.', '#', '.'],
  ['.', '#', '.', '.', '.'],
  ['.', '.', '.', '#', '.'],
  ['#', '#', '.', '#', '.'],
  ['.', '.', '.', '.', 'E']
];

const solver = new MazeSolver(maze);
const solution = solver.solve([0, 0], [4, 4]);
console.log('迷宫解:', solution);

2. 网络爬虫

// 简单的网络爬虫（使用BFS）
class WebCrawler {
  constructor(baseUrl, maxDepth = 3) {
    this.baseUrl = baseUrl;
    this.maxDepth = maxDepth;
    this.visited = new Set();
    this.queue = [{ url: baseUrl, depth: 0 }];
    this.results = [];
  }
  
  // 模拟获取页面链接
  async getPageLinks(url) {
    // 实际应用中这里会发送HTTP请求
    // 这里只是模拟
    const mockLinks = {
      'https://example.com': ['https://example.com/page1', 'https://example.com/page2'],
      'https://example.com/page1': ['https://example.com/page3'],
      'https://example.com/page2': ['https://example.com/page4'],
      'https://example.com/page3': [],
      'https://example.com/page4': []
    };
    
    return mockLinks[url] || [];
  }
  
  // 爬取网页
  async crawl() {
    while (this.queue.length > 0) {
      const { url, depth } = this.queue.shift();
      
      if (this.visited.has(url) || depth > this.maxDepth) {
        continue;
      }
      
      this.visited.add(url);
      this.results.push({ url, depth });
      
      console.log(`爬取: ${url} (深度: ${depth})`);
      
      if (depth < this.maxDepth) {
        const links = await this.getPageLinks(url);
        for (const link of links) {
          if (!this.visited.has(link)) {
            this.queue.push({ url: link, depth: depth + 1 });
          }
        }
      }
    }
    
    return this.results;
  }
}

3. 游戏AI路径规划

// 游戏AI路径规划
class GamePathFinder {
  constructor(gameMap) {
    this.map = gameMap;
    this.rows = gameMap.length;
    this.cols = gameMap[0].length;
  }
  
  // A*算法（启发式搜索）
  findPath(start, end) {
    const openSet = [start];
    const cameFrom = new Map();
    const gScore = new Map();
    const fScore = new Map();
    
    gScore.set(start.join(','), 0);
    fScore.set(start.join(','), this.heuristic(start, end));
    
    while (openSet.length > 0) {
      // 找到fScore最小的节点
      let current = openSet.reduce((min, pos) => {
        const f1 = fScore.get(pos.join(',')) || Infinity;
        const f2 = fScore.get(min.join(',')) || Infinity;
        return f1 < f2 ? pos : min;
      });
      
      if (current[0] === end[0] && current[1] === end[1]) {
        return this.reconstructPath(cameFrom, current);
      }
      
      openSet.splice(openSet.indexOf(current), 1);
      
      const neighbors = this.getNeighbors(current[0], current[1]);
      for (const neighbor of neighbors) {
        const tentativeGScore = (gScore.get(current.join(',')) || Infinity) + 1;
        const neighborKey = neighbor.join(',');
        
        if (tentativeGScore < (gScore.get(neighborKey) || Infinity)) {
          cameFrom.set(neighborKey, current);
          gScore.set(neighborKey, tentativeGScore);
          fScore.set(neighborKey, tentativeGScore + this.heuristic(neighbor, end));
          
          if (!openSet.some(pos => pos[0] === neighbor[0] && pos[1] === neighbor[1])) {
            openSet.push(neighbor);
          }
        }
      }
    }
    
    return null; // 没有路径
  }
  
  // 启发式函数（曼哈顿距离）
  heuristic(pos1, pos2) {
    return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
  }
  
  // 重建路径
  reconstructPath(cameFrom, current) {
    const path = [current];
    let currentKey = current.join(',');
    
    while (cameFrom.has(currentKey)) {
      current = cameFrom.get(currentKey);
      path.unshift(current);
      currentKey = current.join(',');
    }
    
    return path;
  }
  
  // 获取邻居
  getNeighbors(row, col) {
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const neighbors = [];
    
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (this.isValid(newRow, newCol)) {
        neighbors.push([newRow, newCol]);
      }
    }
    
    return neighbors;
  }
  
  // 检查位置是否有效
  isValid(row, col) {
    return row >= 0 && row < this.rows && 
           col >= 0 && col < this.cols && 
           this.map[row][col] !== '#';
  }
}

性能优化技巧

1. 双向BFS

// 双向BFS（适用于已知起点和终点的情况）
function bidirectionalBFS(graph, start, end) {
  const visitedFromStart = new Set();
  const visitedFromEnd = new Set();
  const queueFromStart = [{ vertex: start, path: [start] }];
  const queueFromEnd = [{ vertex: end, path: [end] }];
  
  visitedFromStart.add(start);
  visitedFromEnd.add(end);
  
  while (queueFromStart.length > 0 && queueFromEnd.length > 0) {
    // 从起点扩展
    const { vertex: currentStart, path: pathStart } = queueFromStart.shift();
    
    if (visitedFromEnd.has(currentStart)) {
      // 找到交点，重建路径
      return reconstructBidirectionalPath(currentStart, pathStart, queueFromEnd);
    }
    
    const neighborsStart = graph.getNeighbors(currentStart);
    for (const neighbor of neighborsStart) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visitedFromStart.has(neighborVertex)) {
        visitedFromStart.add(neighborVertex);
        queueFromStart.push({
          vertex: neighborVertex,
          path: [...pathStart, neighborVertex]
        });
      }
    }
    
    // 从终点扩展
    const { vertex: currentEnd, path: pathEnd } = queueFromEnd.shift();
    
    if (visitedFromStart.has(currentEnd)) {
      return reconstructBidirectionalPath(currentEnd, pathStart, pathEnd);
    }
    
    const neighborsEnd = graph.getNeighbors(currentEnd);
    for (const neighbor of neighborsEnd) {
      const neighborVertex = neighbor.to || neighbor;
      if (!visitedFromEnd.has(neighborVertex)) {
        visitedFromEnd.add(neighborVertex);
        queueFromEnd.push({
          vertex: neighborVertex,
          path: [...pathEnd, neighborVertex]
        });
      }
    }
  }
  
  return null;
}

2. 迭代深化DFS

// 迭代深化DFS（结合DFS和BFS的优点）
function iterativeDeepeningDFS(graph, start, end, maxDepth = 10) {
  for (let depth = 0; depth <= maxDepth; depth++) {
    const visited = new Set();
    const result = dfsWithDepthLimit(graph, start, end, depth, visited);
    if (result) {
      return result;
    }
  }
  return null;
}

function dfsWithDepthLimit(graph, current, end, depth, visited) {
  if (current === end) {
    return [current];
  }
  
  if (depth === 0) {
    return null;
  }
  
  visited.add(current);
  
  const neighbors = graph.getNeighbors(current);
  for (const neighbor of neighbors) {
    const neighborVertex = neighbor.to || neighbor;
    if (!visited.has(neighborVertex)) {
      const result = dfsWithDepthLimit(graph, neighborVertex, end, depth - 1, visited);
      if (result) {
        return [current, ...result];
      }
    }
  }
  
  visited.delete(current);
  return null;
}

最佳实践

  1. 选择合适的算法：根据问题特点选择DFS或BFS
  2. 避免重复访问：使用visited集合记录已访问顶点
  3. 优化数据结构：选择合适的图表示方法
  4. 考虑内存使用：对于大图，考虑使用迭代版本
  5. 处理特殊情况：考虑环、孤立顶点等边界情况

图的遍历算法是图论的基础，掌握这些算法对于解决图相关问题至关重要。

最短路径算法

深入理解Dijkstra、Bellman-Ford、Floyd-Warshall等最短路径算法

LeetCode 算法题解

LeetCode 算法题的 JavaScript 解决方案集合