Data Structure Unit-5 |
|||
|
Lectuer-1 |
Lecture-2 |
Lecture-3 Traversing
of Graphs-1
|
Lecture-4 Traversing
of Graphs-2
|
|
Lecture-5 |
Lecture-6 |
Lecture-7 Dijkstra's Algorithm
|
|
|
UNIT – 5 |
||||||||||||||||
|
Unit-05/Lecture-01 |
||||||||||||||||
|
Introduction
to Graph [RGPV/June 2012(7)] A graph is a Non-Linear Data Structure which consists of set of
nodes called vertices V and set of edges E which links vertices. A graph G = (V, E) consists of a set of objects V = {v1, v2, …} called vertices, and another
set E = {e1, e2, …} whose elements are called edges. Each edge ek in E is identified with an
unordered pair (vi, vj) of vertices.
The vertices vi, vj associated with edge ek are called the end
vertices of ek. The most common
representation of graph is by means of a diagram, in which the vertices are
represented as points and each edge as a line segment joining its end
vertices. Often this diagram itself is
referred to as a graph. Note: A tree is a graph without loops BACK
Graph Tree Fig -5.1.1
Fig -5.1.2 In the above Fig edge e1 having same vertex as both
its end vertices is called a self-loop.
There may be more than one edge associated with a given pair of vertices,
for example e4 and e5 Such edges are referred to as parallel edges. A graph that has neither self-loop nor parallel edges are called
a simple graph, otherwise it is called general graph. It should also be noted that, in drawing a
graph, it is immaterial whether the lines are drawn straight or curved, long
or short: what is important is the
incidence between the edges and vertices. Because of its inherent simplicity, graph theory has a
very wide range of applications in engineering, physical, social, and
biological sciences, linguistics, and in numerous other areas. A graph can be used to represent almost any
physical situation involving discrete objects and a relationship among them. Finite and Infinite Graphs Although in the definition of a graph neither the vertex set V
nor the edge set E need be finite, in most of the theory and almost all
applications these sets are finite. A
graph with a finite number of vertices as well as a finite number of edges is
called a finite graph; otherwise, it is an infinite graph. Incidence and Degree[RGPV/Dec 2013(7)] When a vertex vi
is an end vertex of some edge ej, vi and ej
are said to be incident with (on or to) each other. for example, edges e2,
e6, and e7 are incident with vertex v4. Two nonparallel edges are said to be
adjacent if they are incident on a common vertex. For example, e2 and e7
in are adjacent. Similarly, two
vertices are said to be adjacent if they are the end vertices of the same
edge. v4 and v5 are adjacent, but v1 and v4
are not. The number of edges incident on a vertex vi, with
self-loops counted twice is called the degree, d(vi), of vertex vi.For
example, d(v1) = d(v3) = d(v4) = 3, d(v2)
= 4, and d(v5) = 1. The
degree of a vertex is sometimes also referred to as its valency. Since each edge contributes two degrees,
the sum of the degrees of all vertices in G is twice the number of edges in
G. Fig -5.1.3 Graph containing isolated vertices, series edges and a pendant
vertex. Isolated vertex, Pendent vertex, and Null
graph A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are
vertices with zero degree. Vertex v4
and v7 in Fig. 3-2, for example, are isolated vertices. A vertex of degree one is called a pendent vertex or an end vertex. Vertex v3 in Fig. 3-2 is a
pendant vertex. Two adjacent edges are
said to be in series if their
common vertex is of degree two. In
Fig. 3-2, the two edges incident on v1 are in series.
Fig -5.1.4 Null
graph of six vertices. In the definition of a graph G = (V, E), it is possible for the
edge set E to be empty. Such a graph,
without any edges, is called a null graph.
In other words, every vertex in a null graph is an isolated
vertex. A null graph of six vertices
is shown in Fig. Although the edge set E may be empty, the vertex set V must
not be empty; otherwise, there is no graph.
In other words, by definition, a graph must have at least one vertex. Loop : If
an edge is having identical end points, then the edge is called a loop. Degree/order: A
degree of a node is the number of edges containing that node. The number
edges pointing towards the node are called in-degree/in-order. The number edges pointing away from the
node are called out-degree/out-order. A graph in which the edges are having direction is called directed graph or digraph,
otherwise the graph is called undirected
graph Complete Graph :
A graph is called complete if all the nodes of the graph are adjacent to each
other. A complete graph with n nodes will have n*(n-1)/2 edges. Weighted Graph :
A graph is said to be weighted if each edge in the graph is assigned a
non-negative numerical value called the weight or cost of the edge. If an
edge does not have any weight then the weight is considered as 1. Multigraph : If
a graph has two parallel path to an edge or multiple edges along with a loop
is said to be multigraph.
|
||||||||||||||||
|
|
|
Unit-05/Lecture-02 |
||||||||||||||||||||||
|
Sequential
Representations of Graphs [RGPV/Dec
2012(7)] [RGPV/June 2011(10)] Although a pictorial representation of a graph is very
convenient for a visual study, other representations are better for computer
processing. A matrix is a convenient
and useful way of representing a graph to a computer. Matrices lend themselves easily to mechanical
manipulations. Besides, many known
results of matrix algebra can be readily applied to study the structural
properties of graphs from an algebraic point of view. In many applications of graph theory, such
as in electrical network analysis and operation research, matrices also turn
out to be the natural way of expressing the problem. Incidence Matrix Let G be a graph with n vertices, e edges, and no
self-loops. Define an n by e matrix A
=[aij], whose n rows correspond to the n vertices and the e
columns correspond to the e edges, as follows: The matrix element Aij = 1, if jth
edge ej is incident on ith vertex vi,
and = 0, otherwise.
Fig -5.2.1 a b c d e f g h v1 0 0 0 1 0 1 0 0 v2 0 0 0 0 1 1 1 1 v3 0 0 0 0 0 0 0 1 v4 1 1 1 0 1 0 0 0 v5 0 0 1 1 0 0 1 0 v6 1 1 0 0 0 0 0 0 Graph and its incidence matrix. Such a matrix A is called the vertex-edge incidence
matrix, or simply incidence matrix.
Matrix A for a graph G is sometimes also written as A(G). A graph and its incidence matrix are shown
in Fig. The incidence matrix contains only two elements, 0 and 1. Such a matrix is called a binary matrix or
a (0, 1)-matrix. The following
observations about the incidence matrix A can readily be made: 1.
Since every edge is incident on exactly two vertices, each
column of A has exactly two 1’s. 2.
The number of 1’s in each row equals the degree
of the corresponding vertex. 3.
A row with all 0’s, therefore, represents an
isolated vertex. 4.
Parallel edges in a graph produce identical columns in its
incidence matrix, for example, columns 1 and 2 in above matrix. Adjacency
Matrix [RGPV/Dec 2013(7)] Suppose G is a graph with n nodes and the nodes of G are
being ordered and are called v1,v2,v3,…..,vn
then the adjacency matrix A=(aij) of the graph G is defined as
1
if vi is adjacent to vj aij
= 0,
otherwise The adjacency matrix with 1’s and 0’s is also called bit
matrix.
A= 0 0 1 0 1 0 0 0 0 1 1 0
|
|
Unit-05/Lecture-03 |
||||||||||||||||
|
Traversing of Graphs [RGPV/Dec
2012(7)] [RGPV/June 2012(7)/RGPV/Dec2014] Traversing a graph means visiting all the vertices in a
graph exactly one. It is of two types: (1)Breadth First Traversal (2)Depth First Traversal. Depth First Search [RGPV/June 2011(10)] The general "rule" used in
searching a graph using a depth first search is to search down a path from a
particular source vertex as far as you can go. When you can go to farther,
"backtrack" to the last vertex from which a different path could
have been taken. Continue in this fashion, attempting to go as deep as
possible down each path until each node has been visited. The most difficult part of this
algorithm is keeping track of what nodes have already been visited, so that
the algorithm does not run ad infinitum. We can do this by labeling each
visited node and labeling "discovery" and "back" edges. The algorithm is as follows: DFS(Graph G, vertex v): For
all edges e incident to the start vertex v do: 1)
If e is unexplored a) Let e connect v to w. b)
If w is unexplored, then i)
Label e as a discovery edge ii)
Recursively call DFS(G,w) else iii)
Label e as a back edge To prove that this algorithm visits
all vertices in the connected component of the graph in which it starts, note
the following: Let the vertex u be the first vertex
on any path from the source vertex that is not visited. That means that w,
which is connected to u was visited, but by the algorithm given, it's clear
that if this situation occurs, u must be visited, contradicting the
assumption that u was unvisited. Next, we must show that the algorithm
terminates. If it does not, then there
must exist a "search path" that never ends. But this is impossible.
A search path ends when an already visited vertex is visited again. The
longest path that exists without revisiting a vertex is of length V, the
number of vertices in the graph. The running time of DFS is O(V+E). To
see this, note that each edge and vertex is visited at most twice. In order
to get this efficiency, an adjacency list must be used. (An adjacency matrix
can not be used to complete this algorithm that quickly.)
|
|
Unit-05/Lecture-04 |
|
Breadth First
Search [RGPV/Dec 2011(10)] The idea in a breadth first search is
opposite to a depth first search. Instead of searching down a single path
until you can go no longer, you search all paths at an uniform depth from the
source before moving onto deeper paths. Once again, we'll need to mark both
edges and vertices based on what has been visited. In essence, we only want to explore
one "unit" away from a searched node before we move to a different
node to search from. All in all, we will be adding nodes to the back of a
queue to be ones to searched from in the future. In the implementation on the following
page, a set of queues Li are maintained, each storing a list of
vertices a distance of i edges from the starting vertex. One can implement
this algorithm with a single queue as well. Let Li be the set of
vertices visited that are a path length of i from the source vertex for the
algorithm. BFS(G,s): 1) Let L0 be empty 2) Insert s into L0. 3) Let i = 0 4) While Li is not empty do
the following: A)
Create an empty container Li+1. B)
For each vertex v in Li do i)
For all edges e incident to v a)
if e is unexplored, mark endpoint w. b)
if w is unexplored Mark
it. Insert
w into Li+1. Label
e as a discovery edge. else Label
e as a cross edge. C)
i = i+1 The basic idea here is that we have
successive rounds and continue with our rounds until no new vertices are
visited on a round. For each round, we look at each vertex connected to the
vertex we came from. And from this vertex we look at all possible connected
vertices. This leaves no vertex unvisited
because we continue to look for vertices until no new ones of a particular
length are found. If there are no
paths of length 10 to a new vertex, surely there can be no paths of length 11
to a new vertex. The algorithm also terminates since no path can be longer
than the number of vertices in the graph. |
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Write down the BFS and DFS algorithm |
Dec 2011 |
10 |
|
Q.2 |
Differentiate between DFS and BFS. |
Dec 2014 |
7 |
|
Unit-05/Lecture-05 |
|
Spanning tree [RGPV/Dec 2012(7)] [RGPV/Dec 2011(10)] A sub tree of a graph that includes each vertex of the
graph. A sub tree of a given graph as a subset of the components of
that given graph. (Naturally, these components must form a graph as well.
Thus, if your sub
graph can't just have
vertices A and B, but contain an edge connecting vertices B and C.)
All Possible Spanning Trees for Three Points
Fig -5.5.1 All
Possible Spanning Tree for Four Points Minimum spanning tree This is
only defined for weighted graphs. This is the spanning tree of a given graph
whose sum of edge weights is minimum, compared to all other spanning trees. Properties of Spanning tree G be a graph with
vertices in the set V partitioned into two sets V1 and V2.
Then the minimum weight edge, e, that
connects a vertex from V1 to V2 is part of a minimum
spanning tree of G. There is an efficient algorithm to solve this
minimal spanning tree problem. (1)Prim's Algorithm (2) Kruskal’s Algorithm Prim's Algorithm to Construct a Minimal Spanning
Tree [RGPV/Dec 2013(7)] [RGPV/June
2011(10)] Input: A weighted, connected and undirected graph G = (V,E). Output: A minimal spanning tree of G. Step 1: Let x be any vertex in V. Let X = Step 2: Select an edge (u,v) from E such that Step 3: Connect u to v. Let Step 4: If Y is empty, terminate and the resulting
tree is a minimal spanning tree. Otherwise, go to Step 2. Let us consider the graph in Figure 2.7. he process
of applying Prim's algorithm to this graph is now illustrated in Figure 2.8.
Fig -5.5.2 : A General Graph
Fig -5.5.3 : The Process of Applying Prim’s Algorithm to the
Graph in Figure 2.7 We will not formally prove the correctness of Prim's
algorithm. The reader can find the proof in almost every textbook on
algorithms. Yet, now we can easily see the importance of algorithms. If one
does not know the existence of such an efficient algorithm to construct
minimal spanning trees, one can never construct minimal spanning trees if the
input size is large. It would be disastrous for any one to use an exhaustive
search method in this case. |
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Using the Prim’s algorithm,find the minimum spanning tree of the
given graph |
Dec 2013 June 2011 |
7 10 |
|
Q.2 |
Explain minimum cost spanning tree |
Dec 2012 June 2011 |
7 10 |
|
UNIT-05/LECTURE-06 |
||||||||
|
Kruskal's Algorithm [RGPV/June 2012(7)] [RGPV/Dec 2011(10)/RGPV/June 2014] Kruskal's algorithm to construct a minimal spanning
tree is quite similar to Prim's algorithm. It would first sort all of the
edges in the graph into an ascending sequence. Then edges are added into a partially
constructed minimal spanning tree one by one. Each time an edge is added, we
check whether a cycle is formed. If a cycle is formed, we discard this edge.
The algorithm is terminated if the tree contains n-1 edges. Kruskal's Algorithm to
Construct a Minimal Spanning Tree Input: A weighted, connected and undirected graph G
= (V,E). Output: A minimal spanning tree of G. Step 1: Step 2: while T contains less
than n-1edges do Choose an edge (v,w)
from E of the smallest weight. Delete (v,w) from E. If the adding of
(v,w)does not create cycle in T then Add (v,w) to T. Else Discard (v,w). end while
Fig -5.6.1
Fig -5.6.2 The Process of Applying Kruskal’s Algorithm to the Graph
|
|
UNIT-05/LECTURE -07 |
||||||||
Dijkstra's Algorithm
|
||||||||
|
Dijkstra’s Algorithm [RGPV/Dec 2011(10)] Suppose
you have five towns surrounding you.
You determine the amount of time it takes between certain cities on
connecting one-way roads. You would
like to determine the shortest path from your town to each of the other
cities. You do not need to visit every
city, but you will have a path specified for every destination. On worksheet A, have the students find the
minimum time to travel from your town A, to each of the remaining five
towns. There should be five answers to
this problem. One for A to B, one for
A to C, etc… This network is a
directed graph and you can only travel in the direction of the arrows. After
students determine their best answers for the shortest path, introduce
Dijkstra’s algorithm, below. Practice
on the network which follows. To make
this problem easier, there are several things to keep in mind. First, there will be two things recorded at
each node – the node prior to it on the path and the total sum from the
origination up to that node. Also,
there will be two types of nodes.
Nodes will change from having a temporary label to a permanent
label. The algorithm is complete when
all nodes become permanent. The
algorithm will complete one fewer iterations than the number of nodes in the
network. Only one node is changed to
permanent on each iteration. Also,
during each iteration, the node that most recently became permanent will be
noted with a star. All permanent nodes
will be shown as bolded. At
the node, there will be two things recorded.
If node E is labeled with (15,C), then that will mean the total from
the origination to E is 15 and it came to E from C. Dijkstra’s Algorithm Initial
Step: Label
the Origination node (0,-) and make this node permanent. Put the star by this node. Reiterative
Steps: 1)
Locate all nodes that are directly connected to the most recent permanent
labeled node. At each label, add the
weight of the arc taken to the previous total at the star node. If this total is smaller than a previous
label on this node, replace it with this new label and also record the name
of the node which it came from (the one with the star). 2)
Of all of the temporary nodes, choose the node with the smallest total. Change only this node to be permanent and
move the star to this node. 3)
Repeat the iterative steps until all nodes have been labeled as permanent. In
order to interpret the graph, choose any destination. At that node, the amount of the shortest
path is the number recorded. To find
the actual path backtrack from that node to the node labeled in the
parenthesis. Keep backtracking until
the origination node is reached. To
begin, you will first need to create a table, like Table 10-2(a) (below),
with a column for each node in the network except the starting node, Node A.
The table also needs to include a column called “Visited,” in which you will
list each node that has been visited. More precisely, when you list a node in
this column, it indicates that you have gone to that node and examined all of
the node’s immediate neighbors. In addition, the table should include a final
row called “Next” to denote the next node (but only the next node) that the
packet should traverse after it leaves Node A. For example, if the Next value
under column Node G is B, then a packet that is leaving Node A and is
destined for Node G should next be transmitted to Node B. As you work through
this example, you should keep in mind that the way this algorithm works is
that this table, once it’s complete (see Table 10-2(h) at the end of this
section), shows only the very next hop that should be made from Node A to
each of the other nodes. With respect to the example, this means that once
you got to Node B (on your way to Node G), you would have to consult a
different table—namely, the Dijkstra table for Node B—for the next hop. Visited Node - B C D E F G Next Table 10-2(a)
Initial table for Dijkstra’s algorithm After
you’ve created the table, select the starting node, Node A, visit it, and add
the starting node to the Visited list, as shown in Table 10-2(b). After that,
locate each immediate neighbor (a node only one link or hop away) of Node A
that is not yet in the Visited list. Calculate the cost to travel from Node A
to each of these neighbors, and enter these values into the table. For
example, Node B is one hop away from Node A, it has not yet been visited, and
it costs 2 units to travel from A to B. In this case, you should enter 2 in
the column for Node B in Table 10-2(b) to indicate the cost of the path from
Node A to Node B, and enter B in the Next row to note that to get to B, you
go directly to B on the next hop. You can also go from A to C in one hop with
a cost of 4 and a Next value of C, and from A to D with a cost of 5 and a
Next value of D. These values are also recorded in Table 10-2(b). Note that
we have not yet “visited” B, C, or D. We have only visited A, and we are
simply examining the costs of the links that run between A and B, A and C,
and A and D. Visited Node B C D E F G A 2 4 5 - - - Next B C D Table
10-2(b)
Table for Dijkstra’s algorithm after visiting Node A No more
nodes are immediate neighbors of A, and all of Node A’s immediate neighbor
links have been examined, so you need to select the next node to visit.
According to the algorithm, the next node to visit must be the one that has
the least cost in our table thus far. Therefore, you must choose Node B. By
specifying that you select the next node with the least cost, the algorithm
will find the least cost in all situations. Locate the immediate neighbors of
Node B that have not yet been visited (so far only A has been visited), and
determine the cost of traveling from Node A to each immediate neighbor of B
via Node B. Note that Node A has been visited, so you should exclude it from
being considered at this stage (no sense in going backwards). The immediate
neighbors of Node B that have not yet been visited are D, E, and G. The cost
of going from Node A to Node D via node B is 4 (the link from A to B costs 2,
and the link from B to D costs 2). Since this cost is less than the cost of
going directly from A to D (which, as can be seen in Table 10-2(b), is 5),
replace the value 5 with the new value 4, to update the table. This update is
highlighted in Table 10-2(c). You should also replace the D in the Next row
under column D with a B, since the new least-cost path from Node A to Node D
now begins with the packet going to Node B first after leaving Node A. Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 - - - Next B C B Table
10-2(c) Table for Dijkstra’s algorithm after visiting Nodes A and B The
cost of going from A to E via B is 6 (2 + 4), and the cost of going from A to
G via B is 9 (2 + 7). Enter the values 6 and 9 in the E and G columns,
respectively, as shown in Table 10-2(d). B is also the Next value for both E
and G. Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 6 - 9 Next B C B B B Table
10-2(d) Table for Dijkstra’s algorithm
after visiting Nodes A and B, continued Let’s visit Node C next since, as you can see in Table
10-2(d), it has the next smallest cost. The immediate neighbors of C that
have not yet been visited are F and G. The cost of going from A to F via C is
7 (4 + 3). Enter the value 7 in the F column and the value C in the Next row,
as shown in Table 10-2(e). The cost of traveling from Node A to G via C is 9
(4 + 5). Since this new value, 9, is not less than the current value (also 9)
in Table 10-2(d), there is no need to update the table in this case. Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 6 - 9 A
B C 2 4 4 6 7 9 Next B C B B C B Table
10-2(e) Table for Dijkstra’s algorithm after visiting Nodes A, B, and Let’s visit
Node D next, since it has the next smallest cost. The immediate neighbors of
D that have not yet been visited are E, F, and G. The cost of going from A to
E via D (via B) is 5 (4 + 1). Since this value is less than the current cost
from A to E (less than 6), update the table by entering 5 in the E column
(see Table 10-2(f) for reference). We still get to E by first going to B
after leaving A, so the value B in the Next row does not change. The cost of
going from A to F via D is 10 (5 + 5). The cost of going from A to G via D is
also 10. Because the values already entered in the F and G columns are less
than 10 (in other words, the table already reflects the least-cost path for
those nodes), you do not update the table. Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 6 - 9 A
B C 2 4 4 6 7 9 A
B C D 2 4 4 5 7 9 Next B C B B C B Table
10-2(f) Table for Dijkstra’s algorithm
after visiting Nodes A, B, C, and D The next node to visit is E. The immediate neighbor of
E that has not yet been visited is G. The cost of traveling from Node A to
Node G via Node E (via D via B) is 7 (2 + 2 + 1 + 2). The cost of this path,
7, is smaller than the value already entered in Column G, so you should
replace the current value in the table with this new, smaller value, as is
shown in Table 10-2(g). Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 6 - 9 A
B C 2 4 4 6 7 9 A
B C D 2 4 4 5 7 9 A
B C D E 2 4 4 5 7 7 Next B C B B C B Table
10-2(g) Table for Dijkstra’s algorithm after visiting Nodes A, B, C, D, and E The
next node to visit is F. The only immediate neighbor of F that has not yet
been visited is G. The cost of traveling from Node A to Node G via F (via C)
is 8. This cost is not less than the current value for F, so do not update the
table. The
final node to visit is G. There are, however, no immediate neighbors of G
that have not already been visited, so we are finished. Table
10-2(h) shows the final results. From this table, you can now easily look up
the least-cost path from Node A to any other node. If a data packet
originates from Node A and is destined for Node x, the software in the router
will simply consult Column x of the table to determine where the data packet
should go Next. To find the least-cost route starting from another node, you
would need to apply Dijkstra’s algorithm again. For example, if you wished to
find the least-cost path from, say, Node C to any other node, you would
generate a new table by repeating the least-cost algorithm with Node C as the
starting position. Visited Node B C D E F G A 2 4 5 - - - A
B 2 4 4 6 - 9 A
B C 2 4 4 6 7 9 A
B C D 2 4 4 5 7 9 A
B C D E 2 4 4 5 7 7 A
B C D E F 2 4 4 5 7 7 A
B C D E F G 2 4 4 5 7 7 Next B C B B C B Table
10-2(h) The results of Dijkstra’s algorithm applied to a seven-node
sub-network starting from Node A
|
|
|||||||||||||||