0% found this document useful (0 votes)

14 views63 pages

Lec9 - DirectedGraphs (With Demo)

The document provides an overview of directed graphs (digraphs), including their definitions, applications, and common problems associated with them. It discusses the digraph API, representation methods such as adjacency lists, and algorithms like depth-first search for traversing digraphs. Additionally, it highlights various applications of digraphs in fields like transportation, web structure, and scheduling.

Uploaded by

abdklaib233

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

14 views63 pages

Lec9 - DirectedGraphs (With Demo)

Uploaded by

abdklaib233

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 63

Algorithms R OBERT S EDGEWICK | K EVIN W AYNE

D IRECTED G RAPHS

Modified by: Dr. Fahed Jubair and Dr. Ramzi Saifan

Computer Engineering Department

University of Jordan

http: //al g s 4 . cs . pr i n c e to n . ed u
D IRECTED G RAPHS
‣ introduction
‣ digraph API
‣ digraph search
‣ topological sort
‣ strong components (Bonus)
http: //al g s 4 . cs . pr i n c e to n . ed u
Directed graphs

Digraph. Set of vertices connected pairwise by directed edges.

outdegree = 4
indegree = 2
0

6 8 7

directed path 1 2
from 0 to 2

3 9 10

4 directed cycle

5
11 12

3
Digraph applications

digraph vertex directed edge

transportation street intersection one-way street

web web page hyperlink

food web species predator-prey relationship

WordNet synset hypernym

scheduling task precedence constraint

financial bank transaction

cell phone person placed call

infectious disease person infection

game board position legal move

citation journal article citation

object graph object pointer

inheritance hierarchy class inherits from

control flow code block jump

11
Some digraph problems

problem description

s→t path Is there a path from s to t ?

shortest s→t path What is the shortest path from s to t ?

directed cycle Is there a directed cycle in the graph ?

topological sort Can the digraph be drawn so that all edges point upwards?

strong connectivity Is there a directed path between all pairs of vertices ?

transitive closure For which vertices v and w is there a directed path from v to w ?

PageRank What is the importance of a web page ?

12
D IRECTED G RAPHS
‣ introduction
‣ digraph API
‣ digraph search
‣ topological sort
‣ strong components (Bonus)
http: //al g s 4 . cs . pr i n c e to n . ed u
Digraph API

Almost identical to Graph API.

public class Digraph

Digraph(int V) create an empty digraph with V vertices

Digraph(In in) create a digraph from input stream

void addEdge(int v, int w) add a directed edge v→w

Iterable<Integer> adj(int v) vertices pointing from v

int V() number of vertices

int E() number of edges

Digraph reverse() reverse of this digraph

String toString() string representation

15
Digraph API

% java Digraph tinyDG.txt

0->5
0->1
2->0
2->3
3->5
3->2
4->3
4->2
5->4
⋮
11->4
11->12
⋮ 12->9

In in = new In(args[0]); read digraph from

Digraph G = new Digraph(in); input stream

for (int v = 0; v < G.V(); v++)

for (int w : G.adj(v)) print out each
edge (once)
StdOut.println(v + "->" + w);
16
Digraph representation: adjacency lists

Maintain vertex-indexed array of lists.

19
Digraph representations

In practice. Use adjacency-lists representation.

・Algorithms based on iterating over vertices pointing from v.
・Real-world digraphs tend to be sparse.
huge number of vertices,
small average vertex degree

insert edge from edge from iterate over vertices

representation space
v to w v to w? pointing from v?

list of edges E 1 E E

adjacency matrix V2 1† 1 V

adjacency lists E+V 1 outdegree(v) outdegree(v)

† disallows parallel edges

20
Adjacency-lists graph representation (review): Java implementation

public class Graph

{
private final int V;
private final Bag<Integer>[] adj; adjacency lists
public Graph(int V)
{
this.V = V;
adj = (Bag<Integer>[]) new Bag[V]; create empty graph

for (int v = 0; v < V; v++) with V vertices

adj[v] = new Bag<Integer>();

}
public void addEdge(int v, int w)
add edge v–w
{
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v)
iterator for vertices
{ return adj[v]; } adjacent to v
}
21
Adjacency-lists digraph representation: Java implementation

public class Digraph

{
private final int V;
private final Bag<Integer>[] adj; adjacency lists
public Digraph(int V)
{
create empty digraph
this.V = V;
with V vertices
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<Integer>();
}
public void addEdge(int v, int w)
add edge vw
{
adj[v].add(w);
}

public Iterable<Integer> adj(int v) iterator for vertices

{ return adj[v]; } pointing from v
}
22
D IRECTED G RAPHS
‣ introduction
‣ digraph API
‣ digraph search
‣ topological sort
‣ strong components (Bonus)
http: //al g s 4 . cs . pr i n c e to n . ed u
Reachability

