圖的表示法 — 鄰接矩陣、鄰接串列與邊串列完整解析 | 資料結構與演算法

// ─── 型別定義 ────────────────────────────────────────────
interface Edge {
  to: number;
  weight: number;
}

interface GraphOptions {
  directed: boolean;  // true = 有向圖，false = 無向圖
  weighted: boolean;  // true = 加權圖，false = 無加權（權重固定為 1）
}

// ─── 主類別：Graph（鄰接串列實作）───────────────────────
class Graph {
  private readonly adjList: Map<number, Edge[]>;
  private readonly options: GraphOptions;
  private _vertexCount: number;
  private _edgeCount: number;

  constructor(options: Partial<GraphOptions> = {}) {
    this.adjList = new Map();
    this.options = {
      directed: options.directed ?? true,
      weighted: options.weighted ?? false,
    };
    this._vertexCount = 0;
    this._edgeCount = 0;
  }

  // 新增頂點（若已存在則忽略）
  addVertex(v: number): void {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
      this._vertexCount++;
    }
  }

  // 新增邊：u → v（無向圖同時新增 v → u）
  addEdge(u: number, v: number, weight: number = 1): void {
    this.addVertex(u);
    this.addVertex(v);

    const w = this.options.weighted ? weight : 1;
    this.adjList.get(u)!.push({ to: v, weight: w });
    this._edgeCount++;

    if (!this.options.directed) {
      this.adjList.get(v)!.push({ to: u, weight: w });
      // 無向圖的 _edgeCount 不重複計算
    }
  }

  // 查詢邊是否存在：O(degree(u))
  hasEdge(u: number, v: number): boolean {
    const neighbors = this.adjList.get(u);
    if (!neighbors) return false;
    return neighbors.some(e => e.to === v);
  }

  // 取得頂點的所有鄰居
  getNeighbors(v: number): Edge[] {
    return this.adjList.get(v) ?? [];
  }

  // 取得所有頂點
  getVertices(): number[] {
    return [...this.adjList.keys()];
  }

  // 取得頂點的出度（有向圖）/ 度（無向圖）
  getDegree(v: number): number {
    return this.adjList.get(v)?.length ?? 0;
  }

  // 取得所有邊（三元組格式），無向圖只輸出一次
  getEdges(): Array<[number, number, number]> {
    const edges: Array<[number, number, number]> = [];
    for (const [u, neighbors] of this.adjList) {
      for (const { to, weight } of neighbors) {
        if (this.options.directed || u <= to) {
          edges.push([u, to, weight]);
        }
      }
    }
    return edges;
  }

  get vertexCount(): number { return this._vertexCount; }
  get edgeCount(): number   { return this._edgeCount; }
  get isDirected(): boolean { return this.options.directed; }

  // 列印鄰接串列（方便除錯）
  print(): void {
    for (const [v, neighbors] of this.adjList) {
      const edges = neighbors
        .map(e => this.options.weighted ? `(${e.to}, w=${e.weight})` : `${e.to}`)
        .join(', ');
      console.log(`${v}: [${edges}]`);
    }
  }
}

// 從 LeetCode 常見的 number[][] 格式建構
// edges[i] = [u, v] 或 [u, v, w]
function buildGraphFromMatrix(
  n: number,
  edges: number[][],
  directed: boolean = false
): Graph {
  const g = new Graph({ directed, weighted: edges[0]?.length === 3 });
  // 確保所有頂點（0 到 n-1）都存在，即使是孤立頂點
  for (let i = 0; i < n; i++) g.addVertex(i);
  for (const edge of edges) {
    const [u, v, w = 1] = edge;
    g.addEdge(u, v, w);
  }
  return g;
}

// 使用範例：建構有向加權圖
const g = buildGraphFromMatrix(4, [
  [0, 1, 4],
  [0, 2, 2],
  [1, 2, 3],
  [1, 3, 1],
  [2, 3, 5],
], true /* directed */);

g.print();
// 輸出：
// 0: [(1, w=4), (2, w=2)]
// 1: [(2, w=3), (3, w=1)]
// 2: [(3, w=5)]
// 3: []

