1 of 30

Graphs

CS61B Spring 2019 Discussion 11

2 of 30

Administrivia

  • HW 4 due 4/10
  • Update on Proj2ab scores soon

3 of 30

Graph Basics

Graphs are data structures that have 2 components:

  1. Nodes (or vertices)
  2. Edges

Path

Cycle

a

a

b

a

b

a

b

Directed

Undirected

a

b

d

c

a

b

d

c

4 of 30

Undirected

Directed

Directed with edge weights

5 of 30

How to represent a graph

  1. Adjacency Matrix

​

​

2. Adjacency list

​

​

3. List of edges: (0, 1), (1, 2), (0, 2)

0

1

2

​

0

1

2

0

0

1

1

1

0

0

1

2

0

0

0

0

1

2

[1, 2]

[2]

6 of 30

Runtimes

idea

addEdge(s, t)

for(w : adj(v))

printgraph()

hasEdge(s, t)

space used

adjacency matrix

Θ(1)

Θ(V)

Θ(V2)

Θ(1)

Θ(V2)

list of edges

Θ(1)

Θ(E)

Θ(E)

Θ(E)

Θ(E)

adjacency list

Θ(1)

Θ(1) to Θ(V)

Θ(V+E)

Θ(degree(v))

Θ(E+V)

7 of 30

Graph Traversals: DFS

DFS traversal of a graph is very similar to DFS traversal of a tree. The only difference is, since graphs can have cycles, you need to prevent your function from visiting nodes that have already been visited in an effort to avoid infinite loops.

​

​

​

​

​

PreOrder: Process the node when you first visit it

PostOrder: Process the node the last time you visit it.

​

​

​

8 of 30

Graph Traversals: BFS

​

BFS differs from DFS in that instead of exploring a path all the way to the end, it takes a layer-by-layer approach

BFS pseudocode is exactly the same as DFS except with a Queue instead of a stack!

This is actually really cool, because it means we can recycle the entire algorithm but get a completely different traversal!

BFS also has the cool feature of finding the shortest path from one node to all other nodes in terms of number of edges.

9 of 30

Topological Sort

  • Topological sort is a sort such that for each directed edge, u to v, u comes before v in the sort.
  • Analogy: an edge from Class A to Class B means A is a prereq of B. A topological sort is an ordering of classes to take such that when you take a class, you’ve already taken the prereqs.
  • How do we find the topological sort step by step ?
    • 1. Find a node with no incoming edges (in-degree of 0). These nodes are referred to as “sources". The first vertex in a topological sort MUST be a source!
    • 2. Process the vertex, then decrease the in-degree of its neighbors by 1. You can do this by either removing the node from the graph altogether (destructive) or manually decreasing the in-degrees of its neighbors (non-destructive).
    • 3. Mark the node as visited or processed
    • 4. Repeat starting from step 1 until all nodes have been visited.

​

​

10 of 30

Berkeley CS courses Topological Sort

Give a valid topological sort for a student who is on the software track (light blue) given that they would need to take all of the red and blue classes.

11 of 30

Problem 1.1

12 of 30

Problem 1.1 SOLUTION

13 of 30

Problem 2.1

14 of 30

Problem 2.1 SOLUTION

Hint: A valid topological sorting can be obtained by reversing the DFS postorder.

15 of 30

Problem 2.1 SOLUTION

Hint: A valid topological sorting can be obtained by reversing the DFS postorder.

16 of 30

Problem 2.2

17 of 30

Problem 2.2 SOLUTION

Hint: How is order defined in the graph

18 of 30

Problem 2.2 SOLUTION

Hint: How is order defined in the graph

19 of 30

Problem 2.2 SOLUTION

Hint: How is order defined in the graph

20 of 30

Problem 2.3

21 of 30

Problem 2.3 SOLUTION

Hint: Consider every possible situation in which dfs could be called.

For any edge (u,v), what happens when dfs(u) is called

22 of 30

Problem 2.3 SOLUTION

Hint: Consider every possible situation in which dfs could be called.

For any edge (u,v), what happens when dfs(u) is called

23 of 30

Problem 2.3 SOLUTION

Hint: Consider every possible situation in which dfs could be called.

For any edge (u,v), what happens when dfs(u) is called

24 of 30

Problem 2.3 SOLUTION

Hint: Consider every possible situation in which dfs could be called.

For any edge (u,v), what happens when dfs(u) is called

25 of 30

Problem 3.1

right

26 of 30

Problem 3.1 SOLUTION

27 of 30

Problem 3.2

28 of 30

Problem 3.2 SOLUTION

29 of 30

Problem 3.3

30 of 30

Problem 3.3 SOLUTION