Week10-6

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Week10-6 as PDF for free.

More details

  • Words: 3,163
  • Pages: 7
Outline • • • • • • •

Data Structures – Week #10 Graphs & Graph Algorithms

Motivation for Graphs Definitions Representation of Graphs Topological Sort Breadth-First Search (BFS) Depth-First Search (DFS) Single-Source Shortest Path Problem (SSSP) – Dijkstra’s Algorithm

• Minimum Spanning Trees – Prim’s Algorithm – Kruskal’s Algorithm January 5, 2006

Borahan Tümer, Ph.D.

2

Motivation

Graphs & Graph Algorithms

January 5, 2006

Borahan Tümer, Ph.D.

3

Graph Definitions

– Graphs are useful structures for solving many problems computer science is interested in including but not limited to • Computer and telephony networks • Game theory • Implementation of automata

January 5, 2006

Borahan Tümer, Ph.D.

Adjacency Set and Being Adjacent

• A graph G=(V,E) consists a set of vertices V and a set of edges E. • An edge (v,w)E has a starting vertex v and and ending vertex w. An edge sometimes is called an arc. • If the pair is ordered, then the graph is directed. Directed graphs are also called digraphs. • Graphs which have a third component called a weight or cost associated with each edge are called weighted graphs.

• Vertex w is adjacent to v iff (v,w)E. In an undirected graph with e=(v,w), v and w are adjacent to each other. • In Fig. 6.1, the vertices v, w and x form the adjacency set of u or Adj(u)={v,w,x}.

January 5, 2006

January 5, 2006

Borahan Tümer, Ph.D.

4

5

Borahan Tümer, Ph.D.

u

v

w

x

6

More Definitions

Path Definitions • A path in a graph is a sequence of vertices w1, w2, …,wn where each edge (wi, wi+1)E for 1di
• A cycle is a path such that the vertex at the destination of the last edge is the source of the first edge. – A digraph is acyclic iff it has no cycles in it.

• In-degree of a vertex is the number of edges arriving at that vertex. • Out-degree of a vertex is the number of edges leaving that vertex. January 5, 2006

Borahan Tümer, Ph.D.

7

January 5, 2006

Connectedness

Borahan Tümer, Ph.D.

8

Representation of Graphs

An undirected graph is connected if there exists a path from every vertex to every other vertex. • A digraph with the same property is called strongly connected. • If a digraph is not strongly connected, but the underlying graph is connected, then the digraph is said to be weakly connected. • A graph is complete if there is an edge between every pair of vertices

• Two ways to represent graphs: – Adjacency matrix representation – Adjacency list representation

January 5, 2006

January 5, 2006

Borahan Tümer, Ph.D.

9

• Assume you have n vertices. • In a boolean array with n2 elements, where each element represents the connection of a pair of vertices, you assign true to those elements that are connected by an edge and false to others. • Good for dense graphs. • Not very efficient for sparse (i.e., not dense) graphs. • Space requirement: O(|V|2).

Borahan Tümer, Ph.D.

10

Adjacency matrix representation (AMR)

Adjacency Matrix Representation

January 5, 2006

Borahan Tümer, Ph.D.

7

1

5

2 9

8

4

4

5

6

8

6 9 7

7

4

3

1

3

6

3

7

5

3 4

8

1 6

9 3

2

4

5

6

8

9

’ 8

3

9

’ ’ 3

’

1

’ 7

2

’ ’ 5

3

’ ’ ’ 6

’ ’ 4

7

9

’ 3

’ ’ ’ ’ ’

4

’ ’ ’ ’ ’ ’ ’ ’ 5

5

’ 4

6

’ ’ ’ ’ ’ ’ ’ ’ 7

7

’ ’ 8

3

6

’

7

’ ’ ’ ’ ’ ’ ’ 4

8

’ ’ ’ ’ ’ ’ ’ ’ 1

9

’ ’ ’ ’ ’ ’ ’ ’ 3

6

Disadvantage: Waste of space for sparse graphs Advantage: Fast access 11

January 5, 2006

Borahan Tümer, Ph.D.

12

Adjacency List Representation

Adjacency list representation (ALR) array index: source vertex; first number: destination vertex; second number: cost of the corresponding edge

Assume you have n vertices. • We employ an array with n elements, where ith element represents vertex i in the graph. Hence, element i is a header to a list of vertices adjacent to the vertex i. • Good for sparse graphs • Space requirement: O(|E|+|V|). January 5, 2006

Borahan Tümer, Ph.D.

13

7

1

5

2

3

6 8

3

4

4

5

6

8

6 9 7

7

4

9

3

7

5

3 8

4

1 6

9 3

1

2,7

4,8

5,9

8,3

2

3,5

6,4

7,9

9,3

3

4,6

4

9,5

5

2,4

2,4

