Design a site like this with
Get started

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



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

Adjacency List Representation

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

Adjaceny Matrix For Graph

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

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

  1. […] this article, we will discuss popular graph traversal algorithms. Before proceeding please read this article at first to get clear idea about […]


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


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

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

    In addition, the blog loads very quick for me on Safari.
    Outstanding Blog!

    Liked by 1 person

  5. you’re actually a excellent webmaster. The web site loading
    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

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


    1. Sure Rhett, Just ping me ( with the topic you want to write about.
      I would be happy to read it and post the same.
      Thanks for your comment! 😉


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: