ECS122A-L15

📗 -> 11/26/24: ECS122A-L15

---

🎤 Vocab

❗ Unit and Larger Context

Intro Graphs:

• BFS
• DFS
• Prims

✒️ -> Scratch Notes

# dont know what this is doing?
for (v in V) {
	for (w in V) {
		(v,w)
	}
}


# I think this is vertex edge comboes
for (v in V) {
	for (u in Adj[V]) {
		print(v,w)
	}
}

O(V+E)

---

DFS Traversal:

• Topological sort
• Cycles

BFS:

• Shortest path given edge weights are unit

GRAPHS ON FINAL

The big thing on the final will be doing a graph traversal, and marking discovery (d[i]) time and finish (f[i]) time

Labeling of Edges

Tree edge transform graph into tree or forest

1. Tree edge = T
2. Back edges = B (indicate a cycle)
   • When you have grey to white, that’s a tree edge (T)
   • When you have grey to grey, that’s a back edge (B) (indicates a cycle)
3. Forward Edge:
   • From ancestor to descendant
     • Grey to black
4. Cross Edge:
   • Between two trees or two subtrees
     • Also grey to black

Distinguishing Edges:

• If you have grey to black, that is either a forward edge or a cross edge
  • Time of grey entry () and Time of black entry ()
  • REVIEW THIS CAREFULLY. HALF PAYING ATTENTION.
  • If
    • Cross Edge
  • If
    • Forward Edge

---

Shortest Path

Input: Weighted graph G(V,E) and W(E)
Output: Arrays D, Pi such that

• = shortest path from s to u
• is the predecessor parent of m. Shortest path from s to u.
  Shortest path:
  a — (3) -> b — (-2) -> c — (4) -> d

	a	b	c	d
d	0	3	1	5
pi	0	a	b	c

---

Prove shortest path problem has optimal substructure for single pair of nodes:
Steps:

1. given: opti is the optimal path / shortest path between u and v
   • Opt = (x1,x2).. Xr. x1 = u, xr=v
2. A = OPT-(x1,x2)
   • Prove …e A is the shortest path from X2 to V in G(v-x1)
3. Assume A is NOT the shortest path in G(v-x1)
   => Then there exists B that is shortest path in G(v-x1) =>
   W(B) = W(A) def of optimal/short
   B (x1,x2) = VALID path for x1 to V
   W(B) + W(x1, x2) < W(A) + W(x1, x2) by alg.
   Valid Path < Optimal, contradiction

• W function returns a real value

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words