A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect these nodes. Graphs are used to represent relationships between different objects and are widely used in computer science for solving various problems.
Types of graphs:
Undirected Graph: Edges have no direction
Directed Graph: Edges have direction
Weighted Graph: Edges have weights/costs
Unweighted Graph: Edges have no weights
Breadth-First Search (BFS)
BFS is a graph traversal algorithm that explores all the vertices of a graph at the present depth level before moving on to the vertices at the next depth level. It uses a queue data structure to keep track of vertices to be explored.
Applications:
Finding the shortest path in an unweighted graph
Web crawlers
Social networking websites
GPS Navigation systems
function bfs(graph, startNode) {
const queue = [startNode];
const visited = new Set([startNode]);
while (queue.length > 0) {
const currentNode = queue.shift();
console.log(currentNode); // Process node
for (const neighbor of graph[currentNode]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
Depth-First Search (DFS)
DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure (or recursion) to keep track of vertices to be explored.
Applications:
Finding connected components
Topological sorting
Detecting cycles in a graph
Solving mazes
function dfs(graph, startNode, visited = new Set()) {
visited.add(startNode);
console.log(startNode); // Process node
for (const neighbor of graph[startNode]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
Dijkstra's Algorithm (Shortest Path)
Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative weights. It uses a priority queue to always process the node with the smallest current distance.
Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph. It adds edges in order of increasing weight, skipping edges that would create a cycle.
Applications:
Network design (LAN, electrical, hydraulic, etc.)
Cluster analysis
Approximation algorithms for NP-hard problems
function kruskal(graph) {
const edges = [];
const MST = [];
const disjointSet = new DisjointSet(/* all nodes */);
// Get all edges and sort by weight
for (const node in graph) {
for (const [neighbor, weight] of graph[node]) {
if (node < neighbor) { // To avoid duplicate edges
edges.push([node, neighbor, weight]);
}
}
}
edges.sort((a, b) => a[2] - b[2]);
// Build MST
for (const [u, v, weight] of edges) {
if (!disjointSet.sameSet(u, v)) {
disjointSet.union(u, v);
MST.push([u, v, weight]);
}
}
return MST;
}
Prim's Algorithm (Minimum Spanning Tree)
Prim's algorithm finds a minimum spanning tree for a connected weighted graph. It starts from a single node and grows the tree by adding the smallest edge connecting a tree node to a non-tree node.
Applications:
Network design
Approximating the traveling salesman problem
Cluster analysis
function prim(graph, startNode) {
const visited = new Set([startNode]);
const MST = [];
const edges = new PriorityQueue();
// Add all edges from start node
for (const [neighbor, weight] of graph[startNode]) {
edges.enqueue([startNode, neighbor], weight);
}
while (!edges.isEmpty() && visited.size < Object.keys(graph).length) {
const [edge, weight] = edges.dequeue();
const [u, v] = edge;
if (visited.has(v)) continue;
// Add vertex to MST
visited.add(v);
MST.push([u, v, weight]);
// Add new edges to priority queue
for (const [neighbor, weight] of graph[v]) {
if (!visited.has(neighbor)) {
edges.enqueue([v, neighbor], weight);
}
}
}
return MST;
}
Legend
Normal Node
Start Node
Current Node
Visited Node
Normal Edge
Highlighted Edge
Algorithm Statistics
Select and run an algorithm to see statistics
Algorithm logs will appear here...
Select an Algorithm
Please select an algorithm from the dropdown menu and click "Run Algorithm" to see it in action.