CS代考程序代写 algorithm COMP3027: Algorithm Design

COMP3027: Algorithm Design 
Lecture 2: Graphs
William Umboh
School of Computer Science
The University of Sydney
1

Lecture 2: Graphs
– Definitions
– Representations
– Breadth First Search
– Depth First Search
– Applications
The University of Sydney
2

Basic Definitions and Applications
The University of Sydney 3

Undirected Graphs G=(V,E)
– V = {nodes (or vertices)}
– E = {edges between pairs of nodes}
– Captures pairwise (symmetric) relationship between objects – Graph size parameters: n = |V|, m = |E|
The University of Sydney
4
V = { 1, 2, 3, 4, 5, 6, 7, 8 }
E = { (1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (3,7), (3,8),
(4,5), (5,6), (7,8) }  n=8
m = 11

Directed Graphs G=(V,E)
– Edge (u, v) goes from node u to v (sometimes called an arc) – Captures asymmetric relationship between objects
The University of Sydney 5

World Wide Web
– Node: web page.
– Edge: hyperlink from one page to another.
cnn.com
netscape.com
timewarner.com
hbo.com
sorpranos.com
novell.com
cnnsi.com
The University of Sydney
6

Some Graph Applications
Graph
Nodes
Edges
transportation
street intersections
highways
communication
computers
fiber optic cables
social
people
relationships
World Wide Web
web pages
hyperlinks
food web
species
predator-prey
software systems
functions
function calls
scheduling
tasks
precedence constraints
circuits
gates
wires
Undirected
Directed
The University of Sydney 7

The University of Sydney
8
Graph Representations

Graph Representation: Adjacency Matrix
Adjacency matrix. n-by-n matrix with Auv = 1 if (u, v) is an edge.
– Two representations of each edge (undirected graph). – Space proportional to n2.
– –
Checking if (u, v) is an edge takes Θ(1) time. Identifying all edges takes Θ(n2) time even if m << n. 12345678 1 2 3 4 5 6 7 8 01100000 10111000 11001011 01001000 01110100 00001000 00100001 00100010 The University of Sydney 9 Graph Representation: Adjacency List Adjacency list. Node indexed array of lists. – Two representations of each edge (undirected graph). – Space proportional to m + n. degree = number of neighbors of u – Checking if (u, v) is an edge takes O(deg(u)) time. – Identifying all edges takes Θ(m + n) time. 1 2 3 4 5 6 7 8 2 1 1 2 2 5 2 3 4 6 5 3 8 3 7 The University of Sydney 10 3 3 4 5 5 7 8 Paths and Connectivity Definition: A path in an undirected graph G = (V, E) is a sequence P of nodes v1, v2, ..., vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E. Example: 1,2,4,5,6 1,2,4,5,2,3 The University of Sydney 11 Paths and Connectivity Definition: A path in an undirected graph G = (V, E) is a sequence P of nodes v1, v2, ..., vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E. Definition: A path is simple if all nodes are distinct. Example: 1,2,4,5,6 1,2,4,5,2,3 The University of Sydney simple not simple 12 Paths and Connectivity Definition: A path in an undirected graph G = (V, E) is a sequence P of nodes v1, v2, ..., vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E. Definition: A path is simple if all nodes are distinct. Definition: An undirected graph is connected if for every pair of nodes u and v, there is a path between u and v. The University of Sydney 13 Connected Paths and Connectivity Definition: A path in an undirected graph G = (V, E) is a sequence P of nodes v1, v2, ..., vk-1, vk with the property that each consecutive pair vi, vi+1 is joined by an edge in E. Definition: A path is simple if all nodes are distinct. Definition: An undirected graph is connected if for every pair of nodes u and v, there is a path between u and v. The University of Sydney 14 Not connected (or disconnected) Cycles Definition: A cycle is a path v1, v2, ..., vk-1, vk in which v1 = vk, k > 2, and the first k-1 nodes are all distinct.
The University of Sydney
15
cycle C = 1-2-4-5-3-1

Can a simple path contain a cycle?
Definition: A path is simple if all nodes are distinct. Definition: A cycle is a path v1, v2, …, vk-1, vk in which v1 = vk,
k > 2, and the first k-1 nodes are all distinct.
The University of Sydney 16

Can a simple path contain a cycle? NO
Definition: A path is simple if all nodes are distinct. Definition: A cycle is a path v1, v2, …, vk-1, vk in which v1 = vk,
k > 2, and the first k-1 nodes are all distinct.
The University of Sydney 16

Trees
The University of Sydney 17

Trees
Definition: An undirected graph is a tree if it is connected and
does not contain a cycle.
The University of Sydney 17

Trees
Definition: An undirected graph is a tree if it is connected and
does not contain a cycle.
Number of edges in a tree?
The University of Sydney 17

Trees
Definition: An undirected graph is a tree if it is connected and
does not contain a cycle.
Number of edges in a tree?
Theorem: Let G be an undirected graph on n nodes. Any two of the following statements imply the third.
The University of Sydney 17

Rooted Trees
Rooted tree. Given a tree T, choose a root node r and orient each edge away from r.
Importance. Models hierarchical structure.
root r
a tree the same tree, rooted at 1
The University of Sydney
18

Rooted Trees
Rooted tree. Given a tree T, choose a root node r and orient each edge away from r.
Importance. Models hierarchical structure.
root r
Notation:
u is parent of v
v is a child of u
r is an ancestor of v v is a descendant of r
u
v
The University of Sydney
18
a tree
the same tree, rooted at 1

The University of Sydney
19
Graph Traversal

Connectivity
s-t connectivity problem. Given two nodes s and t, is there a path between s and t?
Length of path = number of links along path
s-t shortest path problem. Given two nodes s and t, what is the
length of the shortest path between s and t?
Applications.
Many. For example: Fewest number of hops in a communication network.
The University of Sydney 20

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
BFS algorithm.
– – –
–
L0 ={s}.
L1 = all neighbors of L0.
L1
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
L2
The University of Sydney 21

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
L1
BFS algorithm.
– – –
–
L0 ={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
L0
L2
The University of Sydney
21

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
L1
L2
BFS algorithm.
– – –
–
L0 ={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
L0 L1
The University of Sydney
21

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
BFS algorithm.
– – –
–
L0 ={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
L0
L1 L2
The University of Sydney
21
L1
L2

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
BFS algorithm.
– – –
–
L0 ={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
L0
L1 L2
The University of Sydney
L3 21
L1
L2

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
BFS algorithm.
L0 ={s}.
L1 = all neighbors of L0.
– – –
–
Alt. intuition. Flooding process starting at s
– Initially, s is flooded.
– In each iteration, every unflooded vertex
that neighbors a previously flooded verteLx
becomes flooded
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
The University of Sydney
L3 21
L1
L2
L0 L1
2

Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
L1
BFS algorithm.
– – –
L0 ={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoanodein L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
–
Theorem: For each i, Li consists of all nodes at distance exactly i 
from s. There is a path from s to t if and only if t appears in some layer.
The University of Sydney 22
L2

def BFS(G,s)
s
L1 L2 Ln-1
layers = []
current_layer = [s]
“mark all vertices except s as not seen”
while “current_layer not empty” do
layers.append(current_layer)
for every u in current_layer do
for every v in neighbourhood of u do
if “haven’t seen v yet” then
next_layer.append(v)
“mark v as seen”
current_layer = next_layer
next_layer = []
return layers
The University of Sydney 23

def BFS(G,s)
s
L1 L2 Ln-1
layers = []
current_layer = [s]
“mark all vertices except s as not seen”
while “current_layer not empty” do
layers.append(current_layer)
for every u in current_layer do
for every v in neighbourhood of u do
if “haven’t seen v yet” then
next_layer.append(v)
The University of Sydney
23
“mark v as seen”
current_layer = next_layer
next_layer = []
return layers
What if G is not connected?

Breadth First Search Tree
BFS produces a tree T rooted at the start vertex on the set of nodes in G reachable from s where edges of T are edges that “discover unseen nodes”
The University of Sydney
L0 L1
L2 L3 24

Properties of Breadth First Search Tree
The University of Sydney
L0 L1
L2 L3 25

Properties of Breadth First Search Tree
Obs. LetTbeaBFStreeofG=(V,E).
– if u belongs to some layer, then u and s are connected
– if u and s are connected, then u belongs to some layer
– u belongs to layer i if and only if shortest path between u and s consists of i edges
– edges across layers connect adjacent layers
The University of Sydney
L0 L1
L2 L3 25

Breadth First Search: Analysis
Theorem: The above implementation of BFS runs in O(m + n) time
if the graph is as an adjacency list.
Proof: Easy to prove O(n2) running time:
• at most n lists L[i]
• each node occurs on at most one list; for loop runs ≤ n times
• when we consider node u, there are ≤ n incident edges (u, v), 
and we spend O(1) processing each edge – Actually runs in O(m + n) time:
• •
when we consider node u, there are deg(u) incident edges (u, v) total time processing edges is Σu∈V deg(u) = 2m
each edge (u, v) is counted exactly twice  in sum: once in deg(u) and once in deg(v)
The University of Sydney
26

def BFS(G,s)
layers = []
current_layer = [s]
“mark all vertices except s as not seen”
while “current_layer not empty” do
layers.append(current_layer)
for every u in current_layer do
for every v in neighbourhood of u do
if “haven’t seen v yet” then
next_layer.append(v)
“mark v as seen”
current_layer = next_layer
next_layer = []
return layers
This takes O(n) time
The University of Sydney
27

BFS implementation
Complexity? Depends on graph representation
The University of Sydney
28

BFS implementation
Complexity? Depends on graph representation
Traverse all neighbours of a node u:
The University of Sydney 28

BFS implementation
Complexity? Depends on graph representation
Traverse all neighbours of a node u:
– Adjacencylist:Θ(numberofneighbours)=Θ(|N(u)|)
The University of Sydney 28

BFS implementation
Complexity? Depends on graph representation
Traverse all neighbours of a node u:
– Adjacencylist:Θ(numberofneighbours)=Θ(|N(u)|) – Adjacencymatrix:Θ(n)
Check if u and v are connected by an edge:
– Adjacency list: Θ(number of neighbours) = Θ(|N(u)|) or Θ(|N(v)|)
The University of Sydney 28

Applications of BFS
The University of Sydney 29

Applications of BFS
– Connected component problem:
The University of Sydney 29

Applications of BFS
– Connected component problem:
– Given G and s, output the set of vertices connected to s
The University of Sydney 29

Applications of BFS
– Connected component problem:
– Given G and s, output the set of vertices connected to s
– Shortest path problem:
– Given G and s, output the length of the shortest path between s
and all other nodes in V
The University of Sydney 29

Connected Component
Find all nodes reachable from s.
Connected component containing node 1
= { 1, 2, 3, 4, 5, 6, 7, 8}
The University of Sydney
30

Transitive closure of a graph
The transitive closure graph of G is a graph G’:
– with the same vertices as G, and
– with an edge between all pairs of nodes that are connected by a path in G
input: abcd
output:
abcd
The University of Sydney
31

Closure graph by BFS
The University of Sydney 32

Closure graph by BFS
Question: What is transitive closure of connected graph?
The University of Sydney 32

Closure graph by BFS
Question: What is transitive closure of connected graph? Answer: A complete graph (contains every possible edge)
The University of Sydney 32

Closure graph by BFS
Question: What is transitive closure of connected graph? Answer: A complete graph (contains every possible edge)
Question: What is transitive closure of disconnected graph?
The University of Sydney 32

Closure graph by BFS
Algorithm:
1. Compute connected components
2. For each component, make a complete graph
The University of Sydney 33

DFS – Depth first search
Algorithm: Pick a starting vertex, follow outgoing edges that lead
to new vertices, and backtrack whenever “stuck”.
The University of Sydney 34

DFS via recursion
Algorithm DFS(G,u)
Input: graph G(V,E) and a vertex u in V
begin
mark u as visited
for each edge (u,v) in E do
if v has not been visited then
DFS(G,v)
end
The University of Sydney
35

DFS via stack
The University of Sydney
36
Algorithm DFS(G,s)
Input: graph G(V,E) and a vertex s in V
begin
initialise a stack S with node s
while S is not empty do
end
u=pop(S)
if u not visited then
set u as visited
for each edge (u,v) do
add v to S

BFS via queue
The University of Sydney
37
Algorithm BFS(G,s)
Input: graph G(V,E) and a vertex s in V
begin
initialise a queue Q with node s
while Q is not empty do
end
u=dequeue(Q)
if u not visited then
set u as visited
for each edge (u,v) do
enqueue v to Q

Properties of DFS
Running time: O(n+m)
Subset of edges in DFS that “discover a new node” form a forest
(a collection of trees).
A graph is connected if and only if DFS results in a single tree. Each tree in the DFS result corresponds to a connected component
The University of Sydney 38

The University of Sydney
39
Bipartite Graphs and Testing Bipartiteness

Bipartite Graphs
Definition: An undirected graph G = (V, E) is bipartite if the nodes can be colored red or blue such that every edge has one red and one blue end.
Applications
– Stable marriage: men = red, women = blue. – Scheduling: machines = red, jobs = blue.
The University of Sydney
40
a bipartite graph

Testing Bipartiteness
Testing bipartiteness. Given a graph G, is it bipartite? – Many graph problems become:
• easier if the underlying graph is bipartite (matching)
• tractable if the underlying graph is bipartite (independent set) – Before attempting to design an algorithm, we need to understand
structure of bipartite graphs.
v2 v3
v2
v4
v1
v6v5v4 v3 v5
v7 v1
v6
v7
The University of Sydney a bipartite graph G another drawing of G 41

An Obstruction to Bipartiteness
Lemma: If a graph G is bipartite, it cannot contain an odd
length cycle.
Proof: Not possible to 2-color the odd cycle, let alone G.
The University of Sydney
42
bipartite  (2-colorable)
not bipartite  (not 2-colorable)

Bipartite Graphs
L1 L2 L3 L1 L2 L3
The University of Sydney Case (i) Case (ii) 43

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the
layers produced by BFS starting at node s. Exactly one of the following holds.
L1 L2 L3 L1 L2 L3
The University of Sydney Case (i) Case (ii) 43

Bipartite Graphs
L1 L2 L3
The University of Sydney Case (i) 44

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the
layers produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite).
Proof: Case (i)
– Suppose no edge joins two nodes in the same layer.
– By previous lemma, this implies all edges join nodes on adjacent level. – Bipartition: red = nodes on odd levels, blue = nodes on even levels.
L1 L2 L3
The University of Sydney Case (i) 44

Bipartite Graphs
z = lca(x, y)
The University of Sydney 45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
z = lca(x, y)
The University of Sydney 45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj. – Let z = lca(x, y) = lowest common ancestor.
–
z = lca(x, y)
Let Li be level containing z.
The University of Sydney 45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj.
– Let z = lca(x, y) = lowest common ancestor.
–
z = lca(x, y)
Let Li be level containing z.
– Consider cycle that takes edge from x to y, 
then path from y to z, then path from z to x.
The University of Sydney 45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj.
– Let z = lca(x, y) = lowest common ancestor.
–
then path from y to z, then path from z to x.
– Its length is 1 + (j-i) + (j-i), which is odd. ▪
z = lca(x, y)
Let Li be level containing z.
– Consider cycle that takes edge from x to y, 
The University of Sydney 45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj.
– Let z = lca(x, y) = lowest common ancestor.
–
then path from y to z, then path from z to x.
– Its length is 1 + (j-i) + (j-i), which is odd. ▪
(x, y)
z = lca(x, y)
Let Li be level containing z.
– Consider cycle that takes edge from x to y, 
The University of Sydney
45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj.
– Let z = lca(x, y) = lowest common ancestor.
–
then path from y to z, then path from z to x.
– Its length is 1 + (j-i) + (j-i), which is odd. ▪
(x, y) path from  y to z
z = lca(x, y)
Let Li be level containing z.
– Consider cycle that takes edge from x to y, 
The University of Sydney
45

Bipartite Graphs
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers
produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd- length cycle (and hence is not bipartite).
Proof: Case (ii)
– Suppose (x, y) is an edge with x, y in same level Lj.
– Let z = lca(x, y) = lowest common ancestor.
–
then path from y to z, then path from z to x.
– Its length is 1 + (j-i) + (j-i), which is odd. ▪
(x,y) pathfrom  pathfrom  y to z z to x
z = lca(x, y)
Let Li be level containing z.
– Consider cycle that takes edge from x to y, 
The University of Sydney
45

Obstruction to Bipartiteness
Corollary: A graph G is bipartite if and only if it contain no odd
length cycle.
Proof: Previous lemma showed that G is bipartite if and only if BFS tree has no intra-layer edge. Observe that BFS tree has no intra-layer edge if and only if there is no odd-length cycle.
5-cycle C
The University of Sydney
46
bipartite  (2-colorable)
not bipartite  (not 2-colorable)

Testing bipartiteness
Theorem: Given a graph G=(V,E) one can test if G is bipartitie in
O(n+m) time.
5-cycle C
The University of Sydney
47
bipartite  (2-colorable)
not bipartite  (not 2-colorable)

Cut edges
Definition: In a connected graph, an edge e is called a “cut edge”
if its removal would disconnect the graph • G=(V,E) is connected
• G’ = (V, E\{e}) is not connected
How do we find the cut edges of a graph?
The University of Sydney 48

Finding cut edges
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one)
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one) For every edge e in G
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one) For every edge e in G
remove e from G
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one)
For every edge e in G
remove e from G
check if G is connected (running DFS for
example)
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one)
For every edge e in G
remove e from G
check if G is connected (running DFS for
example)
Running time?
The University of Sydney 49

Finding cut edges
Algorithm 1: (the straightforward one)
For every edge e in G
remove e from G
check if G is connected (running DFS for
example)
Running time? O(m2+mn)
The University of Sydney
49

Finding cut edges
Algorithm 1: (the straightforward one)
For every edge e in G
remove e from G
check if G is connected (running DFS for
example)
Running time? O(m2+mn) More efficient algorithm?
The University of Sydney 49

Structural property of cut edges
Definition: In a connected graph, an edge e is called a “cut edge”
if its removal would disconnect the graph • G=(V,E) is connected
• G’ = (V, E\{e}) is not connected
Lemma. e is a cut edge if and only if e is not contained in a cycle Proof.
-Let e = (u,v) be an edge and G’ = (V, E\{e})
-e is a cut edge if and only if u and v are disconnected in G’
-u and v are disconnected in G’ if and only if e is not in a cycle
The University of Sydney 50

Finding cut edges
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
Algorithm 2:
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
Algorithm 2:
Run DFS on the graph G
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
Algorithm 2:
Run DFS on the graph G
For each edge in the DFS tree
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
Algorithm 2:
Run DFS on the graph G
For each edge in the DFS tree
remove that edge from the graph G
The University of Sydney 51

Finding cut edges
Assumes the input graph G is connected.
Algorithm 2:
Run DFS on the graph G
For each edge in the DFS tree
remove that edge from the graph G
check if G is now disconnected (using DFS)
The University of Sydney 51

The University of Sydney
52
Algorithm DFS(G,u)
Input: graph G(V,E) and a vertex u in V
begin
mark u as visited
for each edge (u,v) in E do
if v has not been visited then
DFS(G,v) end

Algorithm DFS(G,u)
Input: graph G(V,E) and a vertex u in V
begin
mark u as visited
for each edge (u,v) in E do
if v has not been visited then
DFS(G,v) end
The University of Sydney
52

Algorithm DFS(G,u)
Input: graph G(V,E) and a vertex u in V
begin
mark u as visited
for each edge (u,v) in E do
if v has not been visited then
DFS(G,v) end
Obs. Non-tree edges = back edges
The University of Sydney 52

Summary: Graphs
Graph representation:
– adjacency matrix or adjacency list
Basic notations and definitions:
– cycle, simple, connected, path, tree, directed,…
Traversing a graph (BFS or DFS): O(n+m)
– Applications of BFS/DFS: shortest path, transitive closure, testing
bipartitness, cut edges…
The University of Sydney 53

For HW1: Minimum Spanning Tree
Def.: Given a graph G = (V,E) with real-valued edge costs ce f a minimum spanning tree (MST) is a spanning tree T whose sum of edge cost is minimised.
4 24 4 62396 9
16
18
511 511
8 14 7 8 7 10
21
G=(V,E) T, Σe∈T ce=50
The University of Sydney
54

This Week’s Todo’s
Tutorial 2:
– to be posted this evening
– make sure you work on it before the tutorial
Quiz 1:
– to be posted this evening
– due Wednesday 13 March 23:59:00 (no late submissions accepted)
Assignment 1:
– posted tonight
– due Wednesday 20 March 23:59:00
– no submissions later than Wednesday 27 March 23:59:00 accepted – START EARLY!
The University of Sydney 55

Related Posts