Created: 2023-12-11 05:23
Status: #concept
Subject: Programming
Tags: Graph Multidimensional Array Adjacency List

Adjacency Matrix

We can store the graph in a 2D matrix containing boolean values 1 or 0 where the edge (1,2) can be represented as matrix[1][2].

  • the row is the source.
  • the col is the destination.

Adjacency Matrix Illustration.png

Implementation

MAX is the number of possible vertices, so the space complexity of a graph is O(N * N), where N is MAX vertices.

  • G[src][dest] can be 1 denoting a connection, or it can equal to the weight of a graph for Weighted Graphs.

typedef int Graph[MAX][MAX];

void init(Graph G) {
  for (int row = 0; row < MAX; row++) {
    for (int col = 0; col < MAX; col++) {
      G[row][col] = 0;
    }
  }
}

Operations

void addEdge(Graph G, int src, int dest) { G[src][dest] = 1; }

bool edgeExists(Graph G, int src, int dest) {
  return G[src][dest] == 1 ? true : false;
}
We need a Set and a Queue in order to keep track of the visited and nodesToVisit respectively.

  1. We enqueue the root node to scan in our nodesToVisit queue and mark it as visited[root] = 1;
  2. While nodesToVisit is not empty:
  3. We visit all nodes x of the front Node in nodesToVisit and if they are visited[x] == 0, mark them as visited[x] = 1 and enq(Q, x) them.
  4. We deq(Q) and print the element dequeued.

Time complexity is O(V+E).

void bfs(Graph G, int root) {
  // if node is visited, visited[node] == 1
  Set visited = {0};
  // a queue of the current nodes to process, before inserting to Set
  Queue Q = initQueue();
  
  if (Q != NULL) {
    // mark the root as visited & enqueue it
    visited[root] = 1;
    enq(Q, root);

    while (!isEmpty(Q)) {
      int x;
      for (x = 0; x < MAX; x++) {
        // if the current queue node is adjacent to node x & we didn't visit x
        if (G[Q->front->data][x] == 1 && !visited[x]) {
          visited[x] = 1; // mark x as visited
          enq(Q, x);      // enqueue x to visit all its nodes later
        }
      }
      // print the element we enqueued
      printf("%d ", deq(Q));
    }
  }
  puts("");
}

References