CS61B Lecture #33
Today’s Readings: Graph Structures: DSIJ, Chapter 12
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 1
Copyright By PowCoder代写 加微信 powcoder
Why Graphs?
• For expressing non-hierarchically related items • Examples:
– Networks: pipelines, roads, assignment problems
– Representing processes: flow charts, Markov models
– Representing partial orderings: PERT charts, makefiles
– As we’ve seen, in representing connected structures as used in Git.
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 2
Some Terminology
• A graph consists of
– A set of nodes (aka vertices)
– A set of edges: pairs of nodes.
– Nodes with an edge between are adjacent.
– Depending on problem, nodes or edges may have labels (or weights )
• Typically call node set V = {v0, . . .}, and edge set E.
• If the edges have an order (first, second), they are directed edges, and we have a directed graph (digraph), otherwise an undirected graph.
• Edges are incident to their nodes.
• Directed edges exit one node and enter the next.
• A cycle is a path without repeated edges leading from a node back to itself (following arrows if directed).
• A graph is cyclic if it has a cycle, else acyclic. Abbreviation: Di- rected Acyclic Graph—DAG.
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 3
Some Pictures
Directed Undirected bb
Acyclic: a
e WithEdgeLabels: a 3 2 d a 3 d
1b1 1b2 cc
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 4
Trees are Graphs
• A graph is connected if there is a (possibly directed) path between every pair of nodes.
• That is, if one node of the pair is reachable from the other.
• A DAG is a (rooted) tree iff connected, and every node but the root
has exactly one parent.
• A connected, acyclic, undirected graph is also called a free tree. Free: we’re free to pick the root; e.g., all the following are the same graph:
bebd adadebc
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 5
• Edge = Connecting road, with length.
Examples of Use
• Edge = Must be completed before; Node label = time to complete.
Sleep 8 hrs
• Edge = Begat
modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 6
More Examples
• Edge = some relationship
potstickers eats John loves Mary
• Edge = next state might be (with probability) 0.9
hat 0.4 the 0.6 cat 0.4 in
• Edge = next state in state machine, label is triggering input. (Start at s. Being in state 4 means “there is a substring ‘001’ somewhere in the input”.)
s020314 0,1 1
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 7
1: a 2: b 3: c
Representation
• Often useful to number the nodes, and use the numbers in edges.
• Edge list representation: each node contains some kind of list (e.g.,
linked list or array) of its successors (and possibly predecessors).
(2,3) () (3) (1) • Edge sets: Collection of all edges. For graph above:
{(1, 2), (1, 3), (2, 3)}
• Adjacency matrix: Represent connection with matrix entry:
123 1011
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 8
3 0 0 0
Traversing a Graph
• Many algorithms on graphs depend on traversing all or some nodes.
• Can’t quite use recursion because of cycles.
• Even in acyclic graphs, can get combinatorial explosions:
0 3 6 … 3N
Treat 0 as the root and do recursive traversal down the two edges
out of each node: Θ(2N ) operations!
• So typically try to visit each node constant # of times (e.g., once).
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 9
Recursive Depth-First Traversal of a Graph
• Can fix looping and combinatorial problems using the “bread-crumb” method used in earlier lectures for a maze.
• That is, mark nodes as we traverse them and don’t traverse previ- ously marked nodes.
• Makes sense to talk about preorder and postorder, as for trees.
voidpreorderTraverse(GraphG,Nodev) voidpostorderTraverse(GraphG,Nodev) {{
if (v is unmarked) { mark(v);
for (Edge(v, w) ∈ G)
traverse(G, w);
if (v is unmarked) { mark(v);
for (Edge(v, w) ∈ G) traverse(G, w);
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 10
Recursive Depth-First Traversal of a Graph (II)
• We are often interested in traversing all nodes of a graph, not just those reachable from one node.
• So we can repeat the procedure as long as there are unmarked nodes.
void preorderTraverse(Graph G) { clear all marks;
for(v ∈ nodesofG) {
preorderTraverse(G, v);
void postorderTraverse(Graph G) { clear all marks;
for(v ∈ nodesofG) {
postorderTraverse(G, v);
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 11
Topological Sorting
Problem: Given a DAG, find a linear order of nodes consistent with
the edges.
• That is, order the nodes v0, v1, . . . such that vk is never reachable
from vk′ if k′ > k.
• Gmake does this. Also PERT charts.
Graph (two views) Possible Orderings
C ACACACCF G
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 12
B D F DF DB B
H EGEGDE GEH
Sorting and Depth First Search
• Observation: Suppose we reverse the links on our graph.
• If we do a recursive DFS on the reverse graph, starting from node H, for example, we will find all nodes that must come before H.
• When the search reaches a node in the reversed graph and there are no successors, we know that it is safe to put that node first.
• In general, a postorder traversal of the reversed graph visits nodes only after all predecessors have been visited.
BDF1 H EG2
Numbers show post- order traversal order starting from G: every- thing that must come before G.
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 13
General Graph Traversal Algorithm
COLLECTION OF VERTICES fringe;
fringe = INITIAL COLLECTION; while (!fringe.isEmpty()) {
Vertex v = fringe.REMOVE HIGHEST PRIORITY ITEM();
if (!MARKED(v)) { MARK (v);
VISIT (v);
For each edge(v,w) {
if (NEEDS PROCESSING(w)) Add w to fringe;
Replace COLLECTION OF VERTICES, INITIAL COLLECTION, etc. with various types, expressions, or methods to different graph algorithms.
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 14
Example: Depth-First Traversal
Problem: Visit every node reachable from v once, visiting nodes fur-
ther from start first.
// Red sections are specializations of general algorithm Stack
fringe = stack containing {v}; while (!fringe.isEmpty()) {
Vertex v = fringe.pop();
if (!marked(v)) { mark (v);
VISIT (v);
For each edge(v,w) {
if (!marked(w))
fringe.push(w);
Last modified: Wed Apr 15 14:43:04 2020
CS61B: Lecture #33 15
Depth-First Traversal Illustrated
bbbb Marked:z ce ce ce ce
dfdfdfdf Fringe: [a] [b,d] [c,e,d] [d,f,e,d]
bbbb cececece
[f,e,d] [e,e,d] [e,d] []
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 16
fringe D2 F1
A0 D F A0 D F A0 D F
B0 E G B0 E G B0 E G 313121
H1 H1 H1 [A] [A,C] [A,C,B]
Topological Sort in Action
Output: []
A0DFA0DF A0DF 000000
B0EGB0EG B0EG 100000
H1 H1 H0 [A,C,B,F] [A,C,B,F,D] [A,C,B,F,D,E,G,H]
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 17
Shortest Paths: Dijkstra’s Algorithm
Problem: Given a graph (directed or undirected) with non-negative edge weights, compute shortest paths from given source node, s, to all nodes.
• “Shortest” = sum of weights along path is smallest. • For each node, keep estimated distance from s, . . . • . . . and of preceding node in shortest path from s.
PriorityQueue
For each node v { v.dist() = ∞; v.back() = null; } s.dist() = 0;
fringe = priority queue ordered by smallest .dist();
add all vertices to fringe;
while (!fringe.isEmpty()) {
Vertex v = fringe.removeFirst();
For each edge(v,w) {
if (v.dist() + weight(v,w) < w.dist())
{ w.dist() = v.dist() + weight(v,w); w.back() = v; } }
Last modified: Wed Apr 15 14:43:04 2020 CS61B: Lecture #33 18
C|∞ C|5 C|5 545454
2 B|∞ 2 2 A|0 2 B|2 2 2 A|0 2 B|2 2 2
353 353 353
D|∞ 4 E|∞ 1 F|∞ 7 D|3 4 E|∞ 1 F|∞ 7 D|3 4 E|5 1 F|∞
362 362 362 G|∞ 1 H|∞ G|7 1 H|∞ G|7 1 H|∞
C|5 C|5 C|5 545454
2 B|2 2 2 A|0 2 B|2 2 2 A|0 2 B|2 2 2
353 353 353
D|3 4 E|5 1 F|∞ 7 D|3 4 E|5 1 F|7 7 D|3 4 E|5 1 F|6
362 362 362
G|6 1 H|9 C|5
Shortest-path tree processed node at distance d node in fringe at distance d
CS61B: Lecture #33 19
A|0 Final result:
D|3 4 E|5 1 F|6
Last modified: Wed Apr 15 14:43:04 2020
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com