PROBLEM SOLVING - GRAPHS IN C INTRODUCTION

Graph Basics in C

Graph Definition

A graph in C is a non-linear data structure consisting of nodes (vertices) and edges. Key characteristics:

  • Vertices (V) - Represent entities/nodes
  • Edges (E) - Connections between vertices
  • Directed/Undirected - Edges may have direction
  • Weighted/Unweighted - Edges may have weights
// Basic graph representation
struct Graph {
    int V; // Number of vertices
    int E; // Number of edges
    int **adjMatrix; // Adjacency matrix
};

Graph Applications

Graphs are fundamental in computer science with various applications:

  • Social networks (friends connections)
  • Transportation and road networks
  • Computer networks and routing
  • Web page ranking (PageRank)
  • Recommendation systems
  • Dependency resolution
  • Circuit design

Graph Representation

Graphs can be represented in several ways in C:

// Method 1: Adjacency Matrix
int adjMatrix[V][V]; // 2D array

// Method 2: Adjacency List
struct Node {
    int vertex;
    struct Node* next;
};
struct Node* adjList[V]; // Array of linked lists

// Method 3: Edge List
struct Edge {
    int src, dest, weight;
};
struct Edge edgeList[E];

Common Graph Operations

Basic operations performed on graphs:

  • Add/Remove Vertex - Modify graph structure
  • Add/Remove Edge - Change connections
  • Traversal - DFS, BFS
  • Shortest Path - Dijkstra's, Bellman-Ford
  • Minimum Spanning Tree - Prim's, Kruskal's
  • Topological Sorting - For DAGs

Graph Traversal

Basic traversal algorithms:

// Depth-First Search (DFS)
void DFS(int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);
    for each neighbor u of v {
        if (!visited[u])
            DFS(u, visited);
    }
}

// Breadth-First Search (BFS)
void BFS(int s) {
    bool visited[V] = {false};
    queue q;
    visited[s] = true;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("%d ", v);
        for each neighbor u of v {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}