One of the most basic graph operations is to traverse a graph, finding the nodes accessible by following edges from some starting node. You have already seen this operation in CS2110.

**Graph Traversals**

One of
the most basic graph operations is to traverse a graph, finding the nodes
accessible by following edges from some starting node. You have already seen
this operation in CS2110.

We mark
the vertices as visited when we have visited them to keep track of the parts of
the graph that we have already explored. We start with a single vertex and mark
it as visited. We then consider each outgoing edge. If an edge connects to an
unvisited node, we put that node in a set of nodes to explore. Then we
repeatedly remove a node from the set, mark it as visited, and repeat the
process with that node. If we ever take a node out of the set and it is already
marked as visited, then we ignore it. The order in which we explore the
vertices depends on how we maintain the set of vertices to explore. If we use a
queue, so the unvisited vertices are explored in a first-infirst- out (FIFO)
fashion, then the above traversal process it is known as breadth-first search
(BFS). If we use a stack, so the unvisited vertices are explored in a
last-in-first-out (LIFO) fashion, this is known asdepth-first search (DFS). Of
course, such a traversal will only visit nodes reachable from the start node by
a directed path. Here is an implementation of traversal in a directed graph
using the above abstraction. This implementation makes use of a set of vertices
of type **VSet** to keep track of the
visited vertices. It performs a BFS or DFS depending on whether the **Queue** or **Stack** package is opened. It also can traverse either the edges of
the graph or of the ''reverse'' graph (in which all the edges have been
reversed), based on the parameter

**dir**.**moduleVSet = Set.Make (structtype t = Graph.vertex let compare =
Graph.compareend)**

**open Queue (* use Queue for BFS, Stack for DFS *)
let traverse v0 dir =**

**let disc = create()**

**and visited = ref VSet.emptyin**

**(* Expand the visited set to contain everything v
goes to, * and add newly seen vertices to the stack/queue. *)**

**let expand(v) = lethandle_edge(e) =**

**let (v, v', _) = Graph.edge_info(e) in if not
(VSet.mem v' !visited)**

**then (visited := (VSet.add v' !visited); push v'
disc)**

**else () in**

**List.maphandle_edge (ifdir<0 then
(Graph.incoming_rev v) else (Graph.outgoing v))**

**in**

**(visited := VSet.add v0 !visited; push v0 disc;**

**while (not (is_empty disc))**

**do ignore(expand(pop disc)) done; !visited)**

**Connected Components**

In an
undirected graph, a connected component is the set of nodes that are reachable
by traversal from some node. The connected components of an undirected graph
have the property that all nodes in the component are reachable from all other
nodes in the component. In a directed graph, however, reachable usually means
by a path in which all edges go in the positive direction, i.e. from source to
destination. In directed graphs, a vertex v may be reachable from u but not
vice-versa. For instance, for the graph above, the set of nodes reachable from
any of the nodes 1, 2, or 3 is the set {1, 2, 3, 4}, whereas the set of nodes
reachable from node 4 is just the singleton {4}. The strongly connected
components in a directed graph are defined in terms of the set of nodes that
are mutually accessible from one another. In other words, the strongly
connected component of a node u is the set of all nodes v such that v is
reachable from u by a directed path and u is reachable from v by a directed
path. Equivalently, u and v lie on a directed cycle. One can show that this is
an equivalence relation on nodes, and the strongly connected components are the
equivalence classes. For instance, the graph above has two strongly connected
components, namely {1, 2, 3} and {4}. It is possible to show that the strongly
connected component from a node vi can be found by searching for nodes that are
accessible from vi both in G and in Grev, where Grev has the same set of
vertices as G, and has the reverse of each edge in G. Thus the following simple
algorithm finds the strongly connected components.

**letstrong_component v0 =**

**VSet.inter (traverse v0 1) (traverse v0 (-1))
letstrong_components g =**

**letvs = ref VSet.empty andcs = ref [] in**

**(List.iter (function (v) ->vs :=VSet.add v !vs)
(Graph.vertices g); while (not (VSet.is_empty !vs)) do**

**let c = strong_component (VSet.choose !vs) in (vs
:= VSet.diff !vs c;**

**cs := c::!cs) done;**

**!cs)**

**Topological Ordering**

In a directed acyclic graph (DAG), the nodes can be
ordered such that each node in the ordering comes before all the other nodes to
which it has outbound edges. This is called a

topological
sort of the graph. In general, there is not a unique topological order for a
given DAG. If there are cycles in the graph, there is no topological ordering.
Topological orderings have many uses for problems ranging from job scheduling
to determining the order in which to compute quantities that depend on one
another (e.g., spreadsheets, order of compilation of modules in OCaml). The
following figure shows a DAG and a topological ordering for the graph.

Here is a
simple recursive function for computing a topological ordering, which operates
by choosing a vertex with no incoming edges as the first node in the ordering,
and then appending that to the result of recursively computing the ordering of
the graph with that node removed. If in this process there ever is a graph
where all the nodes have incoming edges, then the graph is cyclic and an error
is raised. The running time of this method is O(n2), whereas the asymptotically
fastest methods are O(n + m).

**lettopological_rec g = letrectopological_destr gr =
letvl = Graph.vertices gr in ifvl = [] then []**

**else**

**letsl = List.filter (function v
->Graph.in_degree v = 0) vlin ifsl = [] (* No vertices without incoming
edges *) thenfailwith "Graph is cyclic"**

**else**

**let v = List.hdslin (Graph.remove_vertex gr v; v ::
topological_destr gr) in**

**topological_destr (Graph.copy g)**

Here is
an iterative version of topological sort which has O(n + m) running time. Note
that while **remove_vertex **is O(m) time
for a single vertex, it is also O(m) time when all n vertices of the** **graph are removed, because each edge
is considered a constant number of times overall in the process of removing all
the vertices.

**lettopological_iter g = let gr = Graph.copy g in letsl
= ref (List.filter**

**(function v ->Graph.in_degree v = 0)
(Graph.vertices gr))**

**andrevorder = ref [] in**

**while !sl<> [] do let v = List.hd !slin (sl
:= List.tl !sl; List.iter**

**(function e ->**

**matchGraph.edge_info e with (_, dst, _) ->
ifGraph.in_degreedst = 1**

**thensl := dst :: !slelse ()) (Graph.outgoing v);
Graph.remove_vertex gr v; revorder := v :: !revorder) done;
ifGraph.num_vertices gr = 0 thenList.rev !revorder**

**(* Remaining vertices all with incoming edges *)
elsefailwith "Graph is cyclic"**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Non-Linear Data Structures : Graph Traversals |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.