Home > Articles, Data Structures & Algorithms > Implementation of graph representation with an adjacency list.

Implementation of graph representation with an adjacency list.

The following program reads a set of edges that define a graph and creates a representation of this graph with an adjacency list. The adjacency list of a graph is an array of lists, one for each vertex, where the j-th list contains a linked list of the nodes which are connected with the j-th vertex.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <cstdlib>

using namespace std;

struct node {
  int v; node * next;

  node (int x, node * t) {
    v = x; next = t;
  }
};

typedef node * plink;

const int V = 100;

int
main () {
  int i, j;

  plink adj[V] = { 0 };

  while (cin >> i >> j) {
    adj[j] = new node (i, adj[j]);
    adj[i] = new node (j, adj[i]);
  }

  return EXIT_SUCCESS;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: