greph.txt

AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 1
Unit IV: Graphs
1) Graphs – Definition
Graph is a nonlinear data structure; it contains a set of points known as nodes
(or vertices) and set of links known as edges (or Arcs) which connects the vertices.
A graph is defined as follows...
Graph is a collection of vertices and arcs which connects vertices in the graph.
Graph is a collection of nodes and edges which connects nodes in the graph.
Generally, a graph G is represented as
G = ( V , E )
where V is set of vertices and E is set of edges.
The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = ( V , E ),
Where V = {A,B,C,D,E} and
E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.
Graph
2) Graphs –Terminology
We use the following terms in graph data structure...
Vertex: A individual data element of a graph is called as Vertex. Vertex is also
known as node. In above example graph, A, B, C, D & E are known as vertices.
Edge: An edge is a connecting link between two vertices. Edge is also known as
Arc. An edge is represented as (startingVertex, endingVertex).
For example, in above graph, the link between vertices A and B is represented as
(A,B). In above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D),
(B,E), (C,D), (D,E)).
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 2
Edges are three types:
Undirected Edge - An undirected egde is a bidirectional edge. If there is a undirected edge
between vertices A and B then edge (A , B) is equal to edge (B , A).
Directed Edge - A directed egde is a unidirectional edge. If there is a directed edge
between vertices A and B then edge (A , B) is not equal to edge (B , A).
Weighted Edge - A weighted egde is an edge with cost on it.
Types of Graphs:
Undirected Graph: A graph with only undirected edges is said to be undirected
graph.
Directed Graph: A graph with only directed edges is said to be directed graph.
Mixed Graph: A graph with undirected and directed edges is said to be mixed
graph.
End vertices or Endpoints: The two vertices joined by an edge are called the end
vertices (or endpoints) of the edge.
Origin: If an edge is directed, its first endpoint is said to be origin of it.
Destination: If an edge is directed, its first endpoint is said to be origin of it and the
other endpoint is said to be the destination of the edge.
Adjacent: If there is an edge between vertices A and B then both A and B are said
to be adjacent. In other words, Two vertices A and B are said to be adjacent if there
is an edge whose end vertices are A and B.
Incident: An edge is said to be incident on a vertex if the vertex is one of the
endpoints of that edge.
Outgoing Edge: A directed edge is said to be outgoing edge on its orign vertex.
Incoming Edge: A directed edge is said to be incoming edge on its destination vertex.
Degree: Total number of edges connected to a vertex is said to be degree of that vertex.
Indegree: Total number of incoming edges connected to a vertex is said to be
indegree of that vertex.
Outdegree: Total number of outgoing edges connected to a vertex is said to be
outdegree of that vertex.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 3
Parallel edges or Multiple edges: If there are two undirected edges to have the
same end vertices, and for two directed edges to have the same origin and the same
destination. Such edges are called parallel edges or multiple edges.
Self-loop: An edge (undirected or directed) is a self-loop if its two endpoints coincide.
Simple Graph: A graph is said to be simple if there are no parallel and self-loop edges.
Path: A path is a sequence of alternating vertices and edges that starts at a vertex
and ends at a vertex such that each edge is incident to its predecessor and successor
vertex.
3) Graphs – Applications
Graphs can be used to model many types of relations and processes in physical,
biological, social and information systems. Many practical problems can be
represented by graphs.
• In computer science, graphs are used to represent networks of communication,
data organization, computational devices.
• Graph theory is also used to study molecules in chemistry and physics.
• In mathematics, graphs are useful in geometry.
• Weighted graphs, are used to represent structures in which pairwise
connections have some numerical values. Ex: Road Network.
• Graph algorithms are useful for calculating the shortest path in Routing.
• Maps – finding the shortest/cheapest path for a car from one city to another,
by using given roads.
4) Graphs Representation
Graph data structure is represented using following representations...
▪ Adjacency Matrix
▪ Adjacency List
Adjacency Matrix: In this representation, graph can be represented using a matrix
of size total number of vertices by total number of vertices. That means if a graph
with 4 vertices can be represented using a matrix of 4X4 class. In this matrix, rows
and columns both represents vertices. This matrix is filled with either 1 or 0.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 4
Here, 1 represents there is an edge from row vertex to column vertex and 0 represents
there is no edge from row vertex to column vertex.
For example, consider the following undirected graph representation using matrix
Directed graph representation using matrix
Adjacency List: In this representation, every vertex of graph contains list of its
adjacent vertices.
For example, consider the following directed graph representation implemented
using linked list...
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 5
This representation can also be implemented using array as follows..
5) Graph Search methods (Traversal Methods)
Graph traversal is technique used for searching a vertex in a graph. The graph
traversal is also used to decide the order of vertices to be visit in the search process.
A graph traversal finds the edges to be used in the search process without creating
loops that means using graph traversal we visit all vertices of graph without getting
into looping path.
There are two graph traversal techniques and they are as follows...
• DFS (Depth First Search)
• BFS (Breadth First Search)
DFS (Depth First Search): DFS traversal of a graph, produces a spanning tree as
final result. Spanning Tree is a graph without any loops. We use Stack data structure
with maximum size of total number of vertices in the graph to implement DFS
traversal of a graph.
We use the following steps to implement DFS traversal...
Step 1: Define a Stack of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and push it
on to the Stack.
Step 3: Visit any one of the adjacent vertex of the verex which is at top of the stack
which is not visited and push it on to the stack.
Step 4: Repeat step 3 until there are no new vertex to be visit from the vertex on
top of the stack.
Step 5: When there is no new vertex to be visit then use back tracking and pop one
vertex from the stack.
Step 6: Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7: When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 6
Note : Back tracking is coming back to the vertex from which we came to current
vertex.
Example:
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 7
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 8
BFS (Breadth First Search): BFS traversal of a graph, produces a spanning tree as
final result. Spanning Tree is a graph without any loops. We use Queue data structure
with maximum size of total number of vertices in the graph to implement BFS
traversal of a graph.
We use the following steps to implement BFS traversal...
Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it
into the Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at front of the Queue
which is not visited and insert them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at front of the Queue
then delete that vertex from the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final spanning tree by removing
unused edges from the graph.
Example
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 9
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 10
6) Spanning Tree
A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. A disconnected graph does not have any
spanning tree, as it cannot be spanned to all its vertices.
Given an undirected and connected graph G=(V,E), a spanning tree of the graph
G is a tree that spans G(that is, it includes every vertex of G) and is a subgraph of G
(every edge in the tree belongs to G).
By this definition, we can draw a conclusion that every connected and undirected
Graph G has at least one spanning tree. A disconnected graph does not have any
spanning tree, as it cannot be spanned to all its vertices.
For example
We found three spanning trees off one complete graph. A complete undirected graph
can have maximum n n-2 number of spanning trees, where n is the number of nodes.
In the above addressed example, n is 3, hence 3 3−2 = 3 spanning trees are possible.
Properties of Spanning Tree We now understand that one graph can have more than
one spanning tree.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 11
Spanning tree Properties:
• A connected graph G can have more than one spanning tree.
• All possible spanning trees of graph G, have the same number of edges and
vertices.
• The spanning tree does not have any cycle (loops).
• Removing one edge from the spanning tree will make the graph disconnected,
i.e. the spanning tree is minimally connected.
• Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.
7) Minimum Cost Spanning tree
In a weighted graph, a minimum spanning tree is a spanning tree that has
minimum weight than all other spanning trees of the same graph. In real-world
situations, this weight can be measured as distance, congestion, traffic load or any
arbitrary value denoted to the edges.
The cost of the spanning tree is the sum of the weights of all the edges in the tree.
There can be many spanning trees. Minimum spanning tree is the spanning tree
where the cost is minimum among all the spanning trees. There also can be many
minimum spanning trees.
Minimum spanning tree has direct application in the design of networks. It is used
in algorithms approximating the travelling salesman problem, multi-terminal
minimum cut problem and minimum-cost weighted perfect matching. Other
practical applications are: a) Cluster Analysis, b) Handwriting recognition, and
c) Image segmentation.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 12
8) Dijkstra algorithm
Dijkstra algorithm is a single-source shortest path algorithm. Here, single-source
means that only one source is given, and we have to find the shortest path from the
source to all the nodes.
Steps for Dijkstra algorithm:
• Create a set sptSet (shortest path tree set) that keeps track of vertices included
in the shortest-path tree, i.e., whose minimum distance from the source is
calculated and finalized. Initially, this set is empty.
• Assign a distance value to all vertices in the input graph. Initialize all distance
values as INFINITE. Assign the distance value as 0 for the source vertex so
that it is picked first.
• While sptSet doesn’t include all vertices
o Pick a vertex u which is not there in sptSet and has a minimum distance
value.
o Include u to sptSet.
o Then update distance value of all adjacent vertices of u.
▪ To update the distance values, iterate through all adjacent vertices.
▪ For every adjacent vertex v, if the sum of the distance value of u (from
source) and weight of edge u-v, is less than the distance value of v,
then update the distance value of v.
Note: We use a boolean array sptSet[] to represent the set of vertices included in
SPT. If a value sptSet[v] is true, then vertex v is included in SPT, otherwise not.
Array dist[] is used to store the shortest distance values of all vertices.
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 13
Let's understand the working of Dijkstra's algorithm. Consider the below graph.
Start with a weighted graph
Choose a starting vertex and assign infinity path values to all other devices
Go to each vertex and update its path length
AU-AI Data Structures II YEAR – I SEM
DrAA Unit-IV 14
If the path length of the adjacent vertex is lesser than new path length, don't update it
Avoid updating path lengths of already visited vertices
After each iteration, we pick the unvisited vertex with the least path length. So we choose 5
before 7
Notice how the rightmost vertex has its path length updated twice
Repeat until all the vertices have been visited