2,4

2,4

6

9,7

7

8,4

8

9,1

9

9,3

2,4

2,4

2,4

Disadvantage: Sequential search among edges of a node Advantage: Minimum space requirement January 5, 2006

Borahan Tümer, Ph.D.

14

Algorithm for Topological Sort*

Topological Sort

Void Toposort () { Queue Q; int ctr; Vertex v,w; Q=createQueue(NumVertex); for each vertex v if (indegree[v] == 0) enqueue(v,Q); while (!IsEmpty(Q)) { v=dequeue(Q); topnum[v]=++ctr; for each w adjacent to v if (--indegree[w] == 0) enqueue(w,Q); } if (ctr != NumVertex) report error (‘graph cyclic!’) free queue; }

• A topological sort is an ordering of vertices in an acyclic digraph such that if there is a path from vi to vj, then vj appears after vi in the ordering. • Example: course prerequisite requirements.

*From [2] January 5, 2006

Borahan Tümer, Ph.D.

15

January 5, 2006

Borahan Tümer, Ph.D.

16

Breadth-First Search (BFS)

Breadth-First Search (BFS)

• Given a graph, G, and a source vertex, s, breadth-first search (BFS) checks to discover every vertex reachable from s. • BFS discovers vertices reachable from s in a breadth-first manner. • That is, vertices a distance of k away from s are systematically discovered before vertices reachable from s through a path of length k+1.

• To follow how the algorithm proceeds, BFS colors each vertex white gray or black. • Unprocessed nodes are colored white while vertices discovered (enountered during search) turn to gray. Vertices processed (i.e., vertices with all neighbors discovered) become black. • Algorithm terminates when all vertices are visited.

January 5, 2006

January 5, 2006

Borahan Tümer, Ph.D.

17

Borahan Tümer, Ph.D.

18

An example to BFS

Algorithm for Breadth-First Search* BFS(Graph G, Vertex s) { // initialize all vertices for each vertex uV[G]-{s} { color [u]=white; dist[u]=’; from[u]=NULL; } color[s]=gray; dist[u]=’; from[u]=NULL; Q={}; enqueue(Q,s); *From

while (!isEmpty(Q)) { u=dequeue(Q); for each v Adj[u] if (color [v]==white) { color[v]=gray; dist[v]=dist[u]+1; from[v]=u; enqueue(Q,v); } color[u]=black; } }

r ’

s 0

u ’

v ’

x ’

’ y Q

r 1 u 2

[1]

January 5, 2006

Borahan Tümer, Ph.D.

19

s 0

u 2

v 1

x 2

2 y Q

y

u

t 1

r 1

1 w

u 2

2 z z

s 0 v 1

x 2

2 y Q

u

1 w

u 2

1

1 w

u 2

x

January 5, 2006

t 1

1

1 w

2 y

2 z

v

Q

s 0

t 1

1

1 w

v

2 y Q

s 0

2 z z

Ӆ

Borahan Tümer, Ph.D.

21

z

1 w

u ’

’ y

’ z

v

t

x 2 Q

w

x ’ Q

t 1

r 1

1

1 w

u ’

2 y

’ z y

u

1 w

’ y

s 0

x

1

v

w

v

t 1

v

’ z w

t

s 0

t 1

1

1 w

v

x 2

’ z

2 y Q

t

w

Borahan Tümer, Ph.D.

x

y

20

January 5, 2006

Borahan Tümer, Ph.D.

22

Depth-First Search

