Graph’s In Depth [PART 1]

Graph is a non linear data structure which consist of set of Edges & Vertices.

They have applications in many fields of studies, Computer Networks are visualized through graphs, Internet is a one big example.

Unlike Tree data structure,which is connected,graph may not always be connected.

In the above graph:-

V={A,B,C,D,E,F}

E={(A,B),(A,D),(B,C),(C,D),(D,E),(E,F),(C,F)}

Where V & E is a set of Vertices & Edges respectively.

Graph’s can be directed,un-directed,cyclic weighted.

Graph Terminologies

Edge : Edge connects 2 vertices together in a graph.

Adjancent Vertices : 2 vertices are adjacent if there is an edge between them.
An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two vertices to which it is attached, called its endpoints.

Degree of Vertex : It represents the number of incoming edges a vertex has .

Indegree : Indegree is number of incoming edges a vertex has.

Outdegree: Outdegree represents the number of outgoing edges from a vertex.

Source Vertex : A vertex with indegree zero is a source vertex.

Destination Vertex : A vertex with outdegree zero is a destination vertex.

Isolated Vertex : A vertex which cannot be reached from any other vertex.

Path : Path can be defines as the sequence of edges from source vertex to destination vertex.

Cycle : Cycle is a path that starts and end at the same vertex.

Strongly Connected Graph: A graph is Strongly Connected if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.

Weakly Connected Graph : A directed graph is called Weakly Connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. The vertices in a weakly connected graph have either outdegree or indegree of at least 1.

Bridge : A bridge is an edge whose removal would disconnect the graph.

Forest : If a graph does not contain cycles,then it is called forest.

Spanning tree of an undirected graph is a subgraph that is a tree which includes all of the vertices of the graph.

Graph can be represented by :-

• Adjacency List

• Adjacency Matrix

Adjacency List

Adjacency list is basically implemented by linked-list and array.

It can be called as Array of List.

The adjacency list representation of above graph is :-

Vertex A is adjancent to : B & D.

Thus, ‘A’ array cell consists of B & D chained in linked list.

Adjacency Matrix

An Adjacency matrix is a 2-dimensional array (i.e MATRIX[V][V]] where V is vertices. )

If there is an direct edge between 2 vertices then ‘1’ is added in the corresponding cell.

If there is no edge between 2 vertices then ‘0’ is added in the corresponding cell.

The adjacency matrix for above graph is represented below:-

Since, There is an edge between A -> B , the entry in cell is 1.

(Note :- The above graph does not contain any cycle).

When to Use What ?

Use Adjacency List When:-

• Graph is sparse i.e There are less number of edges in the graph.

Use Adjacency Matrix When :-

• Graph is dense i.e There are more number of edges in the graph.

Implementation Of Graph

Stay Tuned ..