1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
// FILE: searches.template
// TEMPLATE FUNCTIONS IMPLEMENTED: rec_dfs, depth_first, and breadth_first.
// Please see searches.h for documentation of these functions.
// This file is included at the bottom of searches.h, and should not be
// separately compiled.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <queue>
#include <set>
#include "graph.h"
namespace main_savitch_15
{
template <class Process, class Item, class SizeType>
void rec_dfs(Process f, graph<Item>& g, SizeType v, bool marked[])
// Precondition: g is a labeled graph that is being traversed by a
// depth-first search. For each vertex x, marked[x] is true if x has
// already been visited by this search, otherwise marked[x] is false.
// The vertex v is an unmakred vertex that the search has just arrived at.
// Postcondition: the depth-first search of g has been continued
// through vertex v and beyond to all the vertices that can be reached
// from v via a path of unmarked vertices. The function f has been
// applied to the labe of each vertex visited by the search, and each
// such vertex x has also been marked by setting marked[x] to true.
// Library facilities used: cstdlib, graph.h, set
{
std::set<std::size_t> connections = g.neighbors(v);
std::set<std::size_t>::iterator it;
marked[v] = true; // Mark vertex v
f(g[v]); // Process the label of vertex v with the function f
// Traverse all the neighbors, looking for unmarked vertices:
for (it = connections.begin( ); it != connections.end( ); ++it)
{
if (!marked[*it])
rec_dfs(f, g, *it, marked);
}
}
template <class Process, class Item, class SizeType>
void depth_first(Process f, graph<Item>& g, SizeType start)
// Precondion: start is a vertex number of the labeled graph g.
// Postcondition: A depth-first search of g has been executed,
// starting at the start vertex. The function f has been applied to the
// label of each vertex visited by the search.
// Library facilities used: algorithm, cassert, graph.h
{
bool marked[g.MAXIMUM];
assert(start < g.size( ));
std::fill_n(marked, g.size( ), false);
rec_dfs(f, g, start, marked);
}
template <class Process, class Item, class SizeType>
void breadth_first(Process f, graph<Item>& g, SizeType start)
// Precondition: start is a vertex number of the labeled graph g.
// Postcondition: A breadth-first search of g has been executed,
// starting at the start vertex. The function f has been applied to the
// label of each vertex visited by the search.
// Library facilities used: algorithm, cassert, cstdlib, graph.h, queue
{
bool marked[g.MAXIMUM];
std::set<std::size_t> connections;
std::set<std::size_t>::iterator it;
std::queue<std::size_t> vertex_queue;
assert(start < g.size( ));
std::fill_n(marked, g.size( ), false);
marked[start] = true;
f(g[start]);
vertex_queue.push(start);
do
{
connections = g.neighbors(vertex_queue.front( ));
vertex_queue.pop( );
// Mark and process the unmarked neighbors,
// and place them in the queue.
for (it = connections.begin( ); it != connections.end( ); ++it)
{
if (!marked[*it])
{
marked[*it] = true;
f(g[*it]);
vertex_queue.push(*it);
}
}
}
while (!vertex_queue.empty( ));
}
}
|