Problem. Find all vertices reachable from s along a directed path.

25
Depth-first search in digraphs

Same method as for undirected graphs.

・Every undirected graph is a digraph (with edges in both directions).
・DFS is a digraph algorithm.

DFS (to visit a vertex v)

Mark v as visited.
Recursively visit all unmarked
vertices w pointing from v.

26
Depth-first search demo

To visit a vertex v : 42

・Mark vertex v as visited. 23

・Recursively visit all unmarked vertices pointing from v. 32

60
01
0 20
1112
6 8 7
129
1 2 910
911
89
1012
3 9 10
114

4 43
35
5 68
11 12
86
54

a directed graph 05

64 27
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 F –

2 1 F –
1
2 F –
3 F –
4 F –
3 9 10
5 F –

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
a directed graph
11 F –
28
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 F –
3 F –
4 F –
3 9 10
5 F –

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 0: check 5 and check 1
11 F –
29
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 F –
3 F –
4 F –
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 5: check 4
11 F –
30
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 F –
3 F –
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 4: check 3 and check 2
11 F –
31
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 F –
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 3: check 5 and check 2
11 F –
32
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 F –
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 3: check 5 and check 2
11 F –
33
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 2: check 0 and check 3
11 F –
34
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 2: check 0 and check 3
11 F –
35
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 2
11 F –
36
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 3
11 F –
37
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 4: check 3 and check 2
11 F –
38
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 4
11 F –
39
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 5
11 F –
40
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 F –
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 0: check 5 and check 1
11 F –
41
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 T 0
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
visit 1
11 F –
42
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 T 0
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 1
11 F –
43
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 T 0
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done 0
11 F –
44
12 F –
Directed depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 T 0
1
2 T 3
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
done
11 F –
45
12 F –
Depth-first search demo

To visit a vertex v :
・Mark vertex v as visited.
・Recursively visit all unmarked vertices pointing from v.

0
v marked[] edgeTo[]

6 8 7
0 T –

2 1 T 0
1
reachable
2 T 3
from vertex 0
3 T 4
4 T 5
3 9 10
5 T 0

4 6 F –
7 F –
5
11 12 8 F –
9 F –
10 F –
reachable from 0
11 F –
46
12 F –
Depth-first search (in undirected graphs)

Recall code for undirected graphs.

public class DepthFirstSearch
{
private boolean[] marked;

public DepthFirstSearch(Graph G, int s) true if connected to s

{
marked = new boolean[G.V()];
dfs(G, s); constructor marks
} vertices connected to s

private void dfs(Graph G, int v)

{
recursive DFS does the work
marked[v] = true;
for (int w : G.adj(v))
if (!marked[w]) dfs(G, w);
}

public boolean visited(int v) client can ask whether any

{ return marked[v]; } vertex is connected to s
}
47
Depth-first search (in directed graphs)

Code for directed graphs identical to undirected one.

[substitute Digraph for Graph]
public class DirectedDFS
{
private boolean[] marked; true if path from s

public DirectedDFS(Digraph G, int s)

{
constructor marks
marked = new boolean[G.V()];
vertices reachable from s
dfs(G, s);
}
private void dfs(Digraph G, int v)
recursive DFS does the work
{
marked[v] = true;
for (int w : G.adj(v))
if (!marked[w]) dfs(G, w);
}
client can ask whether any
vertex is reachable from s
public boolean visited(int v)
{ return marked[v]; }
} 48
Reachability application: mark-sweep garbage collector

Every data structure is a digraph.

・Vertex = object.
・Edge = reference.
Roots. Objects known to be directly accessible by program (e.g., stack).

Reachable objects. Objects indirectly accessible by program

(starting at a root and following a chain of pointers).

roots

50
Reachability application: mark-sweep garbage collector

Mark-sweep algorithm. [McCarthy, 1960]

・Mark: mark all reachable objects.
・Sweep: if object is unmarked, it is garbage (so add to free list).
Memory cost. Uses 1 extra mark bit per object (plus DFS stack).

roots

51
Breadth-first search in digraphs

Same method as for undirected graphs.

・Every undirected graph is a digraph (with edges in both directions).
・BFS is a digraph algorithm.

BFS (from source vertex s)

Put s onto a FIFO queue, and mark s as visited.

Repeat until the queue is empty:
- remove the least recently added vertex v
- for each unmarked vertex pointing from v:
add to queue and mark as visited.

Proposition. BFS computes shortest paths (fewest number of edges)

from s to all other vertices in a digraph in time proportional to E + V.
53
Directed breadth-first search demo