1 of 57

Graphs and Traversals

1

Lecture 22

CS61B, Spring 2023 @ UC Berkeley

Josh Hug and Justin Yokota

2 of 57

Tree Definition

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

3 of 57

Tree Definition (Reminder)

A tree consists of:

  • A set of nodes.
  • A set of edges that connect those nodes.
    • Constraint: There is exactly one path between any two nodes.

​

Green structures below are trees. Pink ones are not.

4 of 57

Rooted Trees Definition (Reminder)

A rooted tree is a tree where we’ve chosen one node as the “root”.

  • Every node N except the root has exactly one parent, defined as the first node on the path from N to the root.
  • A node with no child is called a leaf.

A

B

C

A

B

C

A

C

C

B

For each of these:

  • A is the root.
  • B is a child of A. (and C of B)
  • A is a parent of B. (and B of C)

​

5 of 57

Trees

We’ve seen trees as nodes in a specific data structure implementation: Search Trees, Tries, Heaps, Disjoint Sets, etc.

6 of 57

Trees

Trees are a more general concept.

  • Organization charts.
  • Family lineages* including phylogenetic trees.
  • MOH Training Manual for Management of Malaria.

*: Not all family lineages are trees!

7 of 57

Tree Traversals

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

8 of 57

Example: File System Tree

Sometimes you want to iterate over a tree. For example, suppose you want to find the total size of all files in a folder called 61b.

  • What one might call “tree iteration” is actually called “tree traversal.”
  • Unlike lists, there are many orders in which we might visit the nodes.
    • Each ordering is useful in different ways.

hw1

synthesizer

spec

GuitarHeroLite.java

hw1.md

karplus-strong.png

...

61b

proj0

audio

data

...

...

...

...

planets.txt

23433 bytes

16180 bytes

1251 bytes

851 bytes

9 of 57

Tree Traversal Orderings

Level Order

  • Visit top-to-bottom, left-to-right (like reading in English): DBFACEG

A

C

B

D

E

F

G

10 of 57

Tree Traversal Orderings

Level Order

  • Visit top-to-bottom, left-to-right (like reading in English): DBFACEG

​

Depth First Traversals

  • 3 types: Preorder, Inorder, Postorder
  • Basic (rough) idea: Traverse “deep nodes” (e.g. A) before shallow ones (e.g. F).
  • Note: Traversing a node is different than “visiting” a node. See next slide.

​

​

​

A

C

B

D

E

F

G

11 of 57

Depth First Traversals

Preorder: “Visit” a node, then traverse its children:

A

C

B

D

E

F

G

preOrder(BSTNode x) {

if (x == null) return;� print(x.key)� preOrder(x.left)� preOrder(x.right)�}

A

B

C

D

E

F

G

12 of 57

Depth First Traversals

Preorder traversal: “Visit” a node, then traverse its children: DBACFEG

Inorder traversal: Traverse left child, visit, then traverse right child:

A

C

B

D

E

F

G

inOrder(BSTNode x) {

if (x == null) return;� inOrder(x.left)� print(x.key)

inOrder(x.right)�}

preOrder(BSTNode x) {

if (x == null) return;� print(x.key)� preOrder(x.left)� preOrder(x.right)�}

A

B

C

D

E

F

G

13 of 57

Depth First Traversals http://yellkey.com/simple

Preorder traversal: “Visit” a node, then traverse its children: DBACFEG

Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG

Postorder traversal: Traverse left, traverse right, then visit: ???????

A

C

B

D

E

F

G

postOrder(BSTNode x) {

if (x == null) return;� postOrder(x.left)

postOrder(x.right)� print(x.key)

}

  1. DBACEFG
  2. GFEDCBA
  3. GEFCABD
  4. ACBEGFD
  5. ACBFEGD
  6. Other

14 of 57

Depth First Traversals

Preorder traversal: “Visit” a node, then traverse its children: DBACFEG

Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG

Postorder traversal: Traverse left, traverse right, then visit: ACBEGFD

A

C

B

D

E

F

G

  • DBACEFG
  • GFEDCBA
  • GEFCABD
  • ACBEGFD
  • ACBFEGD
  • Other

postOrder(BSTNode x) {

if (x == null) return;� postOrder(x.left)

postOrder(x.right)� print(x.key)

}

15 of 57

A Useful Visual Trick (for Humans, Not Algorithms)

  • Preorder traversal: We trace a path around the graph, from the top going counter-clockwise. “Visit” every time we pass the LEFT of a node.
  • Inorder traversal: “Visit” when you cross the bottom of a node.
  • Postorder traversal: “Visit” when you cross the right a node.

