تنفيذ خوارزمية Kosaraju باستخدام JavaScript وTypeScript

DFS على الرسم الأصلي
        ↓
ترتيب انتهاء العقد
        ↓
عكس جميع الحواف
        ↓
DFS على الرسم المعكوس
        ↓
SCCs

const graph = new Map([
  [0, [1]],
  [1, [2, 3]],
  [2, [0]],
  [3, [4]],
  [4, [3]]
]);

0 → 1
1 → 2, 3
2 → 0
3 → 4
4 → 3

function fillOrder(node, graph, visited, stack) {
  visited.add(node);

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      fillOrder(neighbor, graph, visited, stack);
    }
  }

  stack.push(node);
}

A → B

B → A

function transposeGraph(graph) {
  const transpose = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor).push(node);
    }
  }

  return transpose;
}

visited.clear();

function kosaraju(graph) {
  const visited = new Set();
  const stack = [];

  function fillOrder(node) {
    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        fillOrder(neighbor);
      }
    }

    stack.push(node);
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      fillOrder(node);
    }
  }

  const transpose = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor).push(node);
    }
  }

  visited.clear();

  const components = [];

  function collect(node, component) {
    visited.add(node);
    component.push(node);

    for (const neighbor of transpose.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        collect(neighbor, component);
      }
    }
  }

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

    if (!visited.has(node)) {
      const component = [];
      collect(node, component);
      components.push(component);
    }
  }

  return components;
}

type Graph<T> = Map<T, T[]>;

function kosaraju<T>(graph: Graph<T>): T[][] {
  const visited = new Set<T>();
  const stack: T[] = [];

  const fillOrder = (node: T): void => {
    visited.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        fillOrder(neighbor);
      }
    }

    stack.push(node);
  };

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      fillOrder(node);
    }
  }

  const transpose: Graph<T> = new Map();

  for (const node of graph.keys()) {
    transpose.set(node, []);
  }

  for (const [node, neighbors] of graph.entries()) {
    for (const neighbor of neighbors) {
      if (!transpose.has(neighbor)) {
        transpose.set(neighbor, []);
      }

      transpose.get(neighbor)!.push(node);
    }
  }

  visited.clear();

  const components: T[][] = [];

  const collect = (node: T, component: T[]): void => {
    visited.add(node);
    component.push(node);

    for (const neighbor of transpose.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        collect(neighbor, component);
      }
    }
  };

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

    if (!visited.has(node)) {
      const component: T[] = [];
      collect(node, component);
      components.push(component);
    }
  }

  return components;
}

const services: Graph<string> = new Map([
  ["user", ["payment"]],
  ["payment", ["notification"]],
  ["notification", ["user"]],
  ["report", ["analytics"]],
  ["analytics", ["report"]],
  ["admin", ["user"]]
]);

{user, payment, notification}
{report, analytics}
{admin}

O(V + E)

O(V + E)

O(V + E)

O(V + E)

O(V + E)

RangeError: Maximum call stack size exceeded

DFS الأول
↓
Finish Order
↓
Transpose
↓
DFS الثاني
↓
SCCs