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

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

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.

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 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.

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