Skip to main content

Lab 7: Graphs and Adjacency Matrix

Lab PDF

🧠 What is a Graph?​

A graph is a collection of:

  • Vertices (nodes) β€” represent entities
  • Edges (links) β€” represent relationships between vertices

Graph Variants​

  • Direction:

    • Directed: edges have direction (A β†’ B)
    • Undirected: edges are bidirectional (A β€” B)

  • Weight:

    • Weighted: edges have values (e.g., distances)
    • Unweighted: edges have no value

  • Cycle:

    • Cyclic: contains a cycle
    • Acyclic: no cycles

πŸ”Ž Visual:
Vertices: ●, Edges: β†’ or β€”

πŸ“Š Graph Representations​

1. Adjacency Matrix​

A 2D array matrix[V][V], where matrix[i][j] = 1 if there's an edge from vertex i to j, else 0.

Example:

Graph:
0 β†’ 1
0 β†’ 2
1 β†’ 2

Adjacency Matrix:
  0 1 2
0 0 1 1
1 0 0 1
2 0 0 0

2. Adjacency List​

Each vertex maintains a list of its neighbors.

Example:

vector<vector<int>> adj(V);
adj[0] = {1, 2};
adj[1] = {2};
adj[2] = {};

πŸ” Graph Searching​

Why search a graph?

  • Find connectivity between vertices
  • Detect cycles or paths
  • Solve problems like topological sort or shortest path

🧭 Depth-First Search (DFS)​

πŸ”§ Strategy​

Explore a vertex as deeply as possible, then backtrack.

βœ… Pseudocode​

DFS(vertex u):
    mark u as visited
    for each neighbor v of u:
        if v is not visited:
            DFS(v)

πŸ’» C++ Code​

void DFS(int u, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, adj, visited);
        }
    }
}

πŸ“Œ Application: Topological Sort​

Problem​

Given a Directed Acyclic Graph (DAG), list vertices such that for every edge u β†’ v, u comes before v.

🧠 Idea​

Use DFS, but add nodes to a stack after visiting all neighbors.

πŸ’» C++ Code​

void topologicalSortUtil(int u, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& Stack) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
            topologicalSortUtil(v, adj, visited, Stack);
    Stack.push(u);
}

πŸ‘©β€πŸ« Example Problem: Teacher’s Candy Distribution​

Emily wants to distribute candies to students with rules like:

If A is teased by B, then A should get candy before B.

Convert to Graph:​

  • Nodes = Students
  • Edge A β†’ B if B teased A
  • Topological sort gives valid candy order

🚢 Breadth-First Search (BFS)​

πŸ”§ Strategy​

Explore all neighbors at current depth before going deeper.

βœ… Pseudocode​

BFS(start):
    mark start as visited
    enqueue start to Q
    while Q is not empty:
        u = Q.dequeue()
        for each neighbor v of u:
            if v is unvisited:
                mark v visited
                enqueue v

πŸ’» C++ Code​

void BFS(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

πŸƒ Application: Shortest Path (Unweighted Graph)​

If all edge costs are equal (e.g., 1), BFS finds the shortest path from A to B.

πŸ§ͺ Example Problem: Social Network​

You are given a social graph:

  • Node = User
  • Edge = Friendship

Task:
List all friends up to degree N.

Strategy:​

  • Use BFS with depth level tracking
  • Stop when level > N

πŸ” Example Problem: Bipartite Graph Check​

Definition:​

Graph is bipartite if nodes can be divided into two sets A and B such that every edge connects a node from A to B.

πŸ”§ Strategy: BFS Coloring​

  • Start with a node, color it 0
  • Neighboring nodes get 1, then their neighbors get 0 again, etc.
  • If any neighbor has the same color β†’ Not bipartite

πŸ’» C++ Code​

bool isBipartite(vector<vector<int>>& adj) {
    int V = adj.size();
    vector<int> color(V, -1);
    
    for (int i = 0; i < V; i++) {
        if (color[i] == -1) {
            queue<int> q;
            color[i] = 0;
            q.push(i);

            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

🧠 Exercise Set​

Exercise 1: DFS and BFS with Adjacency Matrix​

  • Implement adjacency matrix for a given graph
  • Perform DFS and BFS from vertex 4

Exercise 2: Friendship Degree​

  • For a user, list all friends with friendship degree ≀ N using BFS and adjacency matrix

Exercise 3: Bipartite Graph Check​

Graphs:

G1 = ({1,2,3,4,5,6,7,8,9}, {12, 13, 45, 56, 75, 24, 58, 79, 43, 89})
G2 = ({1,2,3,4,5,6,7,8,9}, {12, 13, 45, 56, 75, 24, 58, 79, 43, 89, 47})
  • Convert into adjacency matrix
  • Check if bipartite

🧠 Graph Modeling Tips​

  1. Identify nodes and edges
  2. Clarify objective
  3. Convert problem to graph terms
  4. Apply graph algorithm
  5. Convert results to required output

🌐 Real-World Applications​

  • Social network suggestions
  • Google Maps
  • Job scheduling (topological sort)
  • AI pathfinding (games, robotics)

πŸ“š More Algorithms​

  • Bidirectional Search: Search from both ends
  • Iterative Deepening DFS (IDS): DFS + BFS memory advantage
  • Dijkstra / A Search*: For weighted graphs

πŸ”— References​