Graphs

Graphs

Graphs are fundamental data structures used to represent relationships and connections. Understanding graphs is essential for GATE CS.

Graph Basics

Graph G = (V, E) where:

• V: Set of vertices (nodes)
• E: Set of edges (connections)

Graph Types

1. Directed Graph (Digraph)

Edges have direction (A → B)

2. Undirected Graph

Edges have no direction (A - B)

3. Weighted Graph

Edges have weights/costs

4. Unweighted Graph

All edges have same weight (or no weight)

Graph Terminology

• Vertex/Node: Element in graph
• Edge: Connection between vertices
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at same vertex
• Connected: Path exists between all pairs
• Degree: Number of edges incident to vertex
• In-degree: Incoming edges (directed)
• Out-degree: Outgoing edges (directed)
• Adjacent: Vertices connected by edge
• Subgraph: Graph formed from subset of vertices/edges

Graph Properties

Handshaking Lemma:

• Sum of all degrees = 2 × |E|
• In directed graph: Sum of in-degrees = Sum of out-degrees = |E|

Complete Graph:

• Every pair of vertices connected
• Number of edges = n(n-1)/2 (undirected)
• Number of edges = n(n-1) (directed)

Graph Representation

1. Adjacency Matrix

2D array where matrix[i][j] = 1 if edge exists, 0 otherwise.

For weighted graph: matrix[i][j] = weight

Space Complexity: O(V²)

Time Complexities:

• Check edge: O(1)
• Add edge: O(1)
• Remove edge: O(1)
• Get neighbors: O(V)

Code:

int adjMatrix[V][V];

void addEdge(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;  // For undirected
}

int hasEdge(int u, int v) {
    return adjMatrix[u][v];
}

Advantages:

• Fast edge lookup
• Simple implementation

Disadvantages:

• High memory usage
• Slow to iterate neighbors

2. Adjacency List

Array of lists where each list contains neighbors.

Space Complexity: O(V + E)

Time Complexities:

• Check edge: O(V)
• Add edge: O(1)
• Remove edge: O(V)
• Get neighbors: O(degree)

Code:

struct Node {
    int vertex;
    struct Node* next;
};

struct Node* adjList[V];

void addEdge(int u, int v) {
    struct Node* newNode = createNode(v);
    newNode->next = adjList[u];
    adjList[u] = newNode;
    
    // For undirected graph
    newNode = createNode(u);
    newNode->next = adjList[v];
    adjList[v] = newNode;
}

Advantages:

• Space efficient
• Fast to iterate neighbors

Disadvantages:

• Slower edge lookup
• More complex implementation

Representation Comparison

Graph Traversals

Breadth-First Search (BFS)

BFS explores graph level by level.

Algorithm:

1. Start from source vertex
2. Visit all neighbors
3. Then visit neighbors of neighbors
4. Use queue to maintain order

Code:

void BFS(int start) {
    bool visited[V] = {false};
    Queue q;
    
    visited[start] = true;
    enqueue(&q, start);
    
    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        printf("%d ", u);
        
        // Visit all neighbors
        for (int v = 0; v < V; v++) {
            if (hasEdge(u, v) && !visited[v]) {
                visited[v] = true;
                enqueue(&q, v);
            }
        }
    }
}

Time Complexity: O(V + E)

Space Complexity: O(V)

Applications:

• Shortest path in unweighted graph
• Level-order traversal
• Finding connected components

Depth-First Search (DFS)

DFS explores as far as possible before backtracking.

Algorithm:

1. Start from source vertex
2. Visit unvisited neighbor
3. Recursively explore
4. Backtrack when no unvisited neighbors

Code (Recursive):

void DFS(int u, bool visited[]) {
    visited[u] = true;
    printf("%d ", u);
    
    for (int v = 0; v < V; v++) {
        if (hasEdge(u, v) && !visited[v]) {
            DFS(v, visited);
        }
    }
}

Code (Iterative):

void DFS(int start) {
    bool visited[V] = {false};
    Stack s;
    
    push(&s, start);
    
    while (!isEmpty(&s)) {
        int u = pop(&s);
        
        if (!visited[u]) {
            visited[u] = true;
            printf("%d ", u);
            
            // Push neighbors in reverse order
            for (int v = V - 1; v >= 0; v--) {
                if (hasEdge(u, v) && !visited[v]) {
                    push(&s, v);
                }
            }
        }
    }
}

Time Complexity: O(V + E)

Space Complexity: O(V)

Applications:

• Cycle detection
• Topological sorting
• Finding strongly connected components
• Maze solving

Graph Algorithms

Cycle Detection

Undirected Graph:

• Use DFS
• If we find edge to visited node (not parent), cycle exists

Directed Graph:

• Use DFS with recursion stack
• If node in recursion stack is visited again, cycle exists

Topological Sort

Topological Sort is ordering of vertices such that for every edge (u, v), u comes before v.

Algorithm (DFS-based):

1. Do DFS
2. When node finished, add to result
3. Reverse result

Time Complexity: O(V + E)

Applications:

• Task scheduling
• Build systems
• Course prerequisites

GATE CS Important Points

1. Representation: Know both adjacency matrix and list
2. Traversals: Master BFS and DFS
3. Time Complexities: O(V + E) for both BFS and DFS
4. Applications: Shortest path, cycle detection, topological sort
5. Graph Properties: Handshaking lemma, complete graphs

Practice Tips

1. Implement Both Representations: Code adjacency matrix and list
2. Traversal Practice: Implement BFS and DFS
3. Cycle Detection: Practice detecting cycles
4. Graph Construction: Build graphs from given data
5. Previous Year Questions: Solve GATE graph questions