Page 28 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes  Locating the shortest path among two nodes u and v
 Testing a graph for bipartiteness
 (Reverse) Cuthill–McKee mesh numbering
 Ford–Fulkerson method for calculating the maximum flow in a flow network

 Serialization/Deserialization of a binary tree vs serialization in sorted order, permits the
tree to be reconstructed in a competent manner.

Finding Connected Components

The set of nodes reached by a BFS (breadth-first search) form the associated component enclosing
the starting node.
Testing Bipartiteness

BFS can be utilized to test bipartiteness, by beginning the hunt at any vertex and providing
alternating labels to the vertices visited all through the search. That is, provide label 0 to the
beginning vertex, 1 to all its neighbours, 0 to those neighbours, and so on. If at any step a vertex
has (visited) neighbours with the same label as itself, then the graph is not bipartite. If the search
ends without such a circumstance occurring, then the graph is bipartite.
Self Assessment

Fill in the blanks:
6. In graph theory, ............................... is a graph search algorithm that starts at the root node
and discovers all the adjacent nodes.
7. From the position of the algorithm, all child nodes attained by increasing a node are
added to a ............................... queue.

8. BFS can be utilized to test ..............................., by beginning the hunt at any vertex and
providing alternating labels to the vertices visited all through the search.

2.4 Depth-first Search

Depth-first Search (DFS) is an algorithm for navigating or looking for a tree, tree structure, or
graph. One begins at the root (choosing some node as the root in the graph case) and discovers
as far as possible with each branch before backtracking.

Officially, DFS is an uninformed search that advances by increasing the first child node of the
search tree that occurs and therefore going deeper and deeper until a purpose node is found, or
until it reaches a node that has no children. Then the search backtracks, recurring to the most
recent node it hasn’t completed exploring. In a non-recursive accomplishment, all freshly extended
nodes are added to a stack for exploration.
The time and space analysis of DFS varies as per its application area. In hypothetical computer
science, DFS is usually used to navigate a complete graph, and takes time O(|V| + |E|), linear
in the size of the graph. In these applications it also utilizes space O(|V|) in the worst case to
accumulate the stack of vertices on the current search path in addition to the set of already-
visited vertices. Consequently, in this setting, the time and space bounds are the comparable as
for breadth first search and the option of which of these two algorithms to use depends less on
their complexity and more on the dissimilar properties of the vertex orderings the two algorithms
generate.

22 LOVELY PROFESSIONAL UNIVERSITY