8. 图（Graph） - Hok Keung

问题：需要表达多对多的关系，如社交网络、地图导航、依赖关系。

核心：由顶点（Vertex）和边（Edge）组成。可以用邻接表（每个顶点存邻居列表）或邻接矩阵（二维数组）表示。

特点

顶点 + 边，有向/无向，有权/无权
邻接表：空间 O(V+E)，适合稀疏图
邻接矩阵：空间 O(V²)，适合密集图，O(1) 判断两点是否相连

优点

能表达复杂的多对多关系
灵活：有向/无向、加权/无权、有环/无环
BFS/DFS 遍历算法成熟

缺点

实现复杂，尤其涉及权重和最短路径
稀疏图用邻接矩阵浪费空间
可能有环，遍历时需标记已访问
最短路径等算法时间复杂度较高

// 邻接表实现
class Graph {
  #adj = new Map();

  addVertex(v) {
    if (!this.#adj.has(v)) this.#adj.set(v, []);
  }

  addEdge(v, w) {
    this.addVertex(v);
    this.addVertex(w);
    this.#adj.get(v).push(w);
    this.#adj.get(w).push(v); // 无向图
  }

  // BFS 广度优先搜索
  bfs(start) {
    const visited = new Set([start]);
    const queue = [start];
    const order = [];

    while (queue.length) {
      const v = queue.shift();
      order.push(v);
      for (const neighbor of this.#adj.get(v) ?? []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }

  // DFS 深度优先搜索
  dfs(start, visited = new Set(), order = []) {
    visited.add(start);
    order.push(start);
    for (const neighbor of this.#adj.get(start) ?? []) {
      if (!visited.has(neighbor)) {
        this.dfs(neighbor, visited, order);
      }
    }
    return order;
  }
}

const g = new Graph();
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');

console.log(g.bfs('A')); // ['A', 'B', 'C', 'D']
console.log(g.dfs('A')); // ['A', 'B', 'D', 'C']

package graph

// 邻接表实现
type Graph struct {
    adj map[string][]string
}

func NewGraph() *Graph {
    return &Graph{adj: make(map[string][]string)}
}

func (g *Graph) AddEdge(v, w string) {
    g.adj[v] = append(g.adj[v], w)
    g.adj[w] = append(g.adj[w], v) // 无向图
}

// BFS
func (g *Graph) BFS(start string) []string {
    visited := map[string]bool{start: true}
    queue := []string{start}
    var order []string

    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]
        order = append(order, v)
        for _, neighbor := range g.adj[v] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    return order
}

// DFS
func (g *Graph) DFS(start string) []string {
    visited := map[string]bool{}
    var order []string
    var dfs func(v string)
    dfs = func(v string) {
        visited[v] = true
        order = append(order, v)
        for _, neighbor := range g.adj[v] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
    dfs(start)
    return order
}

社交网络（好友关系）、地图导航（最短路径 Dijkstra）、Git 提交图、网页爬虫（URL 图）都是图的应用。