Graph in Data Structure
Introduction
Graph is a collection of
nodes (vertices) and edges. Edge is a pair of vertices, if u and v are two
vertices of a Graph, G, and u is adjacent to v, then uv is an edge (e) of G, e
= (u,v). Graphs can be used to represent cities and highways connecting to
them, circuit board, and many more things.
A path in a graph is a
sequence of distinct vertices adjacent to next.
A cycle is a path
containing at least three vertices, the last vertex is adjacent to the first.
Graph
Representation
•                Â
The
set representation: Two sets are used: one to represent
vertices, another to represent edges.
•                Â
Adjacency
Table: Two dimensional boolean array can be used to represent
graph. The vertices are represented by the index of array, starting from 0 to
n-1, where n is the number of vertices of the graph. Boolean graph [n][n];
g[u][v] = true --> u is adjacent to v; u and v are array indices
representing vertices of graph
•                Â
Adjacency
List: List containing distinct vertices and another list to
show adajcent vertices for each vertex.
Topological
Sort
Topological sorting is
arrangement of vertices of the directed graph with no directed circle in such a
way that if there is an edge from vertex u to vertex v then u precedes v in the
sequential listing. Topological sorting can be used to represent jobs which can
be done in sequence only; one job can't be started without completing jobs
before it.
Cycle Detection in a
Undirected Graph
• cycleDetectionDFS(a)
• num(a) = j++;//assign a unique number to a
• for all vertices b adjacent to a
•     if num(a) == 0 then
•       add edge ab to list edges;
•       cycleDetectionDFS(b);
•     else
•       cycleDetected
Minimum Spanning Tree
Suppose graph, G,
represents roads connections between five cities. For some reasons, as many of
road connections have to be closed but still able to reach from one city to
other cities. To solve this problem, we have to create a tree with minimum
number of road connections. We have to create a spanning tree.
Minimum Spanning Tree is
a spanning tree with all the nodes of graphs connected somehow and in which the
weights of the edges is minimal.
Kruskal's
Algorithm for Minimum Spanning Tree
• All the edges of the graph are ordered by
weight
• for each edge arranged in the ordered
sequence
•      if (adding of that edge to the tree
under construction form cycle == false) then
•        the edge is added to the tree
•     otherwise discard that edge.