Graph

Chapter 7: Graphs • Terminology • Storage structures • Operations and algorithms • Minimum spanning trees • Shortest paths • Other well-known problems

1

Graphs • Each node may have multiple predecessors as well as multiple successors. • Graphs are used to represent complex networks and solve related problems.

2

Terminology verte x B

verte x

A

arcs

E

B

A

edge

E

F C

D

Directed graph

F C

D

Undirected graph 3

Terminology • Adjacent vertices: there exists an edge that directly connects them. • Path: a sequence of vertices in which each vertex is adjacent to the next one. • Connected: there is a path from any vertex to any other vertex.

4

Graph Storage Structures • Adjacency matrix

A

B

E F

C

D

A

A

A B C D E F0 1 0 0 0 0

B

B

0

0

1

0

1

0

C

C

0

0

0

1

1

0

D

D

0

0

0

0

0

0

E

E

0

0

0

1

0

1

F

F

0

0

0

0

0

0

verte x vector

adjacency matrix 5

Graph Storage Structures • Adjacency matrix A

B

E F

C

D

A

A

A B C D E F0 1 0 0 0 0

B

B

1

0

1

0

1

0

C

C

0

1

0

1

1

0

D

D

0

0

1

0

1

0

E

E

0

1

1

1

0

1

F

F

0

0

0

0

1

0

verte x vector

adjacency matrix 6

Graph Storage Structures • Adjacency List A

B

E F

C

D

A

B

B

A

C

E

C

B

D

E

D

C

E

E

B

C

F

E

verte x vector

D

adjacency list

F

7

Graph Data Structure count first graphHea d nextVert data ex graphVerte x dest nextArc

inDegre outDegr e ee

B

A

processe d

C

arc

E

graphArc 8

Graph Data Structure graphHead count graphVertex> first <pointer to graphVertex> graphArc> end graphHead

graphArc dest <pointer to nextArc <pointer to end graphArc

graphVertex nextVertex <pointer to graphVertex> data inDegree outDegree processed <0, 1, 2> arc <pointer to graphArc>

9

Operations • Insert vertex • Delete vertex • Insert arc/edge • Delete arc/edge • Traverse graph

10

Create Graph Algorithm createGraph (ref graph <metadata>) Initializes the metadata elements of a graph structure Pre Post

graph is metadata structure metadata elements have been initialized

1 count = 0 2 first = null End createGraph

11

Insert Vertex Algorithm

insertVertex (ref graph <metadata>, val dataIn )

Allocates memory for a new vertex and copies the data to it Pre

graph is a graph head structure dataIn contains data to be inserted into vertex

Post

new vertex allocated and data copied

Return +1 if successful −1 if memory overflow

12

Insert Vertex 1 allocate (newPtr) 2 if (allocation not successful) 1 return −1 3 else Initializes the new vertex 1 newPtr -> nextVertex = null 2 newPtr -> data = dataIn 3 newPtr -> inDegree = 0 4 newPtr -> outDegree = 0 5 newPtr -> processed = 0 6 newPtr -> arc = null 7 graph.count = graph.count + 1 13

Insert Vertex 8 locPtr = graph.first 9 if (locPtr = null) Empty graph. Insert at the beginning 1 graph.first = newPtr 10 else 1 predPtr = null 2 loop (locPtr ≠ null AND dataIn.key > locPtr -> data.key) 1 predPtr = locPtr 2 locPtr = locPtr -> nextVertex 3 if (predPtr = null) 1 graph.first = newPtr else 1 predPtr -> nextVertex = newPtr 4 newPtr -> nextVertex = locPtr 11 return +1 14 End insertVertex

Delete Vertex Algorithm

deleteVertex (ref graph <metadata>, val key )

Deletes an existing vertex only if its degree is 0 Pre

graph is a graph head structure key is the key of the vertex to be deleted

Post

vertex deleted

Return +1 if successful −1 if degree ≠ 0 −2 if key not found

