class Graph {
  private adjacencyList: Map<string, Map<string, number>> = new Map();

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

  addEdge(vertex1: string, vertex2: string, weight: number = 1): void {
    this.addVertex(vertex1);
    this.addVertex(vertex2);

    this.adjacencyList.get(vertex1)!.set(vertex2, weight);
    this.adjacencyList.get(vertex2)!.set(vertex1, weight);
  }

  getVertices(): string[] {
    return Array.from(this.adjacencyList.keys());
  }

  getNeighbors(vertex: string): Map<string, number> {
    return this.adjacencyList.get(vertex) || new Map();
  }

  getWeight(vertex1: string, vertex2: string): number {
    return this.adjacencyList.get(vertex1)?.get(vertex2) || Infinity;
  }
}

function dfs(graph: Graph, start: string, visited: Set<string> = new Set()): string[] {
  const result: string[] = [];
  const stack: string[] = [start];

  while (stack.length > 0) {
    const vertex = stack.pop()!;

    if (!visited.has(vertex)) {
      visited.add(vertex);
      result.push(vertex);

      const neighbors = graph.getNeighbors(vertex);
      for (const neighbor of neighbors.keys()) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }

  return result;
}

function dfsRecursive(graph: Graph, vertex: string, visited: Set<string> = new Set(), result: string[] = []): string[] {
  visited.add(vertex);
  result.push(vertex);

  const neighbors = graph.getNeighbors(vertex);
  for (const neighbor of neighbors.keys()) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited, result);
    }
  }

  return result;
}

