What is Graph?

Graph consists of a set of nodes or vertices and edges or arcs. Edge joints two vertices, edge (v,u) is said to be go from v to u. Graph may also associate some weight to edges.

Types of Graphs:

Directed, Undirected, Weighted, Unweighted

Some of the graph Algorithms:

Depth First Search (DFS), Breadth First Search (BFS), Dijkstra’s Algorithm, Floyd – Warshall algorithm

 

Graph and its representation

Representation of Graph in Programming:

Adjacency Matrix

Adjacency List

Adjacency Matrix:

A 2D matrix in which row presents source vertices and column represents destination vertices.

If cell(I,j) ==1 it means there is a edge from i to j.

If cell(I,j)==0 it means there is no edge from i to j.

 

Graph :

 

 

Adjacency Matrix Representation of Graph

1             2             3             4             5              6

1              0              1              0              0              1              0

2              1              0              1              0              1              0

3              0              1              0              1              0              0

4              0              0              1              0              1              1

5              1              1              0              1              0              0

6              0              0              0              1              0              0

 

Adjacency List Representation of Graph:

Vertices are stored as list of array, and every vertex contains point to list of adjacent vertices.

 

1 => 2 => 5

2 => 1 => 3 => 5

3 => 2 => 4

4 => 3 => 5 => 6

5 => 1 => 2 => 4

6 => 4