Lecture 4: DFS, BFS, and Directed Graphs
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
Lab 1 Exercise
A walk in a graph is a sequence of vertices 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒌 such that there exist edges
𝒗𝟏,𝒗𝟐 , 𝒗𝟐,𝒗𝟑 ,…,{𝒗𝒌−𝟏,𝒗𝒌}
• If no edge is repeated, it is a trail.
• If no vertex is repeated, it’s a path.
Lab Exercise: Prove that if there exists an 𝒙 − 𝒚 trail, then there also exists an 𝒙 − 𝒚 path
𝒅 𝒆 𝒂,𝒃,𝒄,𝒅,𝒃,𝒆
Depth First Search (DFS)
𝑫𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery edges and back edges
Label 𝒖 as explored
for each edge 𝒆 incident to 𝒖 do
if 𝒆 is unexplored then
𝒗 ← other endpoint of 𝒆
if 𝒗 is unexplored then 𝟐
Label 𝒆 as an explored discovery edge 𝑫𝑭𝑺(𝑮, 𝒗)
else 𝟏𝟓 Label 𝒆 as an explored back edge
Depth First Search (DFS)
𝑫𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery edges and back edges
Label 𝒖 as explored
for each edge 𝒆 incident to 𝒖 do
if 𝒆 is unexplored then
𝒗 ← other endpoint of 𝒆 if 𝒗 is unexplored then
𝟎 back 𝟑 𝟐
Label 𝒆 as an explored discovery edge 𝑫𝑭𝑺(𝑮, 𝒗)
Label 𝒆 as an explored back edge
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Back edges go from nodes to one of its ancestors in the traversal discovery spanning tree
𝟒 𝟏 back 𝟓
Breadth First Search (BFS)
𝑩𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery edges and cross edges
𝑸 ← new empty queue Label 𝒖 as explored 𝑸.enqueue(𝒖)
while 𝑸 is not empty do
𝒖 ← 𝑸.dequeue()
for each edge 𝒆 = {𝒖, 𝒗} incident to 𝒖 do
if 𝒆 is unexplored then
if 𝒗 is unexplored then
Label 𝒆 as an explored discovery edge Mark 𝒗 as explored
𝑸.enqueue(𝒗) else
Label 𝒆 as an explored cross edge
Breadth First Search (BFS)
𝑩𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery edges and cross edges
𝑸 ← new empty queue Label 𝒖 as explored 𝑸.enqueue(𝒖)
while 𝑸 is not empty do
𝒖 ← 𝑸.dequeue()
for each edge 𝒆 = {𝒖, 𝒗} incident to 𝒖 do
if 𝒆 is unexplored then
if 𝒗 is unexplored then
Label 𝒆 as an explored discovery edge Mark 𝒗 as explored
𝑸.enqueue(𝒗) else
Label 𝒆 as an explored cross edge
discovery 𝟑 𝟐
discovery 𝟓
𝟒 𝟏𝟐cross𝟑
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Cross edges connect two nodes which do not have any ancestor and descendant relationship in the traversal discovery spanning tree
Directed Graphs (Digraphs)
A directed graph (digraph) is a graph whose edges are all directed
• Can implement undirected graphs using directed graphs
• Applications include one-way streets, flights, task scheduling
A directed edge 𝒆 represents an asymmetric relationship between two vertices 𝒖 and 𝒗
• We write 𝒆 = 𝒖, 𝒗 is an ordered pair
• 𝒖and𝒗aretheendpointsoftheedge
• 𝒖isadjacentto𝒗andviceversa
• 𝒆isincidentto𝒖and𝒗
• 𝒖 is the source vertex and 𝒗 is the destination vertex
• The indegree of a vertex is the number of incoming edges (𝐢𝐧𝐝𝐞𝐠 𝒘
• The outdegree of a vertex is the number of outgoing edges (𝐨𝐮𝐭𝐝𝐞𝐠 𝒘 = 3)
Simple Digraphs
A simple digraph is a graph with no self-loops and no parallel / multi-edges • Note that parallel edges in digraphs refer to edges pointing in the same direction
Theorem: If 𝑮 = (𝑽, 𝑬) is a digraph with 𝒎 edges, then indeg(𝒗)=outdeg𝒗 =𝒎
Theorem: Let 𝑮 be a simple digraph with 𝒏 vertices and 𝒎 edges. Then, 𝒎 ≤ 𝒏(𝒏 − 𝟏)
Corollary: A simple digraph with 𝒏 vertices has 𝑶 𝒏𝟐 edges
𝒏𝒏−𝟏 edges
Digraph Representation: Set of Edges
Maintain a list of directed edges (array or linked list)
• Also have to store a separate list of vertices since some vertices have no edges
Digraph Representation: Adjacency Matrix
Maintain a 𝟐-dimensional 𝒏 × 𝒏 boolean array
• For each directed edge
𝒖, 𝒗 , i.e 𝒖 → 𝒗, 𝐚𝐝𝐣 𝒖 𝒗 = 𝐭𝐫𝐮𝐞 𝟏
Destination
• In undirected graphs, every edge appears twice. In directed graphs, each edge appears once.
Digraph Representation: Adjacency List
Maintain an array indexed by vertices which points to a list of adjacent vertices
𝟎 𝟏𝟐𝟑 𝟏𝟑 𝟐𝟑𝟒 𝟑𝟒 𝟒𝟎
• In undirected graphs, every edge appears twice. In directed graphs, each edge appears once.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com