Graphs

CSE 332 – Section 6

Slides by James Richie Sulaeman

Graphs

A graph is a set of vertices connected by edges

• A vertex is also known as a node
• An edge is represented as a pair of vertices

Graphs

A

D

B

E

F

C

vertices

edges

example of a undirected,

unweighted, cyclic graph

• Degree of vertex V
• Number of edges connected to vertex V
• In-degree: number of edges going into vertex V
• Out-degree: number of edges going out of vertex V
• Weight of edge e
• Numerical value/cost associated with traversing edge e
• Path
• A sequence of adjacent vertices connected by edges
• Cycle
• A path that begins and ends at the same vertex

Graph Terminology

Graph Terminology (continue)

B

C

A

B

C

A

B

C

A

directed, weighted, cyclic graph

directed, unweighted, acyclic graph

undirected, unweighted, acyclic graph

B

C

A

undirected, weighted, cyclic graph

• Directed vs. undirected graphs
• Edges can have direction (i.e. bidirectional vs. unidirectional)
• Weighted vs. unweighted graphs
• Edges can have weights/costs (e.g. how many minutes to go from vertex A to B)
• Cyclic vs. acyclic graphs
• Graph contains a cycle

5

3

7

1

3

5

7

Graph Traversals

• Depth First Search (DFS)
• Visit all nodes reachable by a neighbor before another
• Can be implemented recursively/by using a stack
• O(|V| + |E|) runtime

Graph Traversals

Depth First Search (DFS)

Breadth First Search (BFS)

• Breadth First Search (BFS)
• Explores the graph level by level
• Implemented using a queue
• Finds the shortest path in an unweighted graph
• O(|V| + |E|) runtime

How do we iterate through a graph?

(not recommend)

Depth First Search

DFS(Graph g, Vertex curr):

mark curr as visited

​

for (v : neighbors(current)):

if (!v marked “visited”)

DFS(g, v)

mark curr as “done”;

​

• Explores the graph: visiting all nodes reachable by one neighbor before selecting another. (as deep as possible)
• Implemented recursively/by using a stack
• O(|V| + |E|) runtime

Depth First Search (DFS)

(not recommend)

Breadth First Search

BFS(Vertex start):

initialize queue q to hold start

mark start as visited

​

while q is not empty:

vertex v = q.dequeue()

​

for each neighbour u of v:

if u is not visited:

mark u as visited

predecessor[u] = v

add u to q

• Explores the graph level by level
• Implemented using a queue
• Finds the shortest path in an unweighted graph
• O(|V| + |E|) runtime

Breadth First Search (BFS)

Problem 0

BFS(Vertex start):

initialize queue q to hold start

mark start as visited

​

while q is not empty:

vertex v = q.dequeue()

​

for each neighbour u of v:

if u is not visited:

mark u as visited

predecessor[u] = v

add u to q

Problem 0 (1)

S

T

Z

X

Y

Queue:

front

back

• Initialize queue to hold starting vertex S

• Mark vertex S as visited

S

S

T

Z

X

Y

Queue:

front

back

• Dequeue vertex S

• Add neighbors T, Y to the queue

S

Y

T

S

Problem 0 (2)

S

T

Z

X

Y

Queue:

front

back

• Dequeue vertex T

• Add neighbors X, Z to the queue

(ignore Y since already visited)

S

Y

T

Z

X

T

Problem 0 (3)

S

T

Z

X

Y

Queue:

front

back

• Dequeue vertex Y

• Add neighbors to the queue

(nothing happens since all already visited)

S

Y

T

Z

X

Y

Problem 0 (4)

S

T

Z

X

Y

Queue:

front

back

• Dequeue vertex X

• Add neighbors to the queue

(nothing happens since all already visited)

S

Y

T

Z

X

X

Problem 0 (5)

S

T

Z

X

Y

Queue:

front

back

• Dequeue vertex Z

• Add neighbors to the queue

(nothing happens since all already visited)

S

Y

T

Z

X

Z

Problem 0 (6)

S

T

Z

X

Y

Queue:

front

back

• Queue is empty; we are done

S

Y

T

Z

X

Problem 0 (7)

BFS Table Interpretation

BFS Table Interpretation

