Advanced Graph Algorithm Visualizer
← Back to Home
Graph Controls
Graph Type:
Undirected
Directed
Number of Nodes:
Edges (format: 1-2-3 → node1-node2-weight):
Generate Graph
Algorithms
BFS
DFS
Connected Components
Dijkstra
Prim's MST
Output / Result:
Breadth-First Search (BFS) - Graph
Steps:
Start at the given source node and mark it as visited.
Initialize a queue and enqueue the source node.
While the queue is not empty:
Dequeue a node from the front of the queue.
Process the node (visit it).
Enqueue all unvisited neighbors of the node and mark them as visited.
Continue until the queue is empty and all reachable nodes are visited.
Time Complexity:
O(V + E)
Space Complexity:
O(V)
Depth-First Search (DFS) - Graph
Steps:
Start at the given source node and mark it as visited.
Process the current node (visit it).
Recursively visit all unvisited neighbors of the current node.
Backtrack when all neighbors of a node are visited and continue the recursion.
Continue until all reachable nodes are visited.
Time Complexity:
O(V + E)
Space Complexity:
O(V)
Dijkstra's Algorithm (Shortest Path)
Steps:
Initialize distances of all vertices as ∞ except the source vertex, which is 0.
Create a priority queue (min-heap) and insert the source vertex with distance 0.
While the priority queue is not empty:
Extract the vertex u with the minimum distance from the queue.
For each neighbor v of u, check if the distance to v can be minimized through u.
If yes, update the distance of v and insert it into the priority queue.
Repeat until all vertices are processed.
At the end, the shortest distances from the source to all vertices are determined.
Time Complexity:
O((V + E) log V)
Space Complexity:
O(V + E)
Prim's Algorithm (Minimum Spanning Tree)
Steps:
Initialize a set to track vertices included in the MST (start with any vertex).
Assign key values to all vertices as ∞, except the starting vertex which is 0.
While all vertices are not included in the MST:
Select the vertex u with the minimum key value not yet included in MST.
Include u in the MST set.
For each neighbor v of u, if v is not in MST and edge weight(u,v) < key[v], update key[v] = edge weight(u,v).
Repeat until all vertices are included in the MST.
At the end, the MST edges and their weights are determined.
Time Complexity:
O((V + E) log V)
Space Complexity:
O(V + E)
Graph Visualization