Directed Graphs - Princeton University

Directed Graphs

digraph search transitive closure topological sort strong components

References: Algorithms in Java, Chapter 19

1

Directed graphs (digraphs)

Set of objects with oriented pairwise connections.

one-way streets in a map

dependencies in software modules

prey-predator relationships

hyperlinks connecting web pages

0

25

1

0

34

2

3

4

7

5

6

10

2

7

40

8

41 44

29 49

15 45

19 8

9 33 10

11 12 13 14 15

16

28

17

1

14

18

19

22

48

20

39

21

18

6

21

22

23

24

42

13

23

25 26 27

31

47

28

11

12

29

32

30

30

31

27

5

37

9

26

32

33

34

16

35 36

43

37

38

4

24

39 40

38

41

3

17

36

20

42

35

46

43 44 45

46

47

48

49

6

22

Page ranks with histogram for a larger example

2

Digraph applications

digraph

financial transportation

scheduling WordNet

Web game telephone food web infectious disease citation object graph inheritance hierarchy control flow

vertex

stock, currency street intersection, airport

task synset web page board position person species person journal article object class code block

edge

transaction highway, airway route precedence constraint

hypernym hyperlink legal move placed call predator-prey relation infection citation pointer inherits from

jump

3

Some digraph problems

Transitive closure. Is there a directed path from v to w?

Strong connectivity. Are all vertices mutually reachable?

Topological sort. Can you draw the digraph so that all edges point from left to right?

PERT/CPM. Given a set of tasks with precedence constraints, how we can we best complete them all?

Shortest path. Find best route from s to t in a weighted digraph

PageRank. What is the importance of a web page? 4

Digraph representations

Vertices

? this lecture: use integers between 0 and V-1. ? real world: convert between names and integers with symbol table.

Edges: four easy options

? list of vertex pairs ? vertex-indexed adjacency arrays (adjacency matrix) ? vertex-indexed adjacency lists ? vertex-indexed adjacency SETs

0

7

8

Same as undirected graph BUT

orientation of edges is significant.

1

2

6

9

3

4

11

5

10 12

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download