What is an Unweighted Graph?
An unweighted graph is a graph where all edges are treated equally — there's no cost, distance, or weight associated with traversing from one vertex to another. The focus is on structure, connectivity rather than optimization.
Unlike weighted graphs (used in shortest path algorithms like Dijkstra), unweighted graphs help us answer questions like:
- › Is there a path between two vertices?
- › What's the correct order when tasks have dependencies?
- › How many connected components exist?
Graph II builds on the traversal basics from Graph I (BFS/DFS) to solve these structural problems. While Graph I explored how to traverse graphs and find paths with costs, Graph II focuses on the inherent properties of graphs themselves.
1. Weighted vs Unweighted Graphs
Unweighted Graph
All edges have equal weight (1 or 0)
- › Existence of paths
- › Topological ordering
- › Connectivity analysis
Weighted Graph
Edges have different costs/weights
- › Shortest path (Dijkstra)
- › Minimum spanning tree
- › Cost optimization
2. Core Concepts
3. DAG Deep Dive
What Makes a DAG Special?
A DAG (Directed Acyclic Graph) combines the power of directed edges with the guarantee of no cycles. This simple property unlocks powerful algorithms:
- ✓ Topological ordering always exists
- ✓ No infinite loops — all traversals terminate
- ✓ Partial ordering — captures prerequisite relationships
- ✓ Efficient algorithms — many problems become O(V + E)
Real-World DAG Applications
DAG vs Other Structures
| Structure | Directed? | Acyclic? | Topo Sort? |
|---|---|---|---|
| DAG | ✓ | ✓ | ✓ |
| Directed w/ Cycle | ✓ | ✗ | ✗ |
| Undirected Graph | ✗ | Optional | ✗ |
| Tree | ✓ | ✓ | ✓ |
4. Algorithm Categories
Topological Sort
Linear ordering of vertices in a DAG such that for every directed edge u→v, u comes before v. Essential for task scheduling with dependencies.
Example: Build System A → C → E B → C → E D → F Valid Order: A, B, D, C, F, E
Connected Components
Find groups of vertices where each pair is reachable. Uses BFS to explore and label components.
Undirected Graph:
A --- B C --- D
| |
A, B, C, D all connected = 1 component5. Choose an Algorithm
Compute indegree and outdegree for each vertex. Key for Kahn's algorithm and detecting sources/sinks.
calculateDegree(graph):
indegree = {}
outdegree = {}
for v in vertices:
indegree[v] = 0
outdegree[v] = graph[v].length
for v in vertices:
for u in graph[v]:
indegree[u]++6. Real-World Applications
Key Insight
In unweighted graphs, structure reveals properties. Topological sort tells you if a graph has dependencies that form a valid ordering. Connected components reveal natural groupings. Degree calculations help identify sources and sinks in the graph.
Remember
Topo Sort: Only works on DAGs. If it fails, the graph has a cycle.
Components: Use BFS to explore and label connected groups.
Degree: Indegree counts incoming edges, outdegree counts outgoing edges.