​

Example: Post-Order Traversal

  • 4 7 8 5 2 9 6 3 1

9

4

2

1

3

6

8

5

7

16 of 57

Usefulness of Tree Traversals

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

17 of 57

What Good Are All These Traversals?

Example: Preorder Traversal for printing directory listing:

python

sc2APM

directOverlay

notes

directO.sln

directO.suo

directIO

printAPM.py

DXHookD3D11.cs

Injector.cs

18 of 57

What Good Are All These Traversals?

Example: Postorder Traversal for gathering file sizes.

python

sc2APM

directOverlay

notes

directO.sln

directO.suo

directIO

printAPM.py

DXHookD3D11.cs

Injector.cs

18381

8798

38912

881

324

874

postOrder(BSTNode x) {

if (x == null) return 0;� int total = 0;

for (BSTNode c : x.children())� total += postOrder(c)� total += x.fileSize();

return total;�}

19 of 57

What Good Are All These Traversals?

Example: Postorder Traversal for gathering file sizes.

python

sc2APM

directOverlay

notes

directO.sln

directO.suo

directIO

printAPM.py

DXHookD3D11.cs

Injector.cs

18381

8798

38912

881

324

874

postOrder(BSTNode x) {

if (x == null) return 0;� int total = 0;

for (BSTNode c : x.children())� total += postOrder(c)� total += x.fileSize();

return total;�}

27179

66972

874

68170

20 of 57

Graph Definition

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

21 of 57

Trees and Hierarchical Relationships

Trees are fantastic for representing strict hierarchical relationships.

  • But not every relationship is hierarchical.
  • Example: Paris Metro map.

​

This is not a tree: Contains cycles!

  • More than one way to get from A to B.

A

B

22 of 57

Tree Definition (Revisited)

A tree consists of:

  • A set of nodes.
  • A set of edges that connect those nodes.
    • Constraint: There is exactly one path between any two nodes.

​

Green structures on slide are trees. Pink ones are not.

23 of 57

Graph Definition

A graph consists of:

  • A set of nodes.
  • A set of zero or more edges, each of which connects two nodes.

​

Green structures below are graphs.

  • Note, all trees are graphs!

24 of 57

Graph Example: BART

Is the BART graph a tree?��

25 of 57

Graph Example: BART

Is the BART graph a tree?

  • No, has one cycle.
    • San Bruno
    • SFO
    • Millbrae��

26 of 57

Graph Definition

A simple graph is a graph with:

  • No edges that connect a vertex to itself, i.e. no “length 1 loops”.
  • No two edges that connect the same vertices, i.e. no “parallel edges”.

​

Green graph below is simple, pink graphs are not.

​

27 of 57

Graph Definition

A simple graph is a graph with:

  • No edges that connect a vertex to itself, i.e. no “loops”.
  • No two edges that connect the same vertices, i.e. no “parallel edges”.

​

In 61B, unless otherwise explicitly stated, all graphs will be simple.

  • In other words, when we say “graph”, we mean “simple graph.”

28 of 57

Graph Types

a

b

d

c

a

b

d

c

e

a

b

d

c

a

b

d

c

Acyclic:

Cyclic:

Directed

Undirected

With Edge Labels

b

d

c

e

a

1

2

3

1

29 of 57

Graph Terminology

  • Graph:
    • Set of vertices, a.k.a. nodes.
    • Set of edges: Pairs of vertices.
    • Vertices with an edge between are adjacent.
    • Optional: Vertices or edges may have labels (or weights).
  • A path is a sequence of vertices connected by edges.
    • A simple path is a path without repeated vertices.
  • A cycle is a path whose first and last vertices are the same.
    • A graph with a cycle is ‘cyclic’.
  • Two vertices are connected if there is a path between them. If all vertices are connected, we say the graph is connected.

Figure from Algorithms 4th Edition

30 of 57

Graph Example: The Paris Metro

This schematic map of the Paris Metro is a graph:

  • Undirected
  • Connected
  • Cyclic (not a tree!)
  • Vertex-labeled (each has a color).�

31 of 57

Directed Graph Example

Edge captures ‘is-a-type-of’ relationship. Example: descent is-a-type-of movement.

Not a tree!

  • Two paths from group_action to event.

32 of 57

Some Famous Graph Problems

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

33 of 57

Graph Queries

There are lots of interesting questions we can ask about a graph:

  • What is the shortest route from S to T? What is the longest without cycles?
  • Are there cycles?
  • Is there a tour you can take that only uses each node (station) exactly once?
  • Is there a tour that uses each edge exactly once?

