Graph Introduction
Graph
A graph is a collection of nodes and edges
Denoted by G = (V, E).
V = nodes (vertices, points).
E = edges (links, arcs) between pairs of nodes.
Graph size parameters: n = |V|, m = |E|.
Graph Example
Graph G can be represented as G = ( V , E )
Where Vertices(V) = {A,B,C,D,E}
Edge(E) =
{(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.
Tree Vs Graph
Trees are the restricted types of
graphs, just with some more rules.
Every tree will always be a graph
but not all graphs will be trees.
Linked List, Trees, and Heaps all
are special cases of graph
Types of Graph
Null Graph
A graph is known as null graph if there are no edges in
the graph.
Trivial Graph
Graph having only a single vertex, it is the
smallest graph possible.
Types of Graph
Undirected Graph
A graph in which edges do not have any direction.
Directed Graph
A graph in which edge has direction.
Types of Graph
Connected Graph
The graph in which from one node we can visit any
other node.
Disconnected Graph
The graph in which at least one node is not reachable
from a node.
Types of Graph
Complete Graph
The graph in which from each node there is an edge to
each other node.
Cycle Graph
The graph in which the graph is a cycle in itself, the
degree of each vertex is 2.
Graph Representations
Representation of Graph
There are two ways to store a graph:
Adjacency Matrix
Adjacency List
Adjacency Matrix
In this method, the graph is stored in the form
of the 2D matrix where rows and column
denote vertices.
Adjacency List
This graph is represented as a collection of linked
lists.
There is an array of pointer which points to the edges
connected to that vertex
Breadth First Search(BFS)
Breadth first search is a graph traversal algorithm
that starts traversing the graph from root node and
explores all the neighbouring nodes.
It uses a Queue data structure for implementation.
Breadth-first search (BFS) is an algorithm that is
used to graph data or searching tree or traversing
structures.
Algorithm
BFS (G, s) //Where G is the graph and s is the source
node
let Q be queue.
[Link]( s ) //Inserting s in queue until all its neighbour
vertices are marked.
mark s as visited.
while ( Q is not empty) //Removing that vertex from queue,whose
neighbour will be visited now
v = [Link]( ) //processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
[Link]( w ) //Stores w in Q to further visit its neighbour
mark w as visited.
Example of BFS
Step 1 : Step 2 : Step 3 :
Step 4 Step 5 : Step 6 :
:
Depth First Search(DFS)
Depth first search (DFS) algorithm starts with the
initial node of the graph G, and then goes to deeper
and deeper until we find the goal node or the node
which has no children.
It is an algoirthm for traversing the tree or graph
data structure
Application of DFS – Topological Sorting, Finding the
bridges of a graph, Cycle Detecting
Algorithm
DFS-iterative (G, s): //Where G is graph and s is
source vertex
let S be stack
[Link]( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = [Link]( )
[Link]( )
//Push all the neighbours of v in stack that are
not visited
for all neighbours w of v in Graph G :
if w is not visited :
[Link]( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)
Example of DFS
Step 1 : Undirected graph with 5 vertices
Step 2 : Visit the element and put it in the visited list
Step 3 : Visit the element at the top of stack
Step 4 : Vertex 2 has an unvisited adjacent vertex in 4, so we
add that to the top of the stack and visit it.
Step 5 : Vertex 2 has an unvisited adjacent vertex in 4, so
we add that to the top of the stack and visit it.
Step 6 : After we visit the last element 3, it doesn't have any
unvisited adjacent nodes, so we have completed the Depth
First Traversal of the graph
Topological Sorting
Topological sorting for Directed Acyclic Graph
(DAG) is a linear ordering of vertices such that
for every directed edge u v, vertex u comes
before v in the ordering.
It is an application of Breadth First Search.
Application of Graph
Amazon use graphs to make suggestions for
future shopping
Graph is use in solving Travelling Salesman
Problem(TSP) Branch and Bound algorithms.
Social networks use graph for finding friends,
etc.
Solving Traffic Control Problems