Graph Theory is the mathematical theory of the properties and applications of graph.Graphs can be used to represent almost all the problems and this quality makes graph interesting.
Graph helps us to visualise the problem with the help of 'Vertices / Nodes' and uses 'Edges' to represent relationships between nodes.
Types of Graphs :
- Undirected Graph
An Undirected graph is a graph in which 'Edges' have no orientation they are 'Bidirectional' (which means that you can go from one node to another node and from that node to original node).
. 'Edge' ( line connecting) A-B (A to B) is equal as B-A (B to A).
Analogy : Let's say we are travelling between to cities (node/ vertices) with the help of road (edges between two nodes).
Source City (A) : From where journey started.
Destination City (C) : Where our journey will end.
Roads : Edges between our nodes.
And we take path A-D-B-C from source city to destination city and while returning from destination city to source city we are allow to take same path C-B-D-A then that is the example of Undirected Graph.
Directed Graph :
An Directed graph sometimes also know as digraph is a graph in which 'Edges' have orientation and they are not 'Bidirectional' (which means that you can't go from one node to another node).
In above image you can see that edges are directed from one node to another node because of arrow head representing their direction.
'Edge' ( line connecting) A-B (A to B) is not equal. or same as. B-A (B to A).
Analogy : Let's say we are travelling between to cities (node/ vertices) with the help of road (edges between two nodes).
Source City (A) : From where journey started.
Destination City (C) : Where our journey will end.
Roads : Edges between our nodes.
And we take path A-D-B-C from source city to destination city and while returning from destination city to source city we are not allow to take same path C-B-D-A then that is the example of Directed Graph.
Weighted Graph :
Some graph can have edges that contains a certain 'Weights' which represent an arbitrary values such as cost, distance,quantity.
Weighted graph can be 'Directed' and 'Undirected'.
Analogy : Let's say we are travelling between cities back to in. (node/ vertices) with the help of road (edges between two nodes).
Source City (A) : From where journey started.
Destination City (C) : Where our journey will end.
Roads : Edges between our nodes.
Distance between nodes (W) for our analogy.
And we take path A (12) – C (20) – B (10) – A then the distance we travel will be 12 + 20 + 10 = 42.
Special Graphs :
Trees :
A tree is an undirected graph with no cycle. It is connected with 'N' number of nodes and 'N-1' of edges. Where 'N' can be any number.
Let's say : A tree graph has N (nodes) where 'N' : 100 then it will be connected with 'N-1' edges which is 99 edges.
Rooted Trees :
A rooted tree is a tree with the 'a designated root node' . Where every edge either points away from or towards to the root node. When edges point away from the root the graph is called 'arborescence (out-tree)' and 'anti-arborescence (in-tree).
Directed Acyclic Graph (DAGs) :
DAGs are 'Directed graph with no cycle'. These graphs play an important role in representing structures with dependencies. Several effective algorithm exist to operates on DAGs.
Facts : All out- trees are DAGs but not all DAGs are out-trees.
DAGs are important in computer science because they very often represents system with dependencies like schedulers, bill system compilers.
Bipartite Graph :
A bipartite graph is one whose ' Vertices can be split into two independent ( U and V ) group so that every edge connects between U and V '.
Complete Graph :
A complete graph is one where there is a unique edge between every pair of nodes.
A complete graph with 'N' vertices is denoted as the graph Kn. Where 'N' is number of nodes. Complete graph is seen as worst case scenario graph.
Representing Graph :
The one think which we have to think about is 'How we are representing graph in our system, what kind of data structure we are using' be cause it can have a huge impact on performance.
The simplest way is to repress it as 'Adjacency Matrix'.
Adjacency Matrix :
A 'Adjacency Matrix' (M) is a very simple way to represent a graph. The idea is that the cell ' M[i][j] ' represent the weight of going from node i to j.
PROS :
- Space efficient for representing dense graph.
- Edge weight lookup is O(1).
- Simplest graph representation.
CONS :
- Requires O(V^2) Space.
- Iterating over all edges takes O(V^2) times.
Adjacency List :
An adjacency list is a way of represent a graph as a 'Map from node to Lists of edges'.
PROS :
- Space efficient for representing sparse graph.
- Iterating over all edges is efficient.
CONS :
- Less space efficient for denser graph.
- Edge weight lookup is O(E).
- Slightly more complex graph representation.
Edge List :
An edge list is a way to represent a graph simply as an ' Unordered List of edges.' Assume the notation for any triplet (u,v,w) means : "The cost from node u to node v is w".
PROS :
- Space efficient for representing sparse graphs.
- Iterating over all edges is efficient.
- Very simple structure.
CONS :
- Less space efficient for denser graph.
- Edge weight lookup is O(E).
*…This blog will get updated frequently. Still working on this blog ….*