Graphs data structure in C

• Graphs are non-linear data structures consisting of nodes (vertices) and connections between them (edges)
• They are used to represent relationships or networks
• C can be used to implement graphs

Basic Concepts

• Vertex: A node in the graph which can hold data
• Edge: A connection between two vertices that can be directed or undirected
• Directed Graph: Edges possessing direction from one vertex to another
• Undirected Graph: Edges lacking direction, thus the connection is bidirectional
• Weighted Graph: Edges possessing weights or costs
• Path: A sequence of vertices connected by edges
• Cycle: A path that starts and ends at the same vertex
• Adjacency: Indicates two vertices are connected by an edge

Graph Representation

• Adjacency Matrix: A 2D array where matrix[i][j] = 1 if an edge exists from vertex i to vertex j; otherwise, it's 0; for weighted graphs, matrix[i][j] stores the weight of the edge
• Adjacency List: An array of lists where each array element represents a vertex, and the list contains the adjacent vertices

Adjacency Matrix Implementation in C

• Requires a two-dimensional array
• For a graph with 'V' vertices, the matrix is of size V x V
• Suitable for dense graphs where most vertices are connected
• O(V^2) is the space complexity

Adjacency List Implementation in C

• Requires an array of linked lists
• Each linked list stores the adjacent vertices for a given vertex
• Memory efficient for sparse graphs (graphs with few edges)
• O(V + E) is the space complexity, where E is the number of edges

C Code Example: Adjacency Matrix

 #include <stdio.h>
 #include <stdlib.h>

 #define V 5 /* Number of vertices */

 /* Function to initialize the adjacency matrix */
 void initMatrix(int adjMatrix[][V]) {
  int i, j;
  for (i = 0; i < V; i++)
  for (j = 0; j < V; j++)
  adjMatrix[i][j] = 0;
 }

 /* Function to add an edge to the graph */
 void addEdge(int adjMatrix[][V], int u, int v) {
  adjMatrix[u][v] = 1;
  adjMatrix[v][u] = 1; /* For undirected graph */
 }

 /* Function to print the adjacency matrix */
 void printMatrix(int adjMatrix[][V]) {
  int i, j;
  for (i = 0; i < V; i++) {
  printf("Vertex %d: ", i);
  for (j = 0; j < V; j++)
  printf("%d ", adjMatrix[i][j]);
  printf("\n");
  }
 }

 int main() {
  int adjMatrix[V][V];

  initMatrix(adjMatrix);

  addEdge(adjMatrix, 0, 1);
  addEdge(adjMatrix, 0, 4);
  addEdge(adjMatrix, 1, 2);
  addEdge(adjMatrix, 1, 3);
  addEdge(adjMatrix, 1, 4);
  addEdge(adjMatrix, 2, 3);
  addEdge(adjMatrix, 3, 4);

  printMatrix(adjMatrix);

  return 0;
 }

C Code Example: Adjacency List

 #include <stdio.h>
 #include <stdlib.h>

 /* Structure for an adjacency list node */
 struct AdjListNode {
  int dest;
  struct AdjListNode* next;
 };

 /* Structure for an adjacency list */
 struct AdjList {
  struct AdjListNode* head;
 };

 /* Structure for a graph */
 struct Graph {
  int V; /* Number of vertices */
  struct AdjList* array;
 };

 /* Function to create a new adjacency list node */
 struct AdjListNode* newAdjListNode(int dest) {
  struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
  newNode->dest = dest;
  newNode->next = NULL;
  return newNode;
 }

 /* Function to create a graph */
 struct Graph* createGraph(int V) {
  struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
  graph->V = V;
  graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
  int i;
  for (i = 0; i < V; i++)
  graph->array[i].head = NULL;
  return graph;
 }

 /* Function to add an edge to the graph */
 void addEdge(struct Graph* graph, int src, int dest) {
  struct AdjListNode* newNode = newAdjListNode(dest);
  newNode->next = graph->array[src].head;
  graph->array[src].head = newNode;

  /* For undirected graph, add an edge from dest to src also */
  newNode = newAdjListNode(src);
  newNode->next = graph->array[dest].head;
  graph->array[dest].head = newNode;
 }

 /* Function to print the graph */
 void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->V; v++) {
  struct AdjListNode* pCrawl = graph->array[v].head;
  printf("Adjacency list of vertex %d\n head ", v);
  while (pCrawl) {
  printf("-> %d", pCrawl->dest);
  pCrawl = pCrawl->next;
  }
  printf("\n");
  }
 }

 int main() {
  int V = 5;
  struct Graph* graph = createGraph(V);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 4);
  addEdge(graph, 1, 2);
  addEdge(graph, 1, 3);
  addEdge(graph, 1, 4);
  addEdge(graph, 2, 3);
  addEdge(graph, 3, 4);

  printGraph(graph);

  return 0;
 }