S

T

34 of 57

Graph Queries More Theoretically

Some well known graph problems and their common names:

  • s-t Path. Is there a path between vertices s and t?
  • Connectivity. Is the graph connected, i.e. is there a path between all vertices?
  • Biconnectivity. Is there a vertex whose removal disconnects the graph?
  • Shortest s-t Path. What is the shortest path between vertices s and t?
  • Cycle Detection. Does the graph contain any cycles?
  • Euler Tour. Is there a cycle that uses every edge exactly once?
  • Hamilton Tour. Is there a cycle that uses every vertex exactly once?
  • Planarity. Can you draw the graph on paper with no crossing edges?
  • Isomorphism. Are two graphs isomorphic (the same graph in disguise)?

​

Often can’t tell how difficult a graph problem is without very deep consideration.

35 of 57

Graph Problem Difficulty

Some well known graph problems:

  • Euler Tour. Is there a cycle that uses every edge exactly once?
  • Hamilton Tour. Is there a cycle that uses every vertex exactly once?

​

Difficulty can be deceiving.

  • An efficient Euler tour algorithm O(# edges) was found as early as 1873 [Link].
  • Despite decades of intense study, no efficient algorithm for a Hamilton tour exists. Best algorithms are exponential time.

​

Graph problems are among the most mathematically rich areas of CS theory.

36 of 57

Motivation for Graph Trversals: s-t Connectivity

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

37 of 57

s-t Connectivity

Let’s solve a classic graph problem called the s-t connectivity problem.

  • Given source vertex s and a target vertex t, is there a path between s and t?

​

Requires us to traverse the graph somehow.

1

2

3

4

5

6

7

8

0

s

t

38 of 57

s-t Connectivity

Let’s solve a classic graph problem called the s-t connectivity problem.

  • Given source vertex s and a target vertex t, is there a path between s and t?

​

Requires us to traverse the graph somehow.

  • Try to come up with an algorithm for connected(s, t).

1

2

3

4

5

6

7

8

0

s

t

39 of 57

s-t Connectivity

One possible recursive algorithm for connected(s, t).

  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any neighbor v of s, return true.
  • Return false.

​

What is wrong with the algorithm above?

1

2

3

4

5

6

7

8

0

s

t

40 of 57

s-t Connectivity

One possible recursive algorithm for connected(s, t).

  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any neighbor v of s, return true.
  • Return false.

​

What is wrong with the algorithm above?

1

2

3

4

5

6

7

8

0

s

t

41 of 57

s-t Connectivity

One possible recursive algorithm for connected(s, t).

  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any neighbor v of s, return true.
  • Return false.

​

What is wrong with it? Can get caught in an infinite loop. Example:

  • connected(0, 7):
    • Does 0 == 7? No, so...
    • if (connected(1, 7)) return true;
  • connected(1, 7):
    • Does 1 == 7? No, so…
    • If (connected(0, 7)) … ← Infinite loop.

1

2

3

4

5

6

7

8

0

s

t

42 of 57

s-t Connectivity

One possible recursive algorithm for connected(s, t).

  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any neighbor v of s, return true.
  • Return false.

​

What is wrong with it? Can get caught in an infinite loop.

  • How do we fix it?

1

2

3

4

5

6

7

8

0

s

t

43 of 57

Depth First Search

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search

44 of 57

s-t Connectivity

One possible recursive algorithm for connected(s, t).

  • Mark s.
  • Does s == t? If so, return true.
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false.

​

Basic idea is same as before, but visit each vertex at most once.

  • Marking nodes prevents multiple visits.
  • Demo: Recursive s-t connectivity.

1

2

3

4

5

6

7

8

0

s

t

45 of 57

Depth First Traversal

This idea of exploring a neighbor’s entire subgraph before moving on to the next neighbor is known as Depth First Traversal or Depth First Search.

  • Example: Explore 1’s subgraph completely before using the edge 0-3.
  • Called “depth first” because you go as deep as possible.

1

2

3

4

5

6

7

8

0

s

t

46 of 57

Depth First Traversal

This idea of exploring a neighbor’s entire subgraph before moving on to the next neighbor is known as Depth First Traversal.

  • Example: Explore 1’s subgraph completely before using the edge 0-3.
  • Called “depth first” because you go as deep as possible.

1

2

3

4

5

6

7

8

0

s

t

Entirely possible for 1’s subgraph to include 3!

  • It’s still depth first, since we’re not using the edge 0-3 until the subgraph is explored.

47 of 57

From: https://xkcd.com/761/

​

48 of 57

The Power of Depth First Search (Will Cover Monday)

DFS is a very powerful technique that can be used for many types of graph problems.

​

Another example:

  • Let’s discuss an algorithm that computes a path to every vertex.
  • Let’s call this algorithm DepthFirstPaths.
  • Demo: DepthFirstPaths.

49 of 57

Tree vs. Graph Traversals

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals (will cover Monday)

Challenge: Invent Breadth First Search

50 of 57

Tree Traversals

There are many tree traversals:

  • Preorder: DBACFEG
  • Inorder: ABCDEFG
  • Postorder: ACBEGFD
  • Level order: DBFACEG

A

C

B

D

E

F

G

51 of 57

Graph Traversals

There are many tree traversals:

  • Preorder: DBACFEG
  • Inorder: ABCDEFG
  • Postorder: ACBEGFD
  • Level order: DBFACEG

A

C

B

D

E

F

G

1

2

3

4

5

6

7

8

0

s

What we just did in DepthFirstPaths is called “DFS Preorder.”

  • DFS Preorder: Action is before DFS calls to neighbors.
    • Our action was setting edgeTo.
    • Example: edgeTo[1] was set before DFS calls to neighbors 2 and 4.
  • One valid DFS preorder for this graph: 012543678
    • Equivalent to the order of dfs calls.

52 of 57

Graph Traversals

There are many tree traversals:

  • Preorder: DBACFEG
  • Inorder: ABCDEFG
  • Postorder: ACBEGFD
  • Level order: DBFACEG

A

C

B

D

E

F

G

1

2

3

4

5

6

7

8

0

s

Could also do actions in DFS Postorder.

  • DFS Postorder: Action is after DFS calls to neighbors.
  • Example: dfs(s):
    • mark(s)
    • For each unmarked neighbor n of s, dfs(n)
    • print(s)
  • Results for dfs(0) would be: 347685210
  • Equivalent to the order of dfs returns.

​

53 of 57

Graph Traversals

Just as there are many tree traversals:

  • Preorder: DBACFEG
  • Inorder: ABCDEFG
  • Postorder: ACBEGFD
  • Level order: DBFACEG

A

C

B

D

E

F

G

1

2

3

4

5

6

7

8

0

s

So too are there many graph traversals, given some source:

  • DFS Preorder: 012543678 (dfs calls).
  • DFS Postorder: 347685210 (dfs returns).

54 of 57

Graph Traversals

Just as there are many tree traversals:

  • Preorder: DBACFEG
  • Inorder: ABCDEFG
  • Postorder: ACBEGFD
  • Level order: DBFACEG

A

C

B

D

E

F

G

1

2

3

4

5

6

7

8

0

s

So too are there many graph traversals, given some source:

  • DFS Preorder: 012543678 (dfs calls).
  • DFS Postorder: 347685210 (dfs returns).
  • BFS order: Act in order of distance from s.
    • BFS stands for “breadth first search”.
    • Analogous to “level order”. Search is wide, not deep.
    • 0 1 24 53 68 7

55 of 57

Challenge: Invent Breadth First Search

Lecture 22, CS61B, Spring 2023

Trees

  • Tree Definition
  • Tree Traversals
  • Usefulness of Tree Traversals

Graphs

  • Graph Definition
  • Some Famous Graph Problems

Graph Traversals

  • Motivation: s-t Connectivity
  • Depth First Search
  • Tree vs. Graph Traversals

Challenge: Invent Breadth First Search (Will Cover Monday)

56 of 57

Shortest Paths Challenge Before Next Lecture

Goal: Given the graph above, find the length of the shortest path from s to all other vertices.

  • Give a general algorithm.
  • Hint: You’ll need to somehow visit vertices in BFS order.
  • Hint #2: You’ll need to use some kind of data structure.

Will discuss a solution in the next lecture.

0

1

2

3

4

5

6

7

s

57 of 57

Summary

Graphs are a more general idea than a tree.

  • A tree is a graph where there are no cycles and every vertex is connected.
  • Key graph terms: Directed, Undirected, Cyclic, Acyclic, Path, Cycle.

​

Graph problems vary widely in difficulty.

  • Common tool for solving almost all graph problems is traversal.
  • A traversal is an order in which you visit / act upon vertices.
  • Tree traversals:
    • Preorder, inorder, postorder, level order.
  • Graph traversals:
    • DFS preorder, DFS postorder, BFS.
  • By performing actions / setting instance variables during a graph (or tree) traversal, you can solve problems like s-t connectivity or path finding.

​

​

​

�

​

​