All Labs

Graph Theory & Networks Lab

Build graphs by clicking to add nodes and edges. Run breadth-first and depth-first traversals, find shortest paths with Dijkstra's algorithm, and compute minimum spanning trees with Kruskal's algorithm. Detect Euler paths and analyze graph properties.

Guided Experiment: BFS vs DFS

How does the traversal order differ between BFS and DFS on the same graph? Which explores nearby nodes first?

Write your hypothesis in the Lab Report panel, then click Next.

ABC
Click canvas to add node. Click node, then another node to add edge. Right-click node to delete. Drag nodes to reposition.

Controls

Click the canvas to add nodes. Click a node, then another node to add an edge.

Graph Properties

Nodes
3
Edges
3
Degree Sequence
2, 2, 2
Sum = 6
Connected
Yes
1 component
Eulerian
Euler Circuit
Density
1.000
Dense
Is Tree
No
Bipartite
No (contains odd cycle)

Data Table

(0 rows)
#GraphNodesEdgesConnectedEulerianDensity
0 / 500
0 / 500
0 / 500

Reference Guide

BFS vs DFS

Breadth-first search (BFS) explores all neighbors before going deeper, using a queue. Depth-first search (DFS) goes as deep as possible first, using a stack.

BFS: level-by-levelDFS: branch-by-branch\text{BFS: level-by-level} \quad \text{DFS: branch-by-branch}

BFS finds shortest paths in unweighted graphs. DFS is useful for detecting cycles and topological sorting.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source to all other nodes in a weighted graph with non-negative edges.

d[v]=min⁡(d[v],  d[u]+w(u,v))d[v] = \min(d[v],\; d[u] + w(u,v))

It greedily selects the unvisited node with smallest tentative distance, then relaxes all its neighbors.

Minimum Spanning Tree

A minimum spanning tree (MST) connects all nodes with the minimum total edge weight. Kruskal's algorithm sorts edges by weight and adds them if they do not create a cycle.

MST has ∣V∣−1 edges\text{MST has } |V| - 1 \text{ edges}

MSTs are used in network design, clustering, and approximation algorithms.

Euler Paths & Circuits

An Euler circuit traverses every edge exactly once and returns to the start. An Euler path traverses every edge exactly once but may end at a different vertex.

Circuit: all degrees evenPath: exactly 2 odd degrees\text{Circuit: all degrees even} \quad \text{Path: exactly 2 odd degrees}

A connected graph has an Euler circuit if and only if every vertex has even degree.