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
143
142
370
Problem: Find an order in which all these courses can 378 be taken. Example: 142 143 378
370 321 341 322 326 421 401
R. Rao, CSE 326
321 326
341
401
322 421
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 A
C 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 A
C
Any linear ordering in which
all the arrows go to the right
F is a valid solution
D
E
A B FC DE
R. Rao, CSE 326
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 A
C F
Not a valid topological sort!
D
E
A B EC DF
R. Rao, CSE 326
5
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edge
? The "in-degree" of these vertices is zero
B A
D
C F
E
R. Rao, CSE 326
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:
D
No vertex of in-degree 0
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
E
R. Rao, CSE 326
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
F
A
D
E
R. Rao, CSE 326
9
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Select
B C
F
A
D
E
R. Rao, CSE 326
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 download
- python programming 2 regular expressions lists
- algorithms pseudocode examples
- abstract data types adt s
- algorithmic thinking loops and conditionals
- search command cheatsheet
- complete guide for python programming
- chapter 9 scraping sites that use javascript and ajax
- resume ranking using nlp and machine learning
- s python cheat sheet data science free
- unit 5c merge sort
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