15

Delete Vertex 1 if (graph.first = null) 1 return −2 Locate vertex to be deleted 2 predPtr = null 3 locPtr = graph.first 4 loop (locPtr ≠ null AND key > locPtr -> data.key) 1 predPtr = locPtr 2 locPtr = locPtr -> nextVertex 5 if (locPtr = null OR key ≠ locPtr -> data.key) 1 return −2 16

Delete Vertex Found vertex to be deleted. Test degree. 6 if (locPtr -> inDegree > 0 OR locPtr -> outDegree > 0) 1 return −1 OK to delete vertex. 7 if (predPtr = null) 1 graph.first = locPtr -> nextVertex 8 else 1 predPtr -> nextVertex = locPtr -> nextVertex 9 graph.count = graph.count − 1 10 recycle (locPtr) 11 return +1 End deleteVertex

17

Insert Arc Algorithm

insertArc (ref graph <metadata>, val fromKey , val toKey )

Add an arc between two vertices Pre

graph is a graph head structure fromKey is the key of the source vertex toKey is the key of the destination vertex

Post

arc added to adjacency list

Return +1 if successful −1 if memory overflow −2 if fromKey not found −3 if toKey not found

18

Insert Arc 1 allocate (newArcPtr) 2 if (allocation not successful) 1 return −1 Locate source vertex 3 fromPtr = graph.first 4 loop (fromPtr ≠ null AND fromKey > fromPtr -> data.key) 1

fromPtr = fromPtr -> nextVertex

5 if (fromPtr = null OR fromKey ≠ fromPtr -> data.key) 1

return −2

19

Insert Arc Locate destination vertex 6 toPtr = graph.first 7 loop (toPtr ≠ null AND toKey > toPtr -> data.key) 1 toPtr = toPtr -> nextVertex 8 if (toPtr = null OR toKey ≠ toPtr -> data.key) 1

return −3

Insert new arc 9 fromPtr -> outDegree = fromPtr -> outDegree + 1 10 toPtr -> inDegree = toPtr -> inDegree + 1 11 newArcPtr -> dest = toPtr

20

Insert Arc 12 if (fromPtr -> arc = null) Inserting first arc 1 fromPtr -> arc = newArcPtr 2 newArcPtr -> nextArc = null 3 return +1 13 else Find insertion point in adjacency list 1 arcPredPtr = null 2 arcWalkPtr = fromPtr -> arc 3 loop (arcWalkPtr ≠ null AND toKey > arcWalkPtr -> dest -> data.key) 1 arcPredPtr = arcWalkPtr 2 arcWalkPtr = arcWalkPtr -> nextArc

21

Insert Arc 14 if (arcPredPtr = null) Insertion before first arc 1 fromPtr -> arc = newArcPtr 15 else 1 arcPredPtr -> nextArc = newArcPtr 17 newArcPtr -> nextArc = arcWalkPtr 16 return +1 End insertArc

22

Delete Arc Algorithm

deleteArc (ref graph <metadata>, val fromKey , val toKey )

Add an arc between two vertices Pre

graph is a graph head structure fromKey is the key of the source vertex toKey is the key of the destination vertex

Post

arc added to adjacency list

Return +1 if successful −2 if fromKey not found −3 if toKey not found 23

Delete Arc 1 if (graph.first = null) 1 return −2 Locate source vertex 3 fromVertex = graph.first 4 loop (fromVertex ≠ null AND fromKey > fromVertex -> data.key) 1 fromVertex = fromVertex -> nextVertex 5 if (fromVertex = null OR fromKey ≠ fromVertex -> data.key) 1 return −2

24

Delete Arc Locate destination vertex in adjacency list 6 if (fromVertex -> arc = null) 1 return −3 7 prePtr = null 8 arcPtr = fromVertex -> arc 9 loop (arcPtr ≠ null AND toKey > arcPtr -> dest -> data.key) 1 predPtr = arcPtr 2 arcPtr = arcPtr -> nextArc 10 if (arcPtr = null OR toKey < arcPtr -> dest -> data.key) 1 return −3

