代写代考 Graph Search - PowCoder代写

Graph Search
Comp Sci 214

Things we can do with graphs

• Take an action at (visit) every node.
􏰀 E.g., collect garbage from every house in a neighborhood
• Ask whether there is a path from v to u.
􏰀 E.g., with a social graph, can my great-grandmother find a
chain of people who can eventually introduce her to the pope? (True story!)
• Ask whether there are any cycles.
􏰀 E.g., given a circuit diagram, is there a feedback loop?
• We can accomplish these three tasks (and more!) with a graph search algorithm

Things we can do with graphs
• Take an action at (visit) every node.
􏰀 E.g., collect garbage from every house in a neighborhood
• Ask whether there is a path from v to u.
􏰀 E.g., with a social graph, can my great-grandmother find a
chain of people who can eventually introduce her to the pope? (True story!)
• Ask whether there are any cycles.
􏰀 E.g., given a circuit diagram, is there a feedback loop?
• We can accomplish these three tasks (and more!) with a graph search algorithm
• But first, we’ll look at a restricted version of the problem
􏰀 Let’s start with one very restricted kind of graph: trees
􏰀 And see simpler versions of graph search algos: tree walks

Tree walks

Tree walks (AKA tree traversals)
The goal of a tree walk is to visit every node in a tree.
• Necessary to solve a number of problems
􏰀 Summing up the size of all the files in a filesystem directory
􏰀 Executing a program with an interpreter (cf. Comp Sci 321) 􏰀 Etc.
• “Visiting” = taking an action at that node 􏰀 Depends on what our algorithm is doing 􏰀 E.g., adding the size of a file to the total 􏰀 Here, we’ll leave it generic
We’ll start simple: tree walks on binary trees

Tree walk example
• Start at the root of the tree
6 15
3 7 13 16 22

Tree walk example
• Start at the root of the tree
• Go down to the left child, then its left child, etc.
6 15 24 36 3 7 13 16 22

Tree walk example
• Start at the root of the tree
• Go down to the left child, then its left child, etc. • When you can’t go any deeper, go back up
6 15 24 36 3 7 13 16 22

Tree walk example
• Start at the root of the tree
• Go down to the left child, then its left child, etc.
• When you can’t go any deeper, go back up
• Then go down to the right child (then its left child, etc.) • When you’ve done both sides, keep going back up
6 15 24 36 3 7 13 16 22

Tree walk example
• Start at the root of the tree
• Go down to the left child, then its left child, etc.
• When you can’t go any deeper, go back up
• Then go down to the right child (then its left child, etc.)
• When you’ve done both sides, keep going back up
• After doing both sides of the root, you’ve visited every node
6 15 24 36 3 7 13 16 22

Tree walk pseudocode
Procedure DepthFirst(node)is if node is not null then
visit node;
DepthFirst(node.left); endDepthFirst(node.right)
• Visit, then recursively traverse the left subtree, then recursively traverse the right subtree
􏰀 left subtree = the left child of a node, plus its descendants (m.m. right)
• This algorithm is called depth-first search (DFS) 􏰀 We go as deep as we can, then we backtrack

Tree walkS (plural)
If all you want is to call visit on every node, we’re done. • E.g., summing file sizes in a file system
But, some algorithms require visits to be in a specific order!
• Previous algorithm always visits parents before children
• But, e.g., interpreters require children to be visited before
their parents! (cf. Comp Sci 321)
For binary trees, (2 + 1)! (= 6) possible orders of operations:
• visit • left • right
• left • visit • right
• left • right • visit
• visit • right • left
• right • visit • left
• right • left • visit
Reordering the loop body gives you depth-first search variants.

Tree walkS (plural)
#1 #2 #3 #4 #5 #6
• left • visit • right
• left • right • visit
• visit • right • left
• right • visit • left
• right • left • visit
• #1 (original) is called pre-order depth-first search: visits parents before (pre) children
• #2 is called in-order: visits parents in-between children
• #3 is called post-order: visits parents after (post) children
􏰀 This is the one we want for interpreters
• #4–6 are the same, but right-to-left: reverse pre-order, etc.
􏰀 Reverse post-order used a lot in program analysis (compilers, security)

Tree walk on rose trees
Procedure DepthFirst(node)is visit node;
for c to Children(node) do endDepthFirst(c)
• Iterate over all children, traversing each one recursively • Only pre- and post- order really make sense here

Graph search

Graph search
Similar idea to tree walks
• Want to perform an action at every node of a graph.
• (We’ll use the same pattern to accomplish other tasks too!) But with general graphs, we now have to handle cycles!
• Will need to keep track of where we’ve been • So we don’t go around in circles
Let’s start from our tree depth-first search and adapt it.

Graph DFS example
Graphs don’t have roots; have to pick a starting point.

Graph DFS example
A node’s neighbors/successors are not ordered. Traversing in any order is ok.

Graph DFS example

Graph DFS example
Been there before. No need to go there again. Backtrack.

Graph DFS example

Graph DFS example
Once we’ve explored all the neighbors of the start, we’re done.

Recursive DFS algorithm
Procedure DFS(graph, start)is
seen ← new array of size | graph.V |, filled with false;
Procedure Traverse(v)is if not seen[v] then
seen[v] ← true; Visit(v);
for u in Successors(graph, v) do endTraverse(u)
Traverse(start); endreturn seen
Similar to rose tree version, but recording where you’ve been.

Recursive DFS algorithm (records paths)
• If all you want to do is visit every node, this is all you need. 􏰀 But graph search can do much more than that!
• What if you’re looking for paths between nodes?
􏰀 We know whether we’ve reached a node, but we don’t keep
track of how we got there.
• Thankfully, doing that is not any harder.
􏰀 Instead of using an array of booleans (seen)
􏰀 Use an array of node ids, recording which node we came
from when we got to each node (preds)

Recursive DFS algorithm (records paths)

Recursive DFS algorithm (records paths)
Reverse tree, children point to parents. Each node has just the one parent. Can store in a vector!

Recursive DFS algorithm (records paths)
Reverse tree, children point to parents. Each node has just the one parent. Can store in a vector!
How do we go from 0 to 6? Work backwards from 6 in the array! Gives a path.
Not necessarily the shortest! What is that path?

Recursive DFS algorithm (records paths)
Procedure DFS(graph, start)is
preds ← new array of size | graph.V |, filled with None;
Procedure Visit(pred, v)is if not preds[v] then
preds[v] ← pred;
for u in Successors(graph, v) do endVisit(v, u)
Visit(start, start); endreturn preds

Recursive DFS algorithm (full graph)
• Previous versions traversed starting from a single vertex. 􏰀 If we have a non-connected graph, won’t reach everything. 􏰀 Will only reaching that node’s connected component!
• To be sure to reach all nodes, we need to traverse starting from each vertex.
􏰀 With a shared seen/preds for all traversals, won’t do any redundant work.
􏰀 If we try to start from a vertex we’ve already seen, we stop right away.

Recursive DFS algorithm (full graph)
Procedure DFS(graph)is
preds ← new array of size | graph.V |, filled with None;
Procedure Visit(pred, v)is if not preds[v] then
preds[v] ← pred;
for u in Successors(graph, v) do endVisit(v, u)
for v in Vertices(graph) do endVisit(v, v)
endreturn preds

DFS Time Complexity
Visit each vertex at most once: O(|V|) (assuming O(1) visit) For each vertex, loop over successors.
Total number of successors, across all vertices: O(|E|)

DFS Time Complexity
Visit each vertex at most once: O(|V|) (assuming O(1) visit) For each vertex, loop over successors.
Total number of successors, across all vertices: O(|E|)
Adjacency list
• Iterating over successors, one vertex: O(d) • Iterating over successors, all vertices: O(|E|) • Total: O(|V|) · O(1) + O(|E|) = O(|V| + |E|)

DFS for cycle detection

DFS for cycle detection
Keep track of the nodes we’ve started exploring.

DFS for cycle detection
Keep track of the nodes we’ve started exploring.
When we’re done with their neighbors, mark as finished.

DFS for cycle detection
Keep track of the nodes we’ve started exploring.
When we’re done with their neighbors, mark as finished. Seeing finished nodes again is ok.

DFS for cycle detection
Keep track of the nodes we’ve started exploring.
When we’re done with their neighbors, mark as finished. Seeing finished nodes again is ok.
Seeing an unfinished node again means we have a cycle!

DFS for cycle detection
Procedure FindCycle(graph)is
started ← new array of size | graph.V |, filled with false; finished ← new array of size | graph.V |, filled with false;
Procedure Visit(v)is
if not finished[v] then
if started[v] then endwe found a cycle!
started[v] ← true;
for u in Successors(graph, v) do endVisit(u)
finished[v] ← true; end
for v in Vertices(graph) do endVisit(v)

Breadth-first search (BFS)
All our traversals so far have been depth-first
• I.e., go as far along one path as possible, then backtrack
• Then go as far as possible along another path, etc.
Not all visiting orders can be achieved in a depth-first manner!
Here’s an interesting one that can’t.
• Start from one vertex
• Visit all its neighbors
• Then visit all their neighbors
• Continue with nodes 3 edges away from start, then 4, etc. • This is breadth-first order: instead of going deep, go wide
That order is necessary for some algorithms!
• Two-space garbage collection (cf. Comp Sci 321) • “Forest fire” algorithm for flood fill (graphics)

Breadth-first search (BFS)
To get that order, we’ll need a new traversal template. Insight: depth-first search is recursive
• I.e., it uses a stack to keep track of what to do next 􏰀 What stack? The call stack! Implicit in recursive calls
• Last-in, first-out. When we reach a dead end, we go back to the last node we saw (parent)
To get breadth-first order, let’s use a queue instead!

Running BFS on a digraph

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts