Graphs
A graph G = (V, E) is a set of vertices and edges. Graphs can be directed or undirected, weighted or unweighted.
Representation
| Adjacency matrix | Adjacency list |
|---|---|
| V × V array; O(V²) space | An array of lists; O(V + E) space |
| O(1) edge lookup | Better for sparse graphs |
BFS and DFS
#include <stdio.h>
#define V 6
int g[V][V] = {
{0,1,1,0,0,0},
{1,0,0,1,1,0},
{1,0,0,0,1,0},
{0,1,0,0,0,1},
{0,1,1,0,0,1},
{0,0,0,1,1,0}};
void bfs(int s) {
int vis[V] = {0}, q[V], f = 0, r = 0;
q[r++] = s; vis[s] = 1;
while (f < r) {
int u = q[f++];
printf("%d ", u);
for (int v = 0; v < V; v++)
if (g[u][v] && !vis[v]) { vis[v] = 1; q[r++] = v; }
}
}
int seen[V];
void dfs(int u) {
seen[u] = 1; printf("%d ", u);
for (int v = 0; v < V; v++)
if (g[u][v] && !seen[v]) dfs(v);
}
int main() {
printf("BFS: "); bfs(0); printf("\n");
printf("DFS: "); dfs(0); printf("\n");
return 0;
}BFS: 0 1 2 3 4 5
DFS: 0 1 3 5 4 2
| BFS | DFS | |
|---|---|---|
| Uses | Queue | Stack / recursion |
| Finds | Shortest path (unweighted) | Cycles, topological order |
| Time | O(V + E) | O(V + E) |
Important Graph Algorithms
- Dijkstra: single-source shortest path (non-negative weights)
- Bellman-Ford: handles negative weights
- Floyd-Warshall: all-pairs shortest paths
- Prim / Kruskal: minimum spanning tree
- Topological sort: ordering of a DAG
Track your progress through the Data Structures course