25

Delete Arc Delete arc 11 fromVertex -> outDegree = fromVertex -> outDegree − 1 12 toVertex -> inDegree = toVertex -> inDegree − 1 13 if (prePtr = null) Deleting first arc 1 fromVertex -> arc = arcPtr -> nextArc 14 else 3 prePtr -> nextArc = arcPtr -> nextArc 15 recycle (arcPtr) 16 return +1 End deleteArc 26

Graph Traversal • Depth-first: all of a vertex's descendents are processed before an adjacent vertex. A

X

A X H P E Y M J G

H

Y E

G

P

M

J 27

Graph Traversal A X H P E Y M J G

A

X

H

Y E

G

A

X

P

H G

P E G

M

E G

Y M G

J

M G

J G

G

stack 28

Graph Traversal • Breadth-first: all adjacent vertices are processed before the descendents of a vertex. A

X

A X G H P E M Y J

H

Y E

G

P

M

J 29

Graph Traversal A X G H P E M Y J

A

X

H

Y E

G

A

X

P

GH

HP

M

PE

queu e

E

J

MY

YJ

J

30

Networks • Graph whose edges are weighted (weighted graph). 623

B 200

A 345

548

C

D 360

467

245 E

320 F 555

31

Network Structures • Adjacency matrix A

B

C

D

E

F

A

A

0

623

345

0

0

0

B

B

623

0

200

0

0

C

C

345

200

0

D

0

548

360

E

E

0

0

467

46 7 24 5 0

0

D

54 8 36 0 0

F

F

0

0

0

verte x vector

24 5 32 0

55 5

32 0 55 5 0

adjacency matrix 32

Network Structures • Adjacency List A

B 623

B

A 623

C 200

D 548

C

A 345

B 200

D 360

E 467

D

B 548

C 360

E 245

F 320

E

C 467

D 245

F 555

F

D 320

E 555

verte x vector

adjacency list

33

Minimum Spanning Tree • Spanning tree: tree that contains all of the vertices in a connected graph. • Minimum spanning tree: spanning tree such that the sum of its weights are minimal.

34

Minimum Spanning Tree • Applications?

35

Minimum Spanning Tree • There are various algorithms to find the minimum spanning tree: e.g. Prim’s

36

6

5

B 2

A 3

6

C

3

5 2

3

6

C

2

A 3

C

2

3

4

6

5

5

C

3

3 F 5

D

3 2

E 4

5

2

3

C

F

E

5 2

3

2

D

4

B

3

E

4

B

A

D 3

2 3

F

C

A

3 2

E

6

5

D

2 3

F

B

A

3

E

5

F 5

D

4

B

2

3

6

3

E

4

B

A

D

5

F 5 37

already in tree

B

5

D F

3

A C

4

E B

min edge

5

D F

3

A C

4

X

E

38

Minimum Spanning Tree Prim’s algorithm: Tree = {first vertex}

v

u

Loop (Tree is not complete) minWeight = +∞ For every v∈Tree For every u∉Tree and adjacent(v, u) If weight(v, u) < minWeight minWeight = weight(v, u) minEdge = (v, u) Add minEdge to Tree 39

Spanning Tree Data Structure graphHead count graphVertex> first <pointer to graphVertex> graphEdge> end graphHead

graphEdge destination <pointer to nextEdge <pointer to inTree weight end graphEdge

graphVertex nextVertex <pointer to graphVertex> data inDegree outDegree inTree edge <pointer to graphEdge> end graphHead

40

