Page 296 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

(3) v 0 v 1 Notes
2
0 1 v known d p
5 v v
v 0 T 0 0
1 1 3 v v F 1 v
6 2 1 3
v 2 F 3 v 3
3 v 3 T 1 v 4
1 1 v 4 T 1 v 0
1
v v Q = {v , v }
4
3
1 2
(4) v 0 v 1
2
0 1 v known d p
5 v v
v 0 T 0 0
1 6 1 3 v 2 v 1 T 1 v 3
v 2 F 3 v 3
3 v 3 T 1 v 4
1 1 v 4 T 1 v 0
1
v v Q = {v }
4 3
2
(5) v 0 v 1
2
0 1 v known d p
5 v v
v 0 T 0 0
1 6 1 3 v 2 v 1 F 1 v 3
v 2 F 3 v 3
3 v 3 T 1 v 4
1 1 v 4 T 1 v 0
1
v v Q = { }
4 3

Note v is the source vertex, and d[i] for each vertex i is also indicated in its circle:
0

14.4 Summary

Perhaps the best safeguard in the use of powerful tools is to insist on regularity; that is,

to use the powerful tools only in carefully defined and well-understood ways. Because
of the generality of graphs, it is not always easy to impose this discipline on their use. In
this world, nonetheless, irregularities will always creep in, no matter how hard we try
to avoid them. It is the bane of the systems analyst and programmer to accommodate
these irregularities while trying to maintain the integrity of the underlying system design.
Irregularity even occurs in the very systems that we use as models for the data structures
we devise, models such as the family trees whose terminology we have always used.

14.5 Keywords

Network Flow: Network flow is an advanced branch of graph theory.
Zero-One Principle: If a sorting network sorts every sequence of 0’s and 1’s, then it sorts every
arbitrary sequence of values.

Prim’s algorithm: Prim’s algorithm is an algorithm in graph theory that finds a minimum
spanning tree for a connected weighted graph.

LOVELY PROFESSIONAL UNIVERSITY 291