Scribd
Upload
50 views11 pages

Graphs and Network Flows IE411: Dr. Ted Ralphs

The document discusses graph search algorithms and their applications. It presents a basic search algorithm template that uses a queue to iteratively explore nodes in a graph. The template can be used to solve problems like connectivity and topological sorting. Different queue data structures and node processing steps yield different search orderings and complexities.

Uploaded by

alvaro_65
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
50 views11 pages

Graphs and Network Flows IE411: Dr. Ted Ralphs

The document discusses graph search algorithms and their applications. It presents a basic search algorithm template that uses a queue to iteratively explore nodes in a graph. The template can be used to solve problems like connectivity and topological sorting. Different queue data structures and node processing steps yield different search orderings and complexities.

Uploaded by

alvaro_65
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Graphs and Network Flows IE411 Lecture 4

Dr. Ted Ralphs

IE411 Lecture 4

Search Algorithms
Search algorithms are fundamental techniques applied to solve a wide range of optimization problems. Search algorithms attempt to nd all the nodes in a network satisfying a particular property. Examples Find nodes that are reachable by directed paths from a source node. Find nodes that can reach a specic node along directed paths Identify the connected components of a network Identify directed cycles in network

IE411 Lecture 4

Basic Search Algorithm


This is the basic search algorithm.

Input: Graph G = (N, A) and source node s N 1: Q {s} 2: while Q = do 3: remove the next node v from Q 4: mark v 5: process v 6: for v A(v) do 7: if v is not marked then 8: Q Q {v } 9: end if 10: end for 11: end while (Figure 9.1 from Papadimitriou and Steiglitz)

IE411 Lecture 4

Search Algorithm
The search proceeds dierently depending on which element v is selected from Q on line 3 in each iteration. Q must be ordered in some way by storing it in an appropriate data structure. If Q is a queue, elements are inserted at one end and removed from the other and we get FIFO ordering. If Q is a stack, elements are inserted and deleted from the the same end and we get LIFO ordering. The eciency of the algorithm can be aected by the data structure used to maintain Q, and what additonal steps are required in processing v (line 5).

IE411 Lecture 4

Search Tree
Associated with each search ordering is a search tree that can be used to visualize the algorithm. At the time a node v is added to the queue on line 8, we record v as its predecesor. The set of arcs formed by each node and its predecessor forms a tree rooted at s.

IE411 Lecture 4

Complexity of Search Algorithms


1. Initialization. 2. Maintaining the set Q. What is the maximum number of additions and removals? How many operations are required for each? 3. Searching the adjacency lists. How many times do we touch each element of each list? How much work do we do each time we touch an element? 4. Processing a node.

IE411 Lecture 4

Algorithm Search
The algorithm is a template for a whole class of algorithms. How can we use it to determine whether a graph is connected? Suppose the implementation of line 5 is count count + 1; order[v] count What are we doing?

IE411 Lecture 4

Topological Ordering
In a directed graph, the arcs can be thought of as representing precedence constraints. In other words, an arc (i, j) represents the constraint that node i must come before node j. Given a graph G = (N, A) with the nodes labeled with distinct numbers 1 through n, let order(i) be the label of node i. Then, this labeling is a topological ordering of the nodes if for every arc (i, j) A, order(i) < order(j). Can all graphs be topologically ordered?

IE411 Lecture 4

Topological Ordering
The following algorithm will detect presence of a directed cycle or produce a topological ordering of the nodes.

Input: Directed acyclic graph G = (N, A) Output: The array order is a topological ordering of N . count 1 while {v N : I(v) = 0} = do let v be any vertex with I(v) = 0 order[v] count count count + 1 delete v and all outgoing arcs from G end while if N = then return success else report failure end if

IE411 Lecture 4

Topological Ordering Algorithm


Correctness of algorithm 1. If G has a cycle... 2. If G is acyclic... Running time of the algorithm

IE411 Lecture 4

10

Graph Traversal Methods


Breadth-rst search Depth-rst search Pre-order In-order Post-order How do we implement each of these? How can we get a topological sort from a straightforward graph search?

You might also like