Algorithm spanningTree (val graph ) /* Prim’s algorithm */ Determines the minimum spanning tree of a network Pre graph is a graph head structure Post minimum spanning tree determined 1 if (empty graph) 1 return 2 vertexPtr = graph.first 3 loop (vertexPtr not null) set inTree flag false 1 vertexPtr −> inTree = false 2 edgePtr = vertexPtr −> edge 3 loop (edgePtr not null) 1 edgePtr -> inTree = false 2 edgePtr = edgePtr -> nextEdge 4 vertexPtr = vertexPtr -> nextVertex Now derive minimum spanning tree 4 vertexPtr = graph.first 5 vertexPtr -> inTree = true 6 treeComplete = false 41

7

loop (not treeComplete) 1 treeComplete = true 2 chkVertexPtr = vertexPtr 3 minEdge = +∝ 4 minEdgePtr = null 5 loop (chkVertexPtr not null) Walk thru graph checking vertices in tree 1 if (chkVertexPtr -> inTree = true AND chkVertexPtr -> outDegree > 0) 1 edgePtr = chkVertexPtr -> edge 2 loop (edgePtr not null) 1 if (edgePtr -> destination -> inTree = false) 1 treeComplete = false 2 if (edgePtr -> weight < minEdge) 1 minEdge = edgePtr -> weight 2 minEdgePtr = edgePtr 2 edgePtr = edgePtr -> nextEdge 2 chkVertexPtr = chkVertexPtr -> nextVertex 6 if (minEdgePtr not null) Found edge to insert into tree 1 minEdgePtr -> inTree = true 2 minEdgePtr -> destination -> inTree = true 8 return 42 End spanningTree

Shortest Path • Find the shortest path between any two vertices in a network.

43

Shortest Path • Applications?

44

Shortest Path • There are various algorithms: e.g. Dijkstra's algorithm (1959).

45

5

B

6

2

A 3

C 5

B

D 3

2

5

A 3 5

C

B

4

5 3 2

F

5 3 F

3

C

E

4

B

2

F 5

E

D

6

3

C

B

4

F 5

E

D

6 9 F

A

5 7

3

3

2 3

6

A

C

D

A

5

E

D

2

A 3

D 3

F 5

E

4

B

6

3

5

3

C

E

7

46

Shortest Path • Select the source vertex • Loop until all vertices are in the tree: Consider the adjacent vertices of the vertices already in the tree.

v

u

Examine all the paths from those adjacent vertices to the source vertex. Select the shortest path and insert the corresponding adjacent vertex into the tree.

47

Shortest Path Dijkstra’s algorithm: Tree = {source vertex} v Loop (Tree is not complete) minPathLen = +∞ For every v∈Tree minWeight = +∞ For every u∉Tree and adjacent(v, u) If weight(v, u) < minWeight minWeight = weight(v, u) minEdge = (v, u) If pathLenFrom(v) + minWeight < minPathLen minPathLen = pathLenFrom(v) + minWeight shortestPath = pathFrom(v) + minEdge Add shortestPath to Tree

u

48

Shortest Path Data Structure graphHead count graphVertex> first <pointer to graphVertex> graphEdge> end graphHead

graphEdge destination <pointer to nextEdge <pointer to inTree weight end graphEdge

graphVertex nextVertex <pointer to graphVertex> data inDegree outDegree inTree pathLength /* shortest path to the source vertex */ edge <pointer to graphEdge>

49

Shortest Path Algorithm Algorithm shortestPath (val graph ) /* Dijkstra's algorithm */ Determines the shortest path from the first vertex to other vertices Pre graph is a graph head structure Post minimum path tree determined 1 if (empty graph) 1 return 2 vertexPtr = graph.first 3 loop (vertexPtr not null) initialize inTree flags & path length 1 vertexPtr −> inTree = false 2 vertexPtr -> pathLength = +∝ 3 edgePtr = vertexPtr −> edge 4 loop (edgePtr not null) 1 edgePtr -> inTree = false 2 edgePtr = edgePtr -> nextEdge 5 vertexPtr = vertexPtr -> nextVertex 50

4 5 6 7 8