console.log(g.hasEdge(0, 1)); // 輸出：true
console.log(g.hasEdge(1, 0)); // 輸出：false（有向圖）
console.log(g.getDegree(1));  // 輸出：2（出度 = 2）

// ─── 鄰接矩陣（稠密圖、Floyd-Warshall 使用）──────────────
const INF = Infinity;

class AdjacencyMatrix {
  private matrix: number[][];
  private readonly n: number;
  private readonly directed: boolean;

  constructor(n: number, directed: boolean = true) {
    this.n = n;
    this.directed = directed;
    // 初始化：無邊用 INF（加權圖）；對角線為 0（自身距離）
    this.matrix = Array.from(
      { length: n },
      () => new Array(n).fill(INF)
    );
    for (let i = 0; i < n; i++) this.matrix[i][i] = 0;
  }

  addEdge(u: number, v: number, weight: number = 1): void {
    this.matrix[u][v] = weight;
    if (!this.directed) this.matrix[v][u] = weight;
  }

  hasEdge(u: number, v: number): boolean {
    return this.matrix[u][v] !== INF && u !== v;
  }

  getWeight(u: number, v: number): number {
    return this.matrix[u][v];
  }

  // 遍歷頂點 u 的所有鄰居：O(V)（需掃描整行）
  getNeighbors(u: number): Array<{ to: number; weight: number }> {
    const result: Array<{ to: number; weight: number }> = [];
    for (let v = 0; v < this.n; v++) {
      if (v !== u && this.matrix[u][v] !== INF) {
        result.push({ to: v, weight: this.matrix[u][v] });
      }
    }
    return result;
  }

  // 取得原始矩陣（Floyd-Warshall 需要直接操作）
  getMatrix(): number[][] {
    return this.matrix.map(row => [...row]); // 深拷貝
  }

  print(): void {
    const header = '     ' + [...Array(this.n).keys()]
      .map(i => String(i).padStart(5)).join('');
    console.log(header);
    for (let i = 0; i < this.n; i++) {
      const row = this.matrix[i]
        .map(v => (v === INF ? '  INF' : String(v).padStart(5)))
        .join('');
      console.log(`${String(i).padStart(3)}: ${row}`);
    }
  }
}

// 使用範例
const am = new AdjacencyMatrix(4, true);
am.addEdge(0, 1, 4);
am.addEdge(0, 2, 2);
am.addEdge(1, 2, 3);
am.addEdge(1, 3, 1);
am.addEdge(2, 3, 5);
am.print();
// 輸出：
//        0    1    2    3
//   0:   0    4    2  INF
//   1: INF    0    3    1
//   2: INF  INF    0    5
//   3: INF  INF  INF    0

// ─── 邊串列（Kruskal 等需要排序邊的演算法）──────────────
interface WeightedEdge {
  u: number;
  v: number;
  weight: number;
}

class EdgeList {
  private edges: WeightedEdge[] = [];
  private readonly directed: boolean;

  constructor(directed: boolean = false) {
    this.directed = directed;
  }

  addEdge(u: number, v: number, weight: number = 1): void {
    this.edges.push({ u, v, weight });
  }

  // 按權重升序排列（Kruskal MST 的前置步驟）
  sortByWeight(): WeightedEdge[] {
    return [...this.edges].sort((a, b) => a.weight - b.weight);
  }

  getEdges(): WeightedEdge[] {
    return [...this.edges];
  }

  get edgeCount(): number {
    return this.edges.length;
  }
}

// 使用範例
const el = new EdgeList(false /* 無向 */);
el.addEdge(0, 1, 4);
el.addEdge(0, 2, 2);
el.addEdge(1, 2, 3);
el.addEdge(1, 3, 1);
el.addEdge(2, 3, 5);

const sorted = el.sortByWeight();
console.log(sorted.map(e => `(${e.u},${e.v},${e.weight})`));
// 輸出：["(1,3,1)", "(0,2,2)", "(1,2,3)", "(0,1,4)", "(2,3,5)"]
// 這正是 Kruskal 演算法的處理順序

// ─── 字串頂點版本（頂點名稱為字串的場景）──────────────
class StringGraph {
  private adjList: Map<string, Map<string, number>>;
  private readonly directed: boolean;