DFS-visit(u) DFS(Graph G, Vertex s) { { color[u]=gray; //u just discovered // initialize all vertices time++; for each vertex uV[G] { d[u]=time; color [u]=white; for each v  Adj[u] //check edge (u,v) from[u]=NULL; if (color[v] == white) { } from[v]=u; time=0; DFS-visit(v); //recursive call for each vertex uV[G] } if (color [u]==white) color[u]=black; // u is done processing DFS-visit(u); f[u] = time++; } } *From [1] Borahan Tümer, Ph.D.

2 z u

1

s 0

• Unlike in BFS, depth-first search (DFS), performs a search going deeper in the graph. • The search proceeds discovering vertices that are deeper on a path and looks for any left edges of the most recently discovered vertex u. • If all edges of u are found, DFS backtracks to the vertex t which u was discovered from to find the remaining edges.

Algorithm for Depth-First Search*

January 5, 2006

y

r 1

r

Q

r 1

t 1

v

x ’

t 1

s 0

Depth-First Search (DFS)

x 2

2 z

x 2

January 5, 2006

r 1

z

r 1 u 2

t 1

u ’

s 0

Rest of Example r 1

’ w ’ z

2 y Q

r 1

s

v

x 2

t ’

23

• The function DFS() is a “manager” function calling

the recursive function DFS-visit(u) for each vertex in the graph. • DFS-visit(u) starts by graying the vertex u just discovered. Then it recursively visits and discovers (and hence grays) all those nodes v in the adjacency set of u, Adj[u]. At the end, u is finished processing and turns to black. • time in DFS-visit(u) time-stamps each vertex u when – u is discovered using d[u] – u is done processing using f[u]. January 5, 2006

Borahan Tümer, Ph.D.

24

An example to DFS s

r

t

r

1/

u u

t 2/

v

w

v

s 1/

Example cont’d...

r u

w

s

t

1/

2/

s

t

1/

2/

r

v

w

3/

u

v

u

s

t

1/

2/

z

y

r u

v

w

3/

x

4/5

y

s

t

1/

2/7

r

v

u

w

3/6

s

t

1/

2/

r

v

u

w

3/

s

t

1/

2/

v

x

x

4/

z

z

y

January 5, 2006

4/

r

s

t

1/10

2/7

v

v

8/ w

25

s

t 2/7

v

z

s

t 2/7

u

v

8/ w

3/6

x

4/5

z

y

January 5, 2006

z

1/

r

8/9 w

3/6

x

4/5

y

Borahan Tümer, Ph.D.

u

4/5

y

1/10

r

x

z

y

8/9 w

x

z

y

4/5

z

11/

u

w

3/

x

4/5

3/6

x

t 2/7

x

z

y

y

r

s 1/

3/6

x z

y

u

w

3/6

x

r

4/5

z

y

Borahan Tümer, Ph.D.

Example cont’d...

26

End of Example

r

s

t

r

s

t

r

s

t

r

s

t

r

s

t

r

s

t

11/

1/10

2/7

11/

1/10

2/7

11/

1/10

2/7

11/

1/10

2/7

11/

1/10

2/7

11/

1/10

2/7

u 3/6

v 12/

x

8/9 w

4/5

y

u

z

u

v

3/6

8/9 w

12/

x

4/5

z

y

3/6

x

v 12/

8/9 w

4/5

13/

y

z

u

v

3/6

r r

s

t

r

s

t

r

s

t

11/

1/10

2/7

11/

1/10

2/7

11/

1/10

2/7

u

v

3/6

12/

8/9 w

x 13/

14/

4/5

y

z

u

v

3/6

12/

8/9 w

x 13/

14/

4/5

y

z

u 3/6

11/18

u

v 12/

x 13/

8/9 w

8/9 w

12/

x 13/

3/6

u

14/15

4/5

y

z

1/10

v

z

x 13/16

27

x13/16

12/

8/9 w

14/15

4/5

y

z

t 2/7

r

s

t

11/

1/10

2/7

u 8/9 w

14/15

4/5

v

3/6

12/17

8/9 w

x13/16

14/15

4/5

y

z

z Borahan Tümer, Ph.D.

28

• Dijkstra’s algorithm solves the SSSP problem on a weighted digraph G=(V,E) assuming no negative weights exist in G. • Input parameters for Dijkstra’s algorithm

• SSSP Problem: • Given a weighted digraph G (V,E), we need to efficiently find the shortest path p*=(ui, ui+1,..., uj,..., uk-1,uk) between two vertices ui and uk. • The shortest path p* is the path with the minimum weight among all paths pl=(ui,...,uk), or

– the graph G, – the weights w, – a source vertex s.

• It uses – a set VF holding vertices with final shortest paths from the source vertex s. – from[u] and dist[u] for each vertex u Ӊ V as in BFS. – A min-heap Q

min >w( p )@ l

l

Borahan Tümer, Ph.D.

z

v

3/6

Dijkstra’s Algorithm

Single-Source Shortest Paths (SSSP)

January 5, 2006

4/5

y

12/17

January 5, 2006

8/9 w

14/15

4/5

y

Borahan Tümer, Ph.D.

w( p * )

12/

x13/16

y January 5, 2006

v

3/6

s

u

29

January 5, 2006

Borahan Tümer, Ph.D.

30

Dijkstra’s Algorithm – An Example

Dijkstra’s Algorithm r

Dijkstra(Graph G, while (!IsEmpty(Q)) { Weights w, Vertex s) u=deletemin(Q); add u to VF ; { for each vertex v Ӊ Adj(u) for each vertex uV[G] { if (dist[v]>dist[u]+w(u,v)){ dist [u]=’; dist[v]=dist[u]+w(u,v)); from[u]=NULL; from[v]=u; } } dist [u]=0; } // end of while VF = ø; } //end of function Q = all vertices u Ӊ V ; January 5, 2006

Borahan Tümer, Ph.D.

31

’

t

7

8 v

3

’

0

x

3

’

r

4

’

t

3

6

3

4

6 6

y

’

t

7

5

4

6

4 s

9

8 v

3

0

r

4

5

’

6

t

7

3

13 3

3

4

6 6

y

January 5, 2006

7

3

z

4

6

7

5 1

3

3 9 3

x

z

3 3

4

6 6

y

3

13

u

6

5 1

r

7

3

6

Borahan Tümer, Ph.D.

’

t

7

3 3

6 6

5 1

z

6

y

3

7

5 1

3

6

6 6

7

y

8

8 5 1

3

7 z

9

3 32

Resulting Shortest Paths

4

s

0

w

8

8

6

9

5

3

7

3

x

7

7

3

13

7

6

4

9

u

5

4

8 z

t

7

v

z

3

6

4 6

7

6 4

z

7 4 w

0

3

5

4

3

3

u

Borahan Tümer, Ph.D.

’

7

3

7

9

3

4 s

9

y

1

8

8

t

3

1

y

6

9

x

z

5

6

7

’

7

1

y

’

8 v

8 5

6 6

7

8

6 4

r

7 4 w

0

3

u

6

3

3

7

u

5

4

9 x

4

3

4 s

3

’

7

7

t

9

3

7 8

8

6 3

x

z

6

7 4 w

0 9

u

5

4

4 s

3

’

’

t

7 9

7

1

6 y

7

r

7 3

Note that r is not reachable from s!

z 3 33

Minimum Spanning Trees (MSTs)

January 5, 2006

• MST is

January 5, 2006

January 5, 2006

35

Borahan Tümer, Ph.D.

34

Minimum Spanning Trees (MSTs)

• Problem: • Given a connected weighted undirected graph G=(V,E), find an acyclic subset S E, such that S connects all vertices in G and the sum of the weights of the edges in S are minimum. • The solution to the problem is provided by a minimum spanning tree.

Borahan Tümer, Ph.D.

3

’

8 v

8

8

7 4 w 6

4

3

5

4

3

x

7

6

4

3

0

9

6

7

7

4 s

9 3

13

z

5 1

y

6

5

r

8

8

6 4

u

5

3

’

8 v

8

8

3

3

r

7

7 4 w 6

x

z

7 4 w

0

8 v

7

7

6

3

3

8

8

5

4

9 z

u

4 s

9

x

7 4 w 6

7

8 v

7

7

5

4 0

’

t

3

4 s

9

3

1

y

t

7

13

7

7

’

8 v

8

8

5

6 6

7 8

8

6 3

3

r

6

r

7 4 w

0

9

u

5

4

4 s

9

x

7 4 w 6

9 x

u

t

13

7

7

5

4 0

’

8 v

3

4 s

9

8 v

3

1

y

6

7 8

8

6 3

3

r

7 4 w

9 x

u

7

6

0 9

January 5, 2006

Dijkstra’s Algorithm – An Example r

3

u

5

4

4 s

9

’

’

t

7

8 v

7 4 w

3

’

3

4 0

9

3

1

4 s

9

’

5

6 y

r

’

7 4 w ’

8

’

7

8 v

x

6

6

9

u

5

’

4 s

9

– a tree since it connects all vertices by an acyclic subset of S E, – spanning since it spans the graph (connects all its vertices) – minimum since its weights are minimized.

Borahan Tümer, Ph.D.

36

Prim’s Algorithm

Prim’s Algorithm

• Prim’s algorithm operates similar to Dijkstra’s algorithm to find shortest paths. • Prim’s algorithm proceeds always with a single tree. • It starts with an arbitrary vertex t. • It progressively connects an isolated vertex to the existing tree by adding the edge with the minimum possible weight to the tree.

Prim(Graph G, while (!IsEmpty(Q)) { u=deletemin(Q); Weights w, Vertex t) for each vertex v Ӊ Adj(u) { if (vӉQ and for each vertex uV[G] { w(u,v)
January 5, 2006

January 5, 2006

Borahan Tümer, Ph.D.

37

Kruskal’s Algorithm

Borahan Tümer, Ph.D.

Kruskal(Graph G, Weights w) { for each vertex uV[G] { make each vertex to a single-element tree; } sort edges in ascending order by their weight w; for each edge (u,v) E if (u and v are in two different trees) { add (u,v) to the MST; combine both trees; } dist [u]=0; return;

39

References • [1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Introduction to Algorithms,” 2nd Edition, 2003, MIT Press • [2] M.A. Weiss, “Data Structures and Algorithm Analysis in C,” 2nd Edition, 1997, Addison Wesley

January 5, 2006

Borahan Tümer, Ph.D.

38

Kruskal’s Algorithm

• Kruskal’s Algorithm is another greedy algorithm. • It is about finding the least weight and connecting with that two trees in the forest. • Initially, there exists a forest of many singlenode trees.

January 5, 2006

Borahan Tümer, Ph.D.

41

January 5, 2006

Borahan Tümer, Ph.D.

40