5 Now derive minimum path tree 5 B vertexPtr = graph.first vertexPtr -> inTree = true 3 vertexPtr -> pathLength = 0 A treeComplete = false loop (not treeComplete) C 3 1 treeComplete = true 4 2 chkVertexPtr = vertexPtr 3 minEdgePtr = null /* to a vertex already in the tree */ 4 minPathPtr = null /* to the source vertex */ 5 newPathLen = +∝

D

3 2

E

F 5

51

6

loop (chkVertexPtr not null) Walk thru graph checking vertices in tree 1 if (chkVertexPtr -> inTree = true AND chkVertexPtr -> outDegree >

0) 1 2 3 4

9

edgePtr = chkVertexPtr -> edge chkPath = chkVertexPtr -> pathLength minEdge = +∝ loop (edgePtr not null) 1 if (edgePtr -> destination -> inTree = false) 1 treeComplete = false 2 if (edgePtr -> weight < minEdge) 1 minEdge = edgePtr -> weight 2 minEdgePtr = edgePtr 2 edgePtr = edgePtr -> nextEdge Test for shortest path 5 if (chkPath + minEdge < newPathLen) 1 newPathLen = minPath + minEdge 2 minPathPtr = minEdgePtr 2 chkVertexPtr = chkVertexPtr -> nextVertex 7 if (pathPtr not null) Found edge to insert into tree 1 minPathPtr -> inTree = true 2 minPathPtr -> destination -> inTree = true 3 minPathPtr -> destination -> pathLength = newPathLen return

End shortestPath

52

Shortest Path • What if a negative weight? 6

5

B -10

A 3

C

D 3

4

3 2

E

F 5

53

Shortest Path • What if a negative weight? 6

5

B -10

A 3

C

D 3

4

3 2

E

F 5

FAIL!

54

Shortest Path • What if a directed graph? 6

5

B 2

A 3

C

D 3

4

3 2

E

F 5

55

Maximum Flows • A network of water pipelines from one source to one destination. • Water is pumped thru many pipes with many stations in between. • The amount of water that can be pumped may differ from one pipeline to another.

56

Maximum Flows • The flow thru a pipeline cannot be greater than its capacity. • The total flow coming to a station is the same as the total flow coming from it.

57

Maximum Flows • The flow thru a pipeline cannot be greater than its capacity. • The total flow coming to a station is the same as the total flow coming from it. The problem is to maximize the total flow coming to the destination.

58

Maximum Flows A

2

B

C

1 E

3

5

2 4

S

5

3

2 3

D

F

2

T 1

59

Maximum Flows A

2

B

C

1 E

3

5

2 4

S

5

3

2 3

D

2

T 1

F

A

2

B

C

1 E

3

0

1 2

S

3

1

1 0

D

F

1

T 1 60

Matching • Applicants:

p

• Suitable jobs: a b c de

q

r

bd

ae

s e

t c

• No applicant is accepted for two jobs, and no job is assigned to two applicants.

61

Matching • Applicants:

p

• Suitable jobs: a b c de

q

r

bd

ae

s e

t c

• No applicant is accepted for two jobs, and no job is assigned to two applicants. The problem is to find a worker for each job. 62

Matching • Applicants:

p

• Suitable jobs: a b c de

q

r

s

bd

ae

e

p

q

r

s

t

a

b

c

d

e

t c

63

Matching • Applicants:

p

• Suitable jobs: a b c de

q

r

s

bd

ae

e

p

q

r

s

t

a

b

c

d

e

t c

64

Matching • Maximum matching: as many pairs of worker-job as possible. • Perfect matching (marriage problem): no worker or job left unmatched.

65

Graph Coloring • Given a map of adjacent regions. • Find the minimum number of colors to fill the regions so that no adjacent regions have the same color.

66

Graph Coloring

67

Graph Coloring

68

Graph Coloring The problem is to find the minimum number of sets of non-adjacent vertices.

69

Graph Coloring The problem is to find the minimum number of sets of non-adjacent vertices.

70