​

​

• A path exists if and only if the target node has a predecessor in the table

​

How to find a path from the start node to a target node?

• Locate the target node in the table
• Backtrack through its predecessors until you reach the start node
• The sequence of predecessors form a path from the start to the target
• Will be the shortest path by edge count (but not necessarily sum of edge costs)

How to check if a path exists from the start node to a target node?

Problem 1

DFS(Graph g, Vertex curr):

mark curr as visited

​

for (v : neighbors(current)):

if (!v marked “visited”)

DFS(g, v)

mark curr as “done”;

Problem 1 (1)

S

T

Z

X

Y

StackFrame (curr):

• Build stack frame of dfs(g, S)

• Mark vertex S as visited

S

S

T

Z

X

Y

StackFrame (curr):

• S Call dfs on unvisited neighbor T

• Mark vertex T as visited

S

T

Problem 1 (2)

S

T

Z

X

Y

StackFrame (curr):

• T Call dfs on unvisited neighbor X

• Mark vertex X as visited

T

X

Problem 1 (3)

S

T

Z

X

Y

StackFrame (curr):

• No recursive call in X: all neighbors are visited

• Mark vertex X as done, exit X stack frame

Problem 1 (4)

S

T

Z

X

Y

StackFrame (curr):

• T Call dfs on unvisited neighbor Y

• Mark vertex Y as visited

T

Y

Problem 1 (5)

S

T

Z

X

Y

StackFrame (curr):

• Y Call dfs on unvisited neighbor Z

• Mark vertex Z as visited

Y

Z

Problem 1 (6)

S

T

Z

X

Y

StackFrame (curr):

• No recursive call in Z: all neighbors are visited

• Mark vertex Z as done, exit Z stack frame

Problem 1 (7)

S

T

Z

X

Y

StackFrame (curr):

• Finish all recursive in Y: all neighbors are visited

• Mark vertex Y as done, exit Y stack frame

Problem 1 (8)

S

T

Z

X

Y

StackFrame (curr):

• Finish all recursive in T: all neighbors are visited

• Mark vertex T as done, exit T stack frame

Problem 1 (9)

S

T

Z

X

Y

StackFrame (curr):

• Finish all recursive in S: all neighbors are visited

• Mark vertex S as done, exit S stack frame

Problem 1 (10)

BFS/DFS Useful Properties

BFS - Shortest Path

• BFS always returns the shortest path from source to any other vertex by edge count!
• Intuition:
• Each step push neighbors that are one edge away, onto a queue.
• Because we use a queue, we must process the vertices 1 edge away, before vertices farther away
• Each vertex’s predecessor in the table is the one which initially pushes it onto the queue (earliest/shortest path)

​

DFS - Cycle Detection

• DFS can be used to detect cycles in graphs
• Intuition:
• Each step push neighbors that are one edge away from the current node onto a stack.
• Because we use a stack, we process the vertices further away, before the vertices close to the source
• If we ever see a vertex to a node currently on the stack, we know a back edge and thus a cycle exists

​

Start from A

Detect Cycle Examples

• Use DFS to detect cycle by finding a back edge
• a back edge is an edge that connects a node to one of its ancestors in the current recursion stack.

A

E

B

D

C

Vertex: B

Vertex: B

Mark B as visited

Vertex: A

Vertex: A

Mark A as visited

A

E

B

D

C

Start from A

No Cycle Example

__ - Visited

__ - Done

​

A

B

Vertex: B

Mark B as done

B

C

Vertex: C

Mark C as visited

D

Vertex: D

Mark D as visited

E

Vertex: E

Mark E as visited

E

Vertex: E

Mark E as done

D

Vertex: D

Mark D as done

C

Vertex: C

Mark C as done

A

Vertex: A

Mark A as done

A

D

E

C

B

Start from A

Vertex: A

Vertex: B

Vertex: C

Mark C as visited

Vertex: D

Mark D as visited

Vertex: B

Mark B as visited

Vertex: C

Mark C as visited

Vertex: D

Mark as done

Edge points to a visited node, back edge detected!

Vertex: A

Mark A as visited

Vertex: E

Mark E as visited

Vertex: B

Go to next unvisited

With Cycle Example

A