function bfs(graph: Graph, start: string): string[] {
  const result: string[] = [];
  const visited = new Set<string>();
  const queue: string[] = [start];

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift()!;
    result.push(vertex);

    const neighbors = graph.getNeighbors(vertex);
    for (const neighbor of neighbors.keys()) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

function dijkstra(graph: Graph, start: string): Map<string, { distance: number; path: string[] }> {
  const distances = new Map<string, number>();
  const previous = new Map<string, string>();
  const unvisited = new Set<string>();

  // 初始化
  for (const vertex of graph.getVertices()) {
    distances.set(vertex, vertex === start ? 0 : Infinity);
    unvisited.add(vertex);
  }

  while (unvisited.size > 0) {
    // 找到距离最小的顶点
    let minDistance = Infinity;
    let minVertex: string | null = null;

    for (const vertex of unvisited) {
      const distance = distances.get(vertex)!;
      if (distance < minDistance) {
        minDistance = distance;
        minVertex = vertex;
      }
    }

    if (minVertex === null || minDistance === Infinity) break;

    unvisited.delete(minVertex);

    // 更新邻居距离
    const neighbors = graph.getNeighbors(minVertex);
    for (const [neighbor, weight] of neighbors) {
      if (unvisited.has(neighbor)) {
        const alt = distances.get(minVertex)! + weight;
        if (alt < distances.get(neighbor)!) {
          distances.set(neighbor, alt);
          previous.set(neighbor, minVertex);
        }
      }
    }
  }

  // 构建结果
  const result = new Map<string, { distance: number; path: string[] }>();
  for (const vertex of graph.getVertices()) {
    const path = reconstructPath(previous, vertex);
    result.set(vertex, {
      distance: distances.get(vertex)!,
      path,
    });
  }

  return result;
}

function reconstructPath(previous: Map<string, string>, target: string): string[] {
  const path: string[] = [];
  let current: string | undefined = target;

  while (current) {
    path.unshift(current);
    current = previous.get(current);
  }

  return path;
}

function primMST(graph: Graph): { mst: Array<{ from: string; to: string; weight: number }>; totalWeight: number } {
  const vertices = graph.getVertices();
  if (vertices.length === 0) return { mst: [], totalWeight: 0 };

  const mst: Array<{ from: string; to: string; weight: number }> = [];
  const visited = new Set<string>();
  const minHeap: Array<{ vertex: string; weight: number; from: string }> = [];

  // 从第一个顶点开始
  visited.add(vertices[0]);

  // 添加初始边到堆
  const neighbors = graph.getNeighbors(vertices[0]);
  for (const [neighbor, weight] of neighbors) {
    minHeap.push({ vertex: neighbor, weight, from: vertices[0] });
  }

  while (visited.size < vertices.length && minHeap.length > 0) {
    // 找到权重最小的边
    minHeap.sort((a, b) => a.weight - b.weight);
    const { vertex, weight, from } = minHeap.shift()!;

    if (visited.has(vertex)) continue;

    visited.add(vertex);
    mst.push({ from, to: vertex, weight });

    // 添加新顶点的边到堆
    const newNeighbors = graph.getNeighbors(vertex);
    for (const [neighbor, neighborWeight] of newNeighbors) {
      if (!visited.has(neighbor)) {
        minHeap.push({ vertex: neighbor, weight: neighborWeight, from: vertex });
      }
    }
  }

  const totalWeight = mst.reduce((sum, edge) => sum + edge.weight, 0);
  return { mst, totalWeight };
}

function kruskalMST(graph: Graph): { mst: Array<{ from: string; to: string; weight: number }>; totalWeight: number } {
  const edges: Array<{ from: string; to: string; weight: number }> = [];
  const vertices = graph.getVertices();

  // 收集所有边
  for (const vertex of vertices) {
    const neighbors = graph.getNeighbors(vertex);
    for (const [neighbor, weight] of neighbors) {
      // 避免重复添加边
      if (vertex < neighbor) {
        edges.push({ from: vertex, to: neighbor, weight });
      }
    }
  }

  // 按权重排序
  edges.sort((a, b) => a.weight - b.weight);

  const unionFind = new UnionFind(vertices);
  const mst: Array<{ from: string; to: string; weight: number }> = [];

  for (const edge of edges) {
    if (!unionFind.connected(edge.from, edge.to)) {
      unionFind.union(edge.from, edge.to);
      mst.push(edge);
    }
  }

  const totalWeight = mst.reduce((sum, edge) => sum + edge.weight, 0);
  return { mst, totalWeight };
}

class UnionFind {
  private parent: Map<string, string> = new Map();
  private rank: Map<string, number> = new Map();

  constructor(vertices: string[]) {
    for (const vertex of vertices) {
      this.parent.set(vertex, vertex);
      this.rank.set(vertex, 0);
    }
  }

  find(vertex: string): string {
    if (this.parent.get(vertex) !== vertex) {
      this.parent.set(vertex, this.find(this.parent.get(vertex)!));
    }
    return this.parent.get(vertex)!;
  }

  union(vertex1: string, vertex2: string): void {
    const root1 = this.find(vertex1);
    const root2 = this.find(vertex2);

    if (root1 !== root2) {
      const rank1 = this.rank.get(root1)!;
      const rank2 = this.rank.get(root2)!;

      if (rank1 > rank2) {
        this.parent.set(root2, root1);
      } else if (rank1 < rank2) {
        this.parent.set(root1, root2);
      } else {
        this.parent.set(root2, root1);
        this.rank.set(root1, rank1 + 1);
      }
    }
  }

  connected(vertex1: string, vertex2: string): boolean {
    return this.find(vertex1) === this.find(vertex2);
  }
}

function graphColoring(graph: Graph): Map<string, number> {
  const vertices = graph.getVertices();
  const colors = new Map<string, number>();
  const availableColors = new Set<number>();

  // 为每个顶点分配颜色
  for (const vertex of vertices) {
    // 找到邻居使用的颜色
    const neighborColors = new Set<number>();
    const neighbors = graph.getNeighbors(vertex);

    for (const neighbor of neighbors.keys()) {
      const neighborColor = colors.get(neighbor);
      if (neighborColor !== undefined) {
        neighborColors.add(neighborColor);
      }
    }

    // 找到第一个可用的颜色
    let color = 0;
    while (neighborColors.has(color)) {
      color += 1;
    }

    colors.set(vertex, color);
  }

  return colors;
}

function topologicalSort(graph: Graph): string[] {
  const result: string[] = [];
  const visited = new Set<string>();
  const visiting = new Set<string>();

  const dfs = (vertex: string): boolean => {
    if (visiting.has(vertex)) return false; // 发现环
    if (visited.has(vertex)) return true;

    visiting.add(vertex);

    const neighbors = graph.getNeighbors(vertex);
    for (const neighbor of neighbors.keys()) {
      if (!dfs(neighbor)) return false;
    }

    visiting.delete(vertex);
    visited.add(vertex);
    result.unshift(vertex); // 添加到结果开头

    return true;
  };

  for (const vertex of graph.getVertices()) {
    if (!visited.has(vertex)) {
      if (!dfs(vertex)) {
        throw new Error('Graph contains a cycle');
      }
    }
  }

  return result;
}