  constructor(directed: boolean = true) {
    this.adjList = new Map();
    this.directed = directed;
  }

  addVertex(v: string): void {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, new Map());
    }
  }

  addEdge(u: string, v: string, weight: number = 1): void {
    this.addVertex(u);
    this.addVertex(v);
    this.adjList.get(u)!.set(v, weight);
    if (!this.directed) {
      this.adjList.get(v)!.set(u, weight);
    }
  }

  // O(1) 查邊（Map 的 has 是 O(1) 攤銷）
  hasEdge(u: string, v: string): boolean {
    return this.adjList.get(u)?.has(v) ?? false;
  }

  getNeighbors(v: string): string[] {
    return [...(this.adjList.get(v)?.keys() ?? [])];
  }

  getVertices(): string[] {
    return [...this.adjList.keys()];
  }
}

// 使用範例：Web 爬蟲的有向圖
const webGraph = new StringGraph(true /* 有向 */);
webGraph.addEdge('home', 'products');
webGraph.addEdge('home', 'about');
webGraph.addEdge('products', 'cart');
webGraph.addEdge('products', 'home'); // 「返回首頁」連結

console.log(webGraph.hasEdge('home', 'products')); // 輸出：true
console.log(webGraph.hasEdge('products', 'home')); // 輸出：true（有「返回」連結）
console.log(webGraph.getNeighbors('home'));         // 輸出：["products", "about"]

// 使用範例：社交網路的無向圖
const social = new StringGraph(false /* 無向 */);
social.addEdge('Alice', 'Bob');
social.addEdge('Alice', 'Carol');
social.addEdge('Bob', 'Dave');
social.addEdge('Carol', 'Dave');

console.log(social.getNeighbors('Alice')); // 輸出：["Bob", "Carol"]
// BFS 即可求兩人之間的最短朋友鏈（六度分隔理論）

#include <climits>
#include <iostream>
#include <utility>
#include <vector>
#include <unordered_map>
#include <algorithm>

// ─── 鄰接串列：vector<vector<pair<int,int>>> ─────────────
// LeetCode 最常見的圖表示形式
// adjList[u] = { (v1, w1), (v2, w2), ... }
using AdjList = std::vector<std::vector<std::pair<int, int>>>;

class GraphVec {
  AdjList adj;
  int n;
  bool directed;

 public:
  explicit GraphVec(int vertices, bool directed = true)
      : adj(vertices), n(vertices), directed(directed) {}

  void addEdge(int u, int v, int weight = 1) {
    adj[u].emplace_back(v, weight);
    if (!directed) adj[v].emplace_back(u, weight);
  }

  bool hasEdge(int u, int v) const {
    for (const auto& [to, w] : adj[u]) {
      if (to == v) return true;
    }
    return false;
  }

  const std::vector<std::pair<int, int>>& getNeighbors(int u) const {
    return adj[u];
  }

  void print() const {
    for (int u = 0; u < n; ++u) {
      std::cout << u << ": ";
      for (const auto& [v, w] : adj[u]) {
        std::cout << "(" << v << "," << w << ") ";
      }
      std::cout << "\n";
    }
  }
};

// ─── 鄰接矩陣版本（稠密圖、Floyd-Warshall）──────────────
constexpr int INF_W = INT_MAX / 2; // 避免加法溢位

class AdjacencyMatrixGraph {
  std::vector<std::vector<int>> mat;
  int n;
  bool directed;

 public:
  explicit AdjacencyMatrixGraph(int vertices, bool directed = true)
      : mat(vertices, std::vector<int>(vertices, INF_W)),
        n(vertices), directed(directed) {
    for (int i = 0; i < n; ++i) mat[i][i] = 0;
  }

  void addEdge(int u, int v, int weight = 1) {
    mat[u][v] = weight;
    if (!directed) mat[v][u] = weight;
  }

  bool hasEdge(int u, int v) const {
    return mat[u][v] != INF_W && u != v;
  }

