Graph Visualizer

Graph Traversal

Trace BFS, DFS, and Dijkstra across a weighted directed graph with frontier, visited, settled, and distance state.

AlgorithmO(V + E)

Step Note

Compute indegrees and enqueue nodes with indegree 0.

function topologicalSort(graph: Graph) {
  const indegree = countIncomingEdges(graph)
  const queue = nodesWithZeroIndegree(indegree)
  const order = []
  while (queue.length > 0) {
    const node = queue.shift()
    order.push(node)
    for (const neighbor of graph.neighbors(node)) {
      indegree[neighbor]--
      if (indegree[neighbor] === 0) queue.push(neighbor)
    }
  }
  return order
}