Graph Algorithm #1: Topological Sort
Lecture 20: Topo-Sort and Dijkstra¡¯s Greedy Idea
? Items on Today¡¯s Lunch Menu:
? Topological Sort (ver. 1 & 2): Gunning for linear time¡
? Finding Shortest Paths
? Breadth-First Search
? Dijkstra¡¯s Method: Greed is good!
? Covered in Chapter 9 in the textbook
R. Rao, CSE 326
Some slides based on: CSE 326 by S. Wolfman, 2000
1
Graph Algorithm #1: Topological Sort
322
143
321
326
142
Problem: Find an order in
which all these courses can
be taken.
Example: 142 143 378
370 321 341 322
326 421 401
R. Rao, CSE 326
370
341
378
421
401
2
Topological Sort Definition
Topological sorting problem: given digraph G = (V, E) ,
find a linear ordering of vertices such that:
for all edges (v, w) in E, v precedes w in the ordering
B
C
A
F
D
E
R. Rao, CSE 326
3
Topological Sort
Topological sorting problem: given digraph G = (V, E) ,
find a linear ordering of vertices such that:
for any edge (v, w) in E, v precedes w in the ordering
B
C
A
F
D
Any linear ordering in which
all the arrows go to the right
is a valid solution
E
A
R. Rao, CSE 326
B
F
C
D
E
4
Topological Sort
Topological sorting problem: given digraph G = (V, E) ,
find a linear ordering of vertices such that:
for any edge (v, w) in E, v precedes w in the ordering
B
C
A
Not a valid topological
sort!
F
D
E
A
B
E
C
D
R. Rao, CSE 326
F
5
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edge
? The ¡°in-degree¡± of these vertices is zero
B
C
A
F
D
R. Rao, CSE 326
E
6
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edge
? If no such edges, graph has cycles (cyclic graph)
B
C
A
Example of a cyclic graph:
No vertex of in-degree 0
D
R. Rao, CSE 326
7
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edges
? Select one such vertex
Select
B
C
A
F
D
R. Rao, CSE 326
E
8
Topological Sort Algorithm
Step 2: Delete this vertex of in-degree 0 and all its
outgoing edges from the graph. Place it in the output.
B
C
A
F
D
E
R. Rao, CSE 326
9
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Select
B
C
F
D
R. Rao, CSE 326
A
E
10
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- heart failure treatment algorithm 2019
- chf algorithm treatment
- jnc 8 algorithm 2019
- arctan 1 x graph with intervals
- graph of arctan 1 x
- graph 2cosx 1 0
- algorithm to convert decimal to binary
- insertion sort algorithm python
- insertion sort algorithm analysis
- insertion sort algorithm java
- insertion sort algorithm assembly
- insertion sort algorithm pseudocode