CSE 373 AX SP25 Section 7
Graphs!!! Woo!
Graph Types - Warm Up Question
a
b
d
c
a
b
d
c
e
a
b
d
c
a
b
d
c
Word Bank:
A
B
C
D
Which graphs are associated
with each category below?
Check-in
What's one place you want to visit? Alternatively, can you name all these places?
Announcements
Resources
Graph Traversal (DFS)
Graph Traversal: DFS
DFS Pseudocode (Iterative)
dfs(Graph graph, Vertex start) {
// stores the remaining vertices to visit in the DFS
Stack<Vertex> perimeter = new Stack<>();
// stores the set of visited vertices so we don't revisit them multiple times
Set<Vertex> visited = new Set<>();
// kicking off our starting point by adding it to the perimeter
perimeter.add(start);
while (!perimeter.isEmpty()) {
Vertex from = perimeter.remove();
if (!visited.contains(from)) {
for (E edge : graph.outgoingEdgesFrom(from)) {
Vertex to = edge.to();
perimeter.add(to);
}
visited.add(from);
}
}
}
Graph Traversal: DFS (HTML Graph)
Stack:��T��Current Node:���Visited:��
H1
T
L1
L2
H2
L3
P1
(More-recently inserted items go on the right)
T: Title
H: Heading
L: Link
P: Paragraph
Note: We have not provided any sequential ordering relation, but you may opt to process as: T < H < L < P and 1 < 2 < 3.
Graph Traversal: DFS
Stack:����Current Node:�T��Visited:��
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
T is popped from the stack to then process its unvisited neighbors.
Graph Traversal: DFS
Stack:��H2 H1 ��Current Node:�T��Visited:�T�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
H1 and H2 are unvisited, here they are added in such a way that we will process the one in lower sequential order first.
Done with T = add to visited
If no ordering relation is provided, it is up to you to choose!
Graph Traversal: DFS (ON YOUR WORKSHEET NOW!)
Stack:��H2 ��Current Node:�H1��Visited:�T�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Process H1 to then add in its unvisited neighbors. (Pop from stack)
Graph Traversal: DFS
Stack:��H2 L2 L1��Current Node:�H1��Visited:�T H1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Add in the unvisited nodes, to choose L1 next (sequential)
Done with H1: Add to visited
Graph Traversal: DFS
Stack:��H2 L2��Current Node:�L1��Visited:�T H1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Process L1 and its unvisited neighbors (none), popped from stack
Graph Traversal: DFS
Stack:��H2 L2 ��Current Node:�L1��Visited:�T H1 L1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Mark L1 as visited (done processing)
Graph Traversal: DFS
Stack:��H2��Current Node:�L2��Visited:�T H1 L1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Process L2 and its unvisited neighbors (none), popped from stack
Graph Traversal: DFS
Stack:��H2��Current Node:�L2��Visited:�T H1 L1 L2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Mark L2 as visited (done processing)
Graph Traversal: DFS
Stack:����Current Node:�H2��Visited:�T H1 L1 L2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Process H2 to then add in its unvisited neighbors. (Pop from stack)
Graph Traversal: DFS
Stack:��P1 L3��Current Node:�H2��Visited:�T H1 L1 L2 H2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Add in the unvisited nodes, to choose L3 next (sequential)
Done with H2: Add to visited
Graph Traversal: DFS
Stack:��P1��Current Node:�L3��Visited:�T H1 L1 L2 H2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Pop L3 from stack to process unvisited neighbors (none)
Graph Traversal: DFS
Stack:��P1��Current Node:�L3��Visited:�T H1 L1 L2 H2 L3�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Done with L3: Add to visited
Graph Traversal: DFS
Stack:����Current Node:�P1��Visited:�T H1 L1 L2 H2 L3�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Pop P1 from stack to process unvisited neighbors (none)
Graph Traversal: DFS
Stack:����Current Node:�P1��Visited:�T H1 L1 L2 H2 L3 P1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Done with P1: Add to visited
Graph Traversal: DFS
Stack:����Current Node:���Visited:�T H1 L1 L2 H2 L3 P1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Graph Traversal: DFS
Other Possible Visited orders:�T H1 L1 L2 H2 L3 P1
T H1 L1 L2 H2 P1 L3
T H1 L2 L1 H2 L3 P1
T H1 L2 L1 H2 P1 L3
T H2 L3 P1 H1 L1 L2
T H2 L3 P1 H1 L2 L1
T H2 P1 L3 H1 L1 L2
T H2 P1 L3 H1 L2 L1
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Graph Traversal (BFS)
Graph Traversal: BFS
BFS Pseudocode
bfs(Graph graph, Vertex start) {
// stores the remaining vertices to visit in the BFS
Queue<Vertex> perimeter = new Queue<>();
// stores the set of visited vertices so we don't revisit them multiple times
Set<Vertex> visited = new Set<>();
// kicking off our starting point by adding it to the perimeter
perimeter.add(start); //
visited.add(start); //
while (!perimeter.isEmpty()) {
Vertex from = perimeter.remove();
for (E edge : graph.outgoingEdgesFrom(from)) {
Vertex to = edge.to();
if (!visited.contains(to)) {
perimeter.add(to);
visited.add(to);
}
}
}
}
Graph Traversal: BFS (HTML Graph)
Perimeter (Queue):��T��Current Node:�T��Visited:��
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We start at T; it helps establish our “perimeter” as a ‘from’ vertex.
Note: We have not provided any sequential ordering relation, but you may opt to process as: T < H < L < P and 1 < 2 < 3.
For visibility, we will add to visited after processing a node’s neighbors! In the code, you would add to both concurrently.
Graph Traversal: BFS
Perimeter Queue:��H1 H2��Current Node:�T��Visited:�T�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Since T was found and we’re moving forward, we de-queue it and want to look at its neighbors (“to” vertices)
H1 + H2 = Vertex to
So we add H1 and H2 to perimeter.
�Done with T = visited
Graph Traversal: BFS (ON YOUR WORKSHEET NOW!)
Queue:��H2��Current Node:�H1���Visited:�T�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We go level by level.
Here, we choose to look from H1.
Since H1 was found and we’re moving forward to new edges, we de-queue it and want to look at its neighbors (“to” vertices)
Graph Traversal: BFS
Perim. Queue:��H2 L1 L2��Current Node:�H1��Visited:�T H1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We discover H1’s neighbors are L1 and L2. They are new, so we add them to the queue!
We’re done pursuing H1 (no more edges found), so it is added to visited.
We now want to look from H2 (next in queue)
Graph Traversal: BFS
Perim. Queue:��L1 L2��Current Node:�H2��Visited:�T H1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We go level by level.
Here, we choose to look from H2.
Since H2 was found and we’re moving forward to new edges, we de-queue it and want to look at its neighbors (“to” vertices)
Graph Traversal: BFS
Perim. Queue:��L1 L2 L3 P1��Current Node:�H2��Visited:�T H1 H2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We discover H2’s neighbors are L3 and P1. They are new, so we add them to the queue!
We’re done pursuing H2 (no more edges found), so it is added to visited.
We now want to look from L1 (next in queue)
Graph Traversal: BFS
Perim. Queue:��L2 L3 P1��Current Node:�L1��Visited:�T H1 H2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We de-queue L1 from the Queue to look at its neighbors (“to” vertices)
We see there are none, so we’re going to move onto L2 and eventually mark it visited.
Graph Traversal: BFS
Perim. Queue:��L2 L3 P1��Current Node:�L1��Visited:�T H1 H2 L1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
L1 gets marked as visited as there nothing else to explore (no more children to it and seen before)
Graph Traversal: BFS
Queue:��L3 P1��Current Node:�L2��Visited:�T H1 H2 L1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We de-queue L2 from the Queue to look at its neighbors (“to” vertices)
We see there are none, so we’re going to move onto L3 and eventually mark it visited.
Graph Traversal: BFS
Queue:��L3 P1��Current Node:�L2��Visited:�T H1 H2 L1 L2�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
L2 gets marked as visited as there nothing else to explore (no more children to it and seen before)
Graph Traversal: BFS
Queue:��P1��Current Node:�L3��Visited:�T H1 H2 H2 L1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We de-queue L3 from the Queue to look at its neighbors (“to” vertices)
We see there are none, so we’re going to move onto P1 and eventually mark it visited.
Graph Traversal: BFS
Queue:��P1��Current Node:�L3��Visited:�T H1 H2 L1 L2 L3�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
L3 gets marked as visited as there nothing else to explore (no more children to it and seen before)
Graph Traversal: BFS
Queue:����Current Node:�P1��Visited:�T H1 H2 L1 L2 L3�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
We de-queue P1 from the Queue to look at its neighbors (“to” vertices)
We see there are none, so we’re going to eventually mark it visited.
Graph Traversal: BFS
Queue:����Current Node:�P1��Visited:�T H1 H2 L1 L2 L3 P1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
P1 gets marked as visited as there nothing else to explore (no more children to it and seen before)
Graph Traversal: BFS
Queue:����Current Node:���Visited:�T H1 H2 L1 L2 L3 P1�
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
DONE!
Graph Traversal: BFS
Other Possible Visited orders:�T H1 H2 L1 L2 L3 P1
T H1 H2 L1 L2 P1 L3
T H1 H2 L2 L1 L3 P1
T H1 H2 L2 L1 P1 L3
�T H2 H1 L3 P1 L1 L2
T H2 H1 L3 P1 L2 L1
T H2 H1 P1 L3 L1 L2
T H2 H1 P1 L3 L2 L1
H1
T
L1
L2
H2
L3
P1
T: Title
H: Heading
L: Link
P: Paragraph
Graph Traversal BFS and DFS Summary
Summary
Strongly connected
Not strongly connected
No way to reach 1
Graph Traversal: Design Problem
Multiple source shortest paths
Given a directed graph and multiple possible starting vertices, the multiple source shortest paths problem finds the shortest paths from any starting vertex to every vertex in the graph.
For example, consider starting S = {1, 5, 7}.
Ideally, we want the queue to include {1, 5, 7}. Without changing the code for BFS, describe a modification to the graph (add, remove, or change vertices/edges) so that BFS solves the multiple source shortest paths problem.
5
0
1
4
6
3
2
7
8
9
Approach:
Question for thought: What if this was a weighted graph, and we used a different shortest paths algorithm? What weights should we use?
5
0
1
4
6
3
2
7
8
9
s
Project Activity: Priority Queues!