Graph Traversal

• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking and uses a stack (implicitly through recursion)
• Breadth-First Search (BFS): Explores all the neighbors of a node before moving to the next level of neighbors and uses a queue

Depth-First Search (DFS)

• Algorithm:
• Start at a vertex
• Mark the vertex as visited
• Recursively call DFS for each adjacent unvisited vertex

Breadth-First Search (BFS)

• Algorithm:
• Start at a vertex
• Enqueue the vertex
• While the queue is not empty:
• Dequeue a vertex
• Mark the vertex as visited
• Enqueue all unvisited adjacent vertices

C Code Example: DFS

 #include <stdio.h>
 #include <stdlib.h>

 #define V 5

 int adjMatrix[V][V];
 int visited[V];

 void initMatrix() {
  int i, j;
  for (i = 0; i < V; i++) {
  for (j = 0; j < V; j++) {
  adjMatrix[i][j] = 0;
  }
  visited[i] = 0;
  }
 }

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

 void DFS(int v) {
  visited[v] = 1;
  printf("%d ", v);

  for (int i = 0; i < V; i++) {
  if (adjMatrix[v][i] == 1 && !visited[i]) {
  DFS(i);
  }
  }
 }

 int main() {
  initMatrix();
  addEdge(0, 1);
  addEdge(0, 2);
  addEdge(1, 3);
  addEdge(2, 4);

  printf("DFS traversal starting from vertex 0: ");
  DFS(0);
  printf("\n");

  return 0;
 }

C Code Example: BFS

 #include <stdio.h>
 #include <stdlib.h>

 #define V 5

 int adjMatrix[V][V];
 int visited[V];
 int queue[V];
 int front = 0, rear = 0;

 void initMatrix() {
  int i, j;
  for (i = 0; i < V; i++) {
  for (j = 0; j < V; j++) {
  adjMatrix[i][j] = 0;
  }
  visited[i] = 0;
  }
  front = rear = 0;
 }

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

 void enqueue(int v) {
  queue[rear++] = v;
 }

 int dequeue() {
  return queue[front++];
 }

 int isEmpty() {
  return front == rear;
 }

 void BFS(int startVertex) {
  visited[startVertex] = 1;
  enqueue(startVertex);

  while (!isEmpty()) {
  int currentVertex = dequeue();
  printf("%d ", currentVertex);

  for (int i = 0; i < V; i++) {
  if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
  visited[i] = 1;
  enqueue(i);
  }
  }
  }
 }

 int main() {
  initMatrix();
  addEdge(0, 1);
  addEdge(0, 2);
  addEdge(1, 3);
  addEdge(2, 4);

  printf("BFS traversal starting from vertex 0: ");
  BFS(0);
  printf("\n");

  return 0;
 }

Applications of Graphs

• Social networks: Representing relationships between users
• Mapping: Representing road networks
• Recommendation systems: Suggesting items based on user preferences
• Network routing: Finding the shortest path between two points in a network
• Scheduling: Representing tasks and their dependencies

Common Graph Algorithms

• Shortest Path Algorithms: Dijkstra's algorithm and Bellman-Ford algorithm find the shortest path between two vertices
• Minimum Spanning Tree Algorithms: Prim's algorithm and Kruskal's algorithm find a minimum spanning tree for a connected, weighted graph
• Topological Sort: Orders the vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex A to vertex B, vertex A comes before vertex B in the ordering
• Connected Components: Identifying sets of vertices that are reachable from each other

Explore graphs, a non-linear data structure consisting of nodes and edges. Learn about vertices, edges, directed vs undirected graphs, and weighted graphs. Discover graph representations using Adjacency Matrix and Adjacency List.