B

C

D

D

E

Vertex: C

Mark C as done

C

B

Vertex: E

Mark E as done

E

A

Vertex: A

Mark A as done

Vertex: B

Mark B as done

Problem 2: Detecting Cycles

Problem 2 (0)

S

X

Y

Z

U

• Build stack frame of dfs(g, S)

• Mark vertex S as visited

S

StackFrame (curr):

U

Problem 2 (1)

S

X

Y

Z

U

StackFrame (curr):

• S Call dfs on unvisited neighbor U

• Mark vertex U as visited

S

U

Problem 2 (2)

S

X

Y

Z

StackFrame (curr):

• No recursive call in U: all neighbors are visited

• Mark vertex U as done

S

U

Problem 2 (3)

S

X

Y

Z

X

StackFrame (curr):

• S Call dfs on unvisited neighbor X

• Mark vertex X as visited

S

U

Problem 2 (4)

S

X

Y

Z

Y

StackFrame (curr):

• X Call dfs on unvisited neighbor Y

• Mark vertex Y as visited

S

• Check neighbors of Y: back edge to X detected

U

Problem 2 (5)

S

X

Y

Z

StackFrame (curr):

• Y Call dfs on unvisited neighbor Z

• Mark vertex Z as visited

S

• Check neighbors of Z: back edge to S and X detected

Z

U

Problem 2 (6)

S

X

Y

Z

StackFrame (curr):

• No recursive call in Z: all neighbors are visited

• Mark vertex Z as done

S

U

Problem 2 (7)

S

X

Y

Z

StackFrame (curr):

• Finish all recursive in Y: all neighbors are visited

• Mark vertex Y as done

S

U

Problem 2 (8)

S

X

Y

Z

StackFrame (curr):

• Finish all recursive in X: all neighbors are visited

• Mark vertex X as done

S

U

S

X

Y

Z

StackFrame (curr):

• Finish all recursive in S: all neighbors are visited

• Mark vertex S as done

S

Problem 2 (9)

Dijkstra’s Algorithm

(Shortest Path)

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w // cost of best path to u through v

currBest = u.cost // cost of current best path to u

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

Dijkstra’s Algorithm

Dijkstra’s algorithm finds the minimum-cost path from a source vertex to every other vertex in a non-negatively weighted graph

• O(|V| log |V| + |E| log |V|) runtime

Problem 3

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w

currBest = u.cost

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

Problem 3 (1)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

• Initialize each vertex as unvisited with cost ∞

• Set cost of source vertex A to 0

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

A

1

8

16

13

50

• Select unvisited vertex with lowest cost (A)

• Mark A as visited

• Process each outgoing edge

Problem 3 (2)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

3

13

A

F

• Select unvisited vertex with lowest cost (F)

• Mark F as visited

• Process each outgoing edge

Problem 3 (3)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

5

E

A

• Select unvisited vertex with lowest cost (E)

• Mark E as visited

• Process each outgoing edge

F

Problem 3 (4)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

B

A

• Select unvisited vertex with lowest cost (B)

• Mark B as visited

• Process each outgoing edge

F

E

• No outgoing edges; continue

Problem 3 (5)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

2

D

A

• Select unvisited vertex with lowest cost (D)

• Mark D as visited

• Process each outgoing edge

(ignore D→B since B is already visited)

F

E

B

6

Problem 3 (6)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

7

C

A

• Select unvisited vertex with lowest cost (C)

• Mark C as visited

• Process each outgoing edge

(ignore C→B & C→E since B & E are already visited)

​

F

E

B

D

• No outgoing edges to unvisited nodes; continue

3

Problem 3 (7)

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

A

F

E

B

D

C

• No more unvisited nodes; we are done

Problem 3 (8)

Problem 4

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w

currBest = u.cost

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

Problem 4 (1)

B

A

D

E

F

C

5

3

-5

10

4

60

70

80

90

6

7

• Initialize each vertex as unvisited with cost ∞

• Set cost of source vertex A to 0

B

A

D

E

F

C

5

3

-5

10

4

60

70

80

90

6

7

• Initialize each vertex as unvisited with cost ∞

• Set cost of source vertex A to 0

Problem 4 (2)

Thank You!