La lecture à portée de main
Description
Informations
Publié par | Zawyug |
Nombre de lectures | 21 |
Langue | English |
Extrait
Tutorial 4
Data Structures ’08
Jonathan Cederberg <jonathan.cederberg@it.uu.se>
thFriday, October 10 , 2008Outline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 2 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 3 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample exam question
Example
DFS vs. BFS
Another Prove or disprove:
Example
n+1 nd) 2 =O(2 )
e) lg(f (n)) =O(lg(g(n))) =) f (n) =O(g(n))
f) max(f (n);g(n)) = (f (n) +g(n))
DS’08 Dept. of Information Technology - 4 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 5 - Jonathan Cederberg | jonathan.cederberg@it.uu.seGraphs - what are they good for?
Provide a good representation of...
Example Data structures (linked lists, hash tables, trees)
DFS vs. BFS The internet
Another
Example DNA
A road network
A sewer system
The circulation of your favorite bodily fluid
...
Google uses graphs! I use graphs!
DS’08 Dept. of Information Technology - 6 - Jonathan Cederberg | jonathan.cederberg@it.uu.seWhether there is a path from every junction to all other
junctions.
And then?
With the representation, we can isolate interesting properties of
Example
the graph, and thus discover interesting properties of theDFS vs. BFS
underlying system.Another
Example Example: A road system is abstracted as a directed graph in
the natural way. What information would computing the
strongly connected components of this graph give us?
DS’08 Dept. of Information Technology - 7 - Jonathan Cederberg | jonathan.cederberg@it.uu.seAnd then?
With the representation, we can isolate interesting properties of
Example
the graph, and thus discover interesting properties of theDFS vs. BFS
underlying system.Another
Example Example: A road system is abstracted as a directed graph in
the natural way. What information would computing the
strongly connected components of this graph give us?
Whether there is a path from every junction to all other
junctions.
DS’08 Dept. of Information Technology - 7 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample
Fundamentals: DFS and BFS
DFS vs. BFS
Another We look a vertex at a time, examining it and discovering
Example
its neighbours (moving the frontier).
The difference lies in the order we explore the neighbours!
DS’08 Dept. of Information Technology - 8 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample
DFS
DFS vs. BFS
Another When examining a node, just tag it as discovered and
Example
examine all not yet discovered neighbours first.
So we examine the nodes using a LIFO policy.
DS’08 Dept. of Information Technology - 9 - Jonathan Cederberg | jonathan.cederberg@it.uu.se