Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Graph Representation — Adjacency Matrix and Adjacency List

What is Graph:

G = (V,E)

Graph is a col­lec­tion of nodes or ver­tices (V) and edges(E) between them. We can tra­verse these nodes using the edges. These edges might be weighted or non-weighted.

There can be two kinds of Graphs

  • Un-directed Graph — when you can tra­verse either direc­tion between two nodes.
  • Directed Graph — when you can tra­verse only in the spec­i­fied direc­tion between two nodes.

Directed-and-Undirected-Graph

Directed-and-Undirected-Graph

Now how do we rep­re­sent a Graph, There are two com­mon ways to rep­re­sent it:

  • Adja­cency Matrix
  • Adja­cency List

Adja­cency Matrix:

Adja­cency Matrix is 2-Dimensional Array which has the size VxV, where V are the num­ber of ver­tices in the graph. See the exam­ple below, the Adja­cency matrix for the graph shown above.

Adjacency-Matrix

Adjacency-Matrix

adjMaxtrix[i][j] = 1 when there is edge between Ver­tex i and Ver­tex j, else 0.

It’s easy to imple­ment because remov­ing and adding an edge takes only O(1) time.

But the draw­back is that it takes O(V2) space even though there are very less edges in the graph.

Adja­cency List:

Adja­cency List is the Array[] of Linked List, where array size is same as num­ber of Ver­tices in the graph. Every Ver­tex has a Linked List. Each Node in this Linked list rep­re­sents the ref­er­ence to the other ver­tices which share an edge with the cur­rent ver­tex. The weights can also be stored in the Linked List Node.

Adjacency-List

Adjacency-List

Com­plete Code for Graph Using Adja­cency List:


Out­put:

Nodes connected to Vertex 0 are :
  3  2  1
Nodes connected to Vertex 1 are :
  2  0
Nodes connected to Vertex 2 are :
  4  1  0
Nodes connected to Vertex 3 are :
  0
Nodes connected to Vertex 4 are :
  2

 

You may also like...

  • mgiota

    Nice arti­cle!

    In the addEdge method, when you add the node to the source adj list, I guess you wanted to write

    adn.next = array.head;
    array.head = adn;