  // Floyd-Warshall 全對最短路徑：O(V³)
  std::vector<std::vector<int>> floydWarshall() const {
    auto dist = mat;
    for (int k = 0; k < n; ++k) {       // 中繼點
      for (int i = 0; i < n; ++i) {     // 起點
        for (int j = 0; j < n; ++j) {   // 終點
          if (dist[i][k] != INF_W && dist[k][j] != INF_W) {
            dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
          }
        }
      }
    }
    return dist;
  }
};

// ─── unordered_map 版本（動態頂點、字串頂點）───────────
template <typename V = int>
class GraphMap {
  using Neighbors = std::unordered_map<V, int>;
  std::unordered_map<V, Neighbors> adj;
  bool directed;

 public:
  explicit GraphMap(bool directed = true) : directed(directed) {}

  void addEdge(const V& u, const V& v, int weight = 1) {
    adj[u][v] = weight;
    if (!directed) adj[v][u] = weight;
  }

  // O(1) 平均查邊（unordered_map 雜湊查詢）
  bool hasEdge(const V& u, const V& v) const {
    auto it = adj.find(u);
    if (it == adj.end()) return false;
    return it->second.count(v) > 0;
  }

  std::vector<V> getNeighbors(const V& u) const {
    std::vector<V> result;
    auto it = adj.find(u);
    if (it != adj.end()) {
      for (const auto& [v, w] : it->second) {
        result.push_back(v);
      }
    }
    return result;
  }
};

// ─── 邊串列版本（Kruskal MST）────────────────────────────
struct WeightedEdge {
  int u, v, weight;
  bool operator<(const WeightedEdge& other) const {
    return weight < other.weight;
  }
};

class EdgeListGraph {
  std::vector<WeightedEdge> edges;
  int n;

 public:
  explicit EdgeListGraph(int vertices) : n(vertices) {}

  void addEdge(int u, int v, int weight = 1) {
    edges.push_back({u, v, weight});
  }

  // 按權重升序（Kruskal 演算法的前置步驟）
  std::vector<WeightedEdge> getSortedEdges() const {
    auto sorted = edges;
    std::sort(sorted.begin(), sorted.end());
    return sorted;
  }

  int vertexCount() const { return n; }
  int edgeCount()   const { return static_cast<int>(edges.size()); }
};

// ─── 使用範例 ────────────────────────────────────────────
int main() {
  // 有向加權圖（vector 版）
  GraphVec g(4, true);
  g.addEdge(0, 1, 4);
  g.addEdge(0, 2, 2);
  g.addEdge(1, 2, 3);
  g.addEdge(1, 3, 1);
  g.addEdge(2, 3, 5);
  g.print();
  // 0: (1,4) (2,2)
  // 1: (2,3) (3,1)
  // 2: (3,5)
  // 3:

  // Floyd-Warshall 最短路
  AdjacencyMatrixGraph mg(4, true);
  mg.addEdge(0, 1, 4); mg.addEdge(0, 2, 2);
  mg.addEdge(1, 2, 3); mg.addEdge(1, 3, 1); mg.addEdge(2, 3, 5);
  auto dist = mg.floydWarshall();
  std::cout << dist[0][3] << "\n"; // 輸出：5（0→1→3 = 4+1）

  // 字串頂點（unordered_map 版）
  GraphMap<std::string> sg(true);
  sg.addEdge("A", "B", 10);
  sg.addEdge("A", "C", 3);
  std::cout << sg.hasEdge("A", "B") << "\n"; // 輸出：1（true）

  return 0;
}

// BFS 在棋盤格上（8 方向移動），不需要預先建圖
function bfsOnGrid(
  grid: number[][],
  start: [number, number],
  end: [number, number]
): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]];
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const queue: [[number, number], number][] = [[start, 0]];
  visited[start[0]][start[1]] = true;

  while (queue.length > 0) {
    const [[r, c], dist] = queue.shift()!;
    if (r === end[0] && c === end[1]) return dist;

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && !visited[nr][nc] && grid[nr][nc] === 0) {
        visited[nr][nc] = true;
        queue.push([[nr, nc], dist + 1]);
      }
    }
  }
  return -1;
}
// 頂點 = 格子座標，邊 = 相鄰且不是障礙的格子
// 不需要 Graph 物件，直接在 BFS 裡計算「鄰居」

// 陷阱 1：孤立頂點（Isolated Vertex）遺漏
// 從邊串列建圖時，沒有邊的頂點容易被遺忘
// ❌ 錯誤：只有 [0,1],[1,2] 這兩條邊的圖，頂點 3 不存在
function badBuildGraph(n: number, edges: number[][]): Graph {
  const g = new Graph({ directed: false });
  for (const [u, v] of edges) g.addEdge(u, v);
  return g; // 若頂點 3 沒有邊，adjList 中不會有 key=3
}

// ✅ 正確：先初始化所有頂點
function goodBuildGraph(n: number, edges: number[][]): Graph {
  const g = new Graph({ directed: false });
  for (let i = 0; i < n; i++) g.addVertex(i); // 確保所有頂點存在
  for (const [u, v] of edges) g.addEdge(u, v);
  return g;
}

// 陷阱 2：無向圖重複計算邊數
// adjList[u] 和 adjList[v] 各存一份，若直接加總得到的是實際邊數的 2 倍
// ✅ 正確計法：只計 u < v 的邊，或用獨立的 _edgeCount 追蹤

// 陷阱 3：鄰接矩陣初始化為 0 導致加權圖錯誤
// ❌ 錯誤：matrix 初始化為 0，但 0 是有效權重！
const badMatrix = Array.from({ length: 4 }, () => new Array(4).fill(0));
// 查詢 hasEdge(0,1) 時無法分辨「無邊」與「邊的權重=0」

// ✅ 正確：初始化為 Infinity（TypeScript）或 INT_MAX/2（C++）
const goodMatrix = Array.from({ length: 4 }, () => new Array(4).fill(Infinity));

// 陷阱 4：有向圖混淆入度/出度
// adjList[u].length 是頂點 u 的「出度」，不是「入度」
// 計算入度需要額外遍歷所有邊，或建圖時維護 inDegree[] 陣列
function computeInDegrees(n: number, edges: number[][]): number[] {
  const inDegree = new Array(n).fill(0);
  for (const [, v] of edges) {
    inDegree[v]++;  // 每條邊 u→v 讓 v 的入度加 1
  }
  return inDegree;
}

// 題目：找出「鎮長」：被其他所有人信任（入度 n-1），但不信任任何人（出度 0）
function findJudge(n: number, trust: number[][]): number {
  const inDegree  = new Array(n + 1).fill(0); // 被信任次數
  const outDegree = new Array(n + 1).fill(0); // 信任他人次數

  for (const [a, b] of trust) {
    outDegree[a]++; // a 信任 b → a 的出度加 1
    inDegree[b]++;  // a 信任 b → b 的入度加 1
  }

  for (let i = 1; i <= n; i++) {
    // 鎮長：出度為 0（不信任任何人）且入度為 n-1（被所有人信任）
    if (outDegree[i] === 0 && inDegree[i] === n - 1) return i;
  }

  return -1;
}

console.log(findJudge(2, [[1, 2]]));                     // 輸出：2
console.log(findJudge(3, [[1,3],[2,3]]));                // 輸出：3
console.log(findJudge(3, [[1,3],[2,3],[3,1]]));          // 輸出：-1

// 題目：無向圖中判斷 source 與 destination 是否連通（BFS 版本）
function validPath(
  n: number,
  edges: number[][],
  source: number,
  destination: number
): boolean {
  if (source === destination) return true;

  // 建構鄰接串列
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u); // 無向圖
  }

  // BFS 從 source 出發，看能否到達 destination
  const visited = new Array(n).fill(false);
  const queue = [source];
  visited[source] = true;

  while (queue.length > 0) {
    const curr = queue.shift()!;
    for (const next of adj[curr]) {
      if (next === destination) return true;
      if (!visited[next]) {
        visited[next] = true;
        queue.push(next);
      }
    }
  }

  return false;
}

console.log(validPath(3, [[0,1],[1,2],[2,0]], 0, 2)); // 輸出：true
console.log(validPath(6, [[0,1],[0,2],[3,5],[5,4],[4,3]], 0, 5)); // 輸出：false