Discrete Mathematics

196

DISCRETE

MATHEMATICS·--------------------------

In general, topological sort

is

one

of

the most powerful tools available for dealing with directed acyclic

graphs.

6.4

SIMPLE GRAPH PROPAGATION ALGORITHM

Some graph problems can be solved by a simple propagation procedure. For example, consider the problem

of

determining all the vertices in a graph reachable from a given subset

of

the vertices. Intuitively, we can

address this by associating a Boolean variable

or

mark, with each vertex in the graph and executing the

following procedure:

1.

Mark each vertex in the graph false;

2.

For

each vertex in the initial set, mark it true and add it