Đề tài Data Structures and Algorithm

ck:A
D E F G H I
B C
J
A
Stack:CA
D E F G H I
B C
J
A
Stack:BCA
DSA CMT502 340
D E F G H I
B C
J
A
Stack:IBCA
D E F G H I
B C
J
A
Stack:HIBCA
D E F G H I
B C
J
A
Stack:GHIBCA
D E F G H I
B C
J
A
Stack:FGHIBCA
InsertVertex(),
DSA CMT502 341
D E F G H I
B C
J
A
Stack:JFGHIBCA
D E F G H I
B C
J
A
Stack:EJFGHIBCA
D E F G H I
B C
J
A
Stack:DEJFGHIBCA
DSA CMT502 342
12.3.4 Finding a Path
z12.3.4.1 The shortest path in an 
unweighted graph
A B C D
E F G H
I J K L
M N O P
AÆEÆIÆMÆNÆK
AÆFÆJÆK
AÆFÆK
AÆBÆFÆK
AÆBÆCÆGÆK
DSA CMT502 343
12.3.4.1 The shortest path in an 
unweighted graph
{Enhance breadth-first traversal to solve the 
problem
A B C D
E F G H
I J K L
M N O P
0
1
2
A A
A
E F F
B
DSA CMT502 344
algorithm for getting shortest path in an unweighted graph
Input: graph G, vertices originVertex, endVertex
Output: a stack S for the resulting traversal order
getShortestPath(G, originVertex, endVertex){
done = false
initiate a queue Q to hold neighbours
mark originVertex as visited
Q.enqueue(oringinVertex)
while(!done && !Q.isEmpty()){
frontVertex=Q.dequeue();
while(!done && frontVertex has unvisited neighbours){
nextNeighbour = next unvisited neighbour of frontVertex
mark nextNeighbour as visited
set the predecessor of nextNeighbour to frontVertex
Q.enqueue(nextNeighbour)
if(nextNeighbour==endVertex) done=true
}
}
DSA CMT502 345
S = a new stack of vertices
S.push(endVertex)
while(endVertex has a prodecessor){
endVertex = prodecessor of endVertex
S.push(endVertex)
}
return S
}
DSA CMT502 346
12.3.4.2 The shortest path in a weighted 
graph
zThe shortest path in a weighted graph is 
not necessarily the one with the fewest 
edges, but the one with the smallest edge-
weight sum.
A B C D
E F G H
I J K L
M N O P
path weight
AÆEÆIÆMÆNÆK 8
AÆFÆJÆK 11
AÆFÆK 10
AÆBÆFÆK 7
AÆBÆCÆGÆK 6
1
2
1
6
4
2 3
23
1 2
2 1 2 5
6
8
3
42
DSA CMT502 347
12.3.4.2 The shortest path in a weighted 
graph
zDeveloping the algorithm:
{based on a breadth-first traversal
{uses a priority queue.
zEach entry in the priority queue is an object that 
contains
• A vertex
• The cost of the path to that vertex from the origin vertex
• The previous vertex on that path
zThe queue uses the cost of the path as priority. The 
less cost has higher priority. 
DSA CMT502 348
1
2
1
6
4
2
3
2
3
1 2
2 1 2 5
6
8
3
42
A 0
E 1 A
I 3 E
M 4 I
B 1 A
F 6 A
J
N 7 M
C 3 B
G 4 C
K 6 G
O
D
H
L
P
DSA CMT502 349
algorithm for getting shortest path in a weighted graph
Input: graph G, vertices originVertex, endVertex
output: a stack S for the resulting traversal order
getShortestPath(G, originVertex, endVertex){
initiate a priority queue Q
set originVertex as visited
Q.enqueue(new pathEntry(originVertex, 0, null))
while(Q.isEmpty()){
frontEntry = Q.dequeue()
frontVertex = vertex in frontEntry
if(frontVertex equals endVertex) break
while(frontVertex has an unvisited neighbour){
nextNeighbour = next unvisited neighbour of frontVertex
set the cost of path to nextNeighbour as 
(weight of edge between frontVertex and 
nextNeighbour + cost of path to frontVertex)
set the processor of nextNeighbour as frontVertex
set nextNeighbour as visited
add nextNeighbour to Q
}
}
DSA CMT502 350
S = a new stack of vertices
S.push(endVertex)
while(endVertex has a prodecessor){
endVertex = prodecessor of endVertex
S.push(endVertex)
}
return S
}
DSA CMT502 351
Chapter 13 Greedy Algorithms
z13.1 Coin changing
z13.2 Kruskal algorithm
z13.3 Prim’s algorithm
z13.4 Dijkstra’s algorithm
DSA CMT502 352
Chapter 13 Greedy Algorithms
zA greedy algorithm builds a solution to a 
problem in steps. In each step, it adds a 
part of the solution which is the best 
available based on a greedy rule.
DSA CMT502 353
13.1 Coin Changing Problem
zSuppose we want to make change for an 
amount A using the fewest number of 
coins. Suppose further that the available 
denominations are 1, 5 and 10.
zOne of the greedy rules: select the largest 
denomination available. 
DSA CMT502 354
13.1 Coin Changing Problem
zExample: A=18.
{
510 1 1 1
DSA CMT502 355
13.1 Coin Changing Problem
z Greedy coin changing algorithm: this algorithm makes change for an 
amount A using coins of denominations
denom[1]>denom[2]>>denom[n]=1
Input: amount A, denom
Output: A queue storing the selections in order 
Greedy-coin-changing(A, denom){
i=1;
Initiate a queue Q
while(A>0){
c=A/denom[i]
if(c>0){
for(j=0; j<c; j++) Q.enqueue(denom[i])
A = A-c*denom[i]
i++;
}
}
return Q
}
DSA CMT502 356
13.1 Coin Changing Problem
zRunning time analysis
{The running time for the greedy coin changing 
algorithm is O(n), where n is the number of the 
denominations of coins.
DSA CMT502 357
13.2 Kruskal Algorithm
z A problem: The following graph shows six cities A, B, C, 
D, E and F and the costs (in hundreds of thousands of 
pounds) of rebuilding roads between them. We need to 
find out the cheapest way to rebuild enough roads so 
that each pair of cities will be connected. That is, to find 
a spanning tree with minimum weight (minimal 
spanning tree).
A
E
B
C
D
F
2 4
3
3
2
6
6
5
1
DSA CMT502 358
13.2 Kruskal Algorithm
zKruskal algorithm is a greedy algorithm for 
finding a minimal spanning tree in a 
connected weighted graph G.
{It begins with all the vertices of G and no 
edges.
{It then applies the greedy rule: Add an edge of 
minimum weight that does not make a cycle.
DSA CMT502 359
A
E
B
C
D
F
2
4
3
3
2
6 6
5
1
A
E
B
C
D
F
2
4
3
3
2
6 6
5
1
A
E
B
C
D
F
2
4
3
3
2
6 6
5
1
A
E
B
C
D
F
2
4
3
3
2
6 6
5
1
(a) (b)
(c) (d)
DSA CMT502 360
A
E
B
C
D
F
2
4
3
3
2
6 6
5
1
(e)
The cost of this spanning tree is 12.
DSA CMT502 361
13.2 Kruskal Algorithm
z Implementing the Kruskal Algorithm
{Represents graph as a list of edges and their 
weights.
{Sorts the edges in non-decreasing order by 
weight and examines them in sorted order.
{Determines whether adding an edge would 
create a cycle.
DSA CMT502 362
13.2 Kruskal Algorithm
z Example: Find the minimal spanning tree in the 
following graph.
The representation of the graph is:
(1,2,4)(1,3,2)(1,5,3)(2,4,5)(3,4,1)(3,5,6)(3,6,3)(4,6,6)(5,6,2)
Where (a, b, w) is interpreted as edge (a, b) of weight w.
1
5
2
4
6
3
2 4
3
3
2
6
6
5
1
DSA CMT502 363
13.2 Kruskal Algorithm
First of all, we sort the edges in non-descendent order by weight
(3,4,1)(1,3,2)(5,6,2)(1,5,3)(3,6,3)(1,2,4)(2,4,5)(3,5,6)(4,6,6)
When the Kruskal algorithm starts, no edges have been selected, 
so we put all the vertices into different sets
{1} {2} {3} {4} {5} {6}
The first edge (3,4) is selected, and the sets to which vertices 3 and 
4 belong are merged:
{1} {2} {3,4} {5} {6}
Next edge (1,3) is selected, and the sets to which vertices 1 and 3 
belong are merged:
{1,3,4} {2} {5} {6}
DSA CMT502 364
13.2 Kruskal Algorithm
Next edge (5,6) is selected, and the sets to which vertices 5 and 6 
belong are merged:
{1,3,4} {2} {5,6}
Next edge (1,5) is selected, and the sets to which vertices 1 and 5 
belong are merged:
{1,3,4, 5,6} {2}
Next edge (3,6) is examined and rejected, because its vertices 3
and 6 belongs to the same set.
Finally edge (1,2) is selected, and the sets to which vertices 1 and 
2 belong are merged:
{1,3,4, 5,6, 2}
DSA CMT502 365
The algorithm
Input: edgelist, n
//edgelist is an array of edges. The members of edge are its end vertices 
and its weight. N is the number of vertices.
Output:
Kruskal(edgelist, n){
sort edgelist in a non-descendent order
make a set for each vertex
i=0
count =n
while( count>1){
(a, b) = the edge represented in edgelist[i]
if (vertices a and b are in different sets){
println (“(”+a+”, “+b+”)”)
merge the two sets
count - -
}
i++
}
}
DSA CMT502 366
13.3 Prim’s Algorithm
zPrim’s algorithm is another greedy 
algorithm for finding a minimal spanning 
tree in a connected weighted graph G.
{It begins with a start vertex and no edges.
{It then applies the greedy rule: Add an edge of 
minimum weight that has one vertex in the 
current tree and the other not in the current 
tree.
DSA CMT502 367
1
5
2
4
6
3
2
4
3
3
2
6 6
5
1
(a)
1
5
2
4
6
3
2 4
3
3
2
6
6
5
1
Find the minimum spanning tree
Starting vertex
1 2
4
6
3
2
4
3
3
2
6 6
5
1
(b)
5
DSA CMT502 368
1 2
4
6
3
2
4
3
3
2
6 6
5
1
(c)
5
1 2
4
6
3
2
4
3
3
2
6 6
5
1
(d)
5
1 2
4
6
3
2
4
3
3
2
6 6
5
1
(e)
5
DSA CMT502 369
13.4 Dijkstra’s Algorithm
zDijkstra’s algorithm is a greedy algorithm 
that finds the shortest paths from a 
designed vertex s to all other vertices in 
non-decreasing order of length.
{The first path found is from s to s of length 0.
{It then applies the greedy rule: Among all of the 
vertices that can extend a shortest path already 
found by one edge, choose the one that results 
in the shortest path.
DSA CMT502 370
13.4 Dijkstra’s Algorithm
zExample: finds the shortest paths from 
vertex 5 to all other vertices in non-
decreasing order.
1 2
3 4
5 6
80
60
40 100
20
40
120 12060
DSA CMT502 371
1 2
3 4
5 6
80
60
40 100
20
40
120 12060
05
Path lengthShortest path
1 2
3 4
80
60
40 100
20
40
120 12060
05
405Æ6
Path lengthShortest path
5 6
DSA CMT502 372
1 2
3 4
80
60
40 100
20
40
120 12060
405Æ6
05
605Æ1
Path lengthShortest path
5 6
1 2
3 4
80
60
40 100
20
40
120 12060 605Æ1
405Æ6
05
1005Æ6Æ3
Path lengthShortest path
5 6
DSA CMT502 373
1005Æ6Æ3
605Æ1
405Æ6
05
1205Æ6Æ3Æ4
Path lengthShortest path1 2
3 4
80
60
40 100
20
40
120 12060
5 6
1205Æ6Æ3Æ4
1005Æ6Æ3
605Æ1
405Æ6
05
1405Æ1Æ
Path lengthShortest path1 2
3 4
80
60
40 100
20
40
120 12060
5 6