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

Adjacency List

An array of Linked Lists, where each index corresponds to a source node and its links are the different destinations it connects with.

Adjacency List Illustration.png

Implementation

MAX is the number of possible vertices, so the space complexity of an adjacency list is O(V + E).

  • V is the possible vertices.
  • E are the number of edges in the graph.

typedef struct node {
  int data;
  struct node *link;
} *Node;

typedef Node Graph[MAX];

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

Operations

// similar to insertSorted
void addEdge(Graph G, int src, int dest) {
  Node *trav;
  for (trav = &G[src]; *trav != NULL && (*trav)->data < dest;
       trav = &(*trav)->link) {
  }

  Node newNode = (Node)malloc(sizeof(struct node));
  if (newNode != NULL) {
    Node tmp = *trav;
    newNode->data = dest;
    newNode->link = *trav;
    *trav = newNode;
    free(tmp);
  }
}

// isMember
bool edgeExists(Graph G, int src, int dest) {
  Node *trav;
  for (trav = &G[src]; *trav != NULL && (*trav)->data != dest;
       trav = &(*trav)->link) {
  }

  return *trav == NULL ? false : true;
}

References