Transcript V 0 V 6 V 5 V 3 V 4 V 1 V 2

CS2420: Lecture 37
Vladimir Kulyukin
Computer Science Department
Utah State University
Outline
• Graph Algorithms (Chapter 9)
Finding Prime Numbers
• The simplest way of finding the next prime
size of your hash table is to double the
current size (TableSize) and start testing
the numbers from 2TableSize on for being
prime.
• A integer n is prime if there is no integer
b/w 1 and n/2 + 1 that divides n.
Finding Prime Numbers
• The Sieve of Eratosthenes is another
commonly used algorithm for finding prime
numbers in a specific range.
• The algorithm is reasonably efficient but
requires to allocate an array from 1 to n,
where n is the upper bound of the range in
which you are looking for primes.
Sieve of Eratosthenes
• Here is a Wiki link that explains the history
and gives a pseudocode:
– http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• Here is a link to a C source (I am sure
there are many more out there):
– http://www.insidereality.net/site/content/computer_science/eratosthenes_c++.php
Shortest-Path Algorithms
Let G = (V, E) be an unweighted or
weighted graph. Let s be a vertex of G.
Find the shortest paths from s to every
other vertex in G.
This problem is sometimes referred to as
the single source shortest paths problem.
Two Solutions
• Breadth-First Search for Unweighted
Graphs.
• Dijkstra’s Algorithm for Positive-Weighted
Graphs.
Breadth First Search (BFS):
Unweighted Shortest Paths
• Every vertex W in G has a distance variable
associated with it (W.Dist). This is the number of
edges that it took the search to reach W. Initially,
W.Dist = INF (some big number).
• Every vertex W in G also has a pointer to the
vertex it was reached from (W.Prev).
• S is the start vertex.
• Q is a queue of vertices which is initially empty.
• The input to BFS is the start vertex S and the
graph G (adjacency lists).
BFS: Pseudocode
BFS(S, G) {
Initialize Q;
S.Dist  0; S.Prev  NULL;
Q.Push(S);
While ( Q is not empty ) {
V  Q.Pop();
For each verte x W adjacent t o V {
if ( W.Dist  INF ) {
W.Dist  V.Dist  1;
W.Prev  V;
Q.Push(W);
} // end if
} // end for
} // end while
} // end BFS
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V2, 0, NULL>};
The notation <V2, 0, NULL> means that V2 is a vertex such that
V2.Dist = 0 and V2.Prev = NULL;
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V0,1,V2>, <V5,1,V2};
When the vertex is colored yellow, it
means it has been popped off the
QUEUE.
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V5,1,V2>, <V1,2,V0>, <V3,2,V0>};
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V1,2,V0>, <V3,2,V0>};
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V3,2,V0>, <V4,3,V1>};
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V4,3,V1>,<V6,3,V3>};
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {<V6,3,V3>};
BFS: Example
V0
V2
V1
V3
V5
V4
V6
QUEUE = {};
BFS: Example
• Notice the order in which the vertices are
visited:
– <V2, 0, NULL>;
– <V0, 1, V2>,
– <V5, 1, V2>,
– <V1, 2, V0>,
– <V3, 2, V0>,
– <V4, 3, V1>
– <V6, 3, V3>;
BFS: Vertex Visitation Tree
V2
V0
V5
V1
V3
V4
V6
BFS forms a vertex visitation
tree whose root is the start
vertex. We can use the tree
to find the path from the start
vertex to every vertex reachable
from the start vertex.