# 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 :-

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.

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 ?

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

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

Stay Tuned ..

## 10 thoughts on “Graph’s In Depth [PART 1]”

1. Graph's In Depth [PART 2] – Shriniket's Blog

Like

2. Implement Graph Using Java – Shriniket's Blog

[…] If you are new to graph data structure , read article on graph introduction here. […]

Like

3. poker88 asia

I have been exploring for a little for any high-quality articles or weblog posts on this sort
of house . Exploring in Yahoo I ultimately stumbled upon this site.
Reading this info So i’m satisfied to convey that I have a very good uncanny feeling I
discovered just what I needed. I such a lot for sure will make sure to don?t omit this website and provides it a
look regularly.

Liked by 1 person

1. shriniket deshmukh

Thanks a lot.

Like

4. blog

Woah! I’m really digging the template/theme of this site.
It’s simple, yet effective. A lot of times it’s challenging to get that “perfect balance” between superb usability and visual appearance.

I must say that you’ve done a amazing job with this.

Outstanding Blog!

Liked by 1 person

5. shriniket deshmukh

Thank you so much

Like

6. blog

velocity is incredible. It sort of feels that you are doing any distinctive trick.

Also, The contents are masterpiece. you have performed a excellent activity on this topic!

Liked by 1 person

1. shriniket deshmukh

Thank you so much

Like

7. Rhett Mulligan

I absolutely love your blog and find nearly all of your post’s to be just what I’m looking for. Would you offer guest writers to write content for you? I wouldn’t mind writing a post or elaborating on some of the subjects you write about here. Again, awesome website!

Like

1. shriniket deshmukh

Sure Rhett, Just ping me (shriniketdeshmukh111@gmail.com) with the topic you want to write about.
I would be happy to read it and post the same.