Graphs

Introduction

A graph G = (V, E) consists of a set of vertices V and a set of edges E, where each edge connects two vertices. Unlike trees, graphs can contain cycles and a vertex can have any number of neighbors. Graphs are the most general non-linear data structure.

Terminology

• Directed vs undirected — whether edges have direction.
• Weighted vs unweighted — whether edges carry a numeric cost.
• Degree of a vertex — number of incident edges.
• Path — sequence of vertices connected by edges.
• Cycle — path that starts and ends at the same vertex.
• Connected graph — path exists between every pair of vertices.
• Complete graph — every pair of vertices is connected.

Representations

Adjacency matrix: a V×V matrix A where A[i][j] = 1 (or weight) if edge (i,j) exists, 0 otherwise. Space O(V²), edge lookup O(1). Best for dense graphs.

Adjacency list: for each vertex, keep a list of its neighbors. Space O(V + E), edge lookup O(degree). Best for sparse graphs.

// Adjacency list
struct Node { int v; struct Node* next; };
struct Node* adj[V];

Breadth-First Search (BFS)

BFS explores neighbors level by level using a queue. It finds the shortest path in an unweighted graph.

void BFS(int start) {
    visited[start] = 1;
    enqueue(start);
    while (!empty(q)) {
        int u = dequeue();
        for each neighbor v of u
            if (!visited[v]) { visited[v] = 1; enqueue(v); }
    }
}

Time complexity: O(V + E).

Depth-First Search (DFS)

DFS follows one path as deep as possible before backtracking. Uses recursion (or a stack).

void DFS(int u) {
    visited[u] = 1;
    for each neighbor v of u
        if (!visited[v]) DFS(v);
}

Time complexity: O(V + E). DFS is used for cycle detection, topological sort, and finding connected components.

Shortest Path — Dijkstra's Algorithm

On a graph with non-negative weights, Dijkstra finds the shortest path from a source to all vertices using a priority queue. Time complexity O((V + E) log V) with a binary heap.

Minimum Spanning Tree

A spanning tree connects all vertices with V - 1 edges and no cycles. The minimum spanning tree (MST) has minimum total weight. Two classic algorithms:

• Prim's — grow the MST from a starting vertex, adding the cheapest edge to the frontier.
• Kruskal's — sort edges by weight and add them if they do not form a cycle (uses union-find).

Applications

1. Social networks (friends graph).
2. Road and airline networks.
3. Web pages and hyperlinks (PageRank).
4. Computer networks (routing).
5. Dependency resolution.
6. Recommendation systems.

Summary

Graphs model arbitrary pairwise relationships. Represent them with an adjacency matrix or list depending on density. BFS and DFS are the fundamental traversals; Dijkstra and Prim/Kruskal solve classic weighted-graph problems.

Important Questions

1. Define graph and terms: path, cycle, degree, connected.
2. Differentiate adjacency matrix and adjacency list.
3. Write the BFS algorithm and give its complexity.
4. Write the DFS algorithm and give its complexity.
5. Compare BFS and DFS.
6. Explain Dijkstra's shortest-path algorithm.
7. What is a minimum spanning tree? Explain Prim's algorithm.
8. List real-world applications of graphs.