6.1 Classic Algorithms -Graph Traversal

Question 1

What is “Search” in Graphs?

Answer 1

❑Start at the source node and search until we find the target node
❑When we work with graphs, we often wish to do something to each node in the graph exactly once
❑Visit each node once and only once
❑Examples:
❑A piece of information that needs to be distributed to all the computers on a network
❑Look for information among computer in a networ

Question 2

What is “Depth-First Search”(DFS)?

Answer 2

1.We visit the starting node and then proceed to follow links through the graph until we reach a dead end
2.We then back up along our path until we find an unvisited adjacent node, and continue in that new direction
3.The process completes when we back up to the starting node and all the nodes adjacent to it have been visited
4.If presented with two choices, we choose the node with numerically and/or alphabetically smaller label (just for convenience

Question 2

What is “Depth-First”?

Answer 2

❑Depth-First: allows us to explore nodes and edges of a graph
❑The traversal will go as far as possible down a path until a “Dead End” is reached
❑In an undirected graph:
❑A node is a dead end if all of the nodes adjacent to it have already been visited
❑In a directed graph:
❑A node is a dead end If it has no outgoing edges and we visited everything else

Question 3

DFS Running Time Analysis

Answer 3

❑Remember:
❑DFS is called on each node exactly once
❑nnodes : O(n)
❑Every edge is processed once
❑medges: O(m)
❑O(n) + O(m) O(n+m)

Question 4

Other Types of Graph “Search”

Answer 4

❑There are other ways to search a graph other than visiting all nodes
❑Finding a path between two nodes
❑Finding the shortest path between two nodes (number of edges)
❑Finding the cheapest path between two nodes (a function of edge weight)

Question 5

The Exhaustive Search

Answer 5

❑The exhaustive search systematically evaluates every possible path in a graph
❑This methods is guaranteed to find what we are looking for
❑However this method is unsuitable for most real world problems

Question 6

Exhaustive Running Time

Answer 6

❑This is very complicated to compute
❑It depends on how the nodes and edges are organised
❑If we look at the worse case, that of a complete graph:
❑Here all the nodes are connected to each other
❑For the first node in the path there are n-1edges to follow
❑For the second, n-2
❑For the third, n-3, …
❑Hence we get (n-1)(n-2)(n-3)…1 = O((n-1)!)

Question 7

Breadth-First Search

Answer 7

❑Breadth-first search is different from depth first search in the way that it explores the graph…
❑This search method considers neighbouring nodes first
❑All the neighbours of the start node are expanded first
❑Then the neighbours of the neighbours
❑Until the goal state is found
❑Similar to depth-first search, breadth-first search will eventually find a path to the goal, but it may not be the best path
❑This search is expensive since all the partial paths being considered must be stored
❑The algorithm is similar to the exhaustive search algorithm, but it stops when the goal node is reached
❑Exhaustive generates all path

Question 8

Best-First Search

Answer 8

❑Best-first search is an improvement upon depth-first search
❑A heuristic is used to decide which node is explored next
❑A heuristicis a rule of thumb or best practice
❑We will look at heuristics in much more detail later
❑For example nodes are expanded in order of lowest cost

Question 9

Minimum Spanning Trees

Answer 9

❑A spanning tree is a sub-graph of a connected and undirected graph. It should form a tree (no cycles) and contains all of the nodes of the super-graph
❑The super-graph is usually a complete graph
❑The edges can only come from the super-graph
❑A graph may have many spanning trees
❑The cost of a spanning tree is the sum of all the edge weights
❑A minimum spanning tree (MST) is the spanning tree with the minimum cost

Question 10

Applications of MST

Answer 10

❑Network Design
❑Computer networks, telecommunications networks, transportation networks, water supply networks, etc…
❑E.g. in network design we use it to ensure devices (represented as nodes) are connected while avoiding network loops and ensuring efficient routing…
❑E.g. to minimisethe total cable length or infrastructure cost…
❑CfAredshift survey
❑MSTs used for understanding the large-scale structure of the universe
❑Approximation algorithms for NP-hard problems
❑E.g. Travelling salesperson problem
❑Cancer imaging
❑The British Columbia Cancer Research centre uses them to describe the arrangements of nuclei in skin cell