Implement the following algorithm for connectivity of undirected graphs
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Implement the following
Transcribed Image Text:blockDFS(v)
pred(v) = num(v) = i++;
for all vertices u adjacent to V
if edge(vu) has not been processed undirected graphs
push(edge(vu));
if num(u) is 0
blockDFS(u);
if pred(u) > num(v)
e = pop();
while e + edge(vu)
Connectivity in
%3D
// if there is no edge from u to
// a vertex above v, output a block
// by popping all edges off the stack
// until edge(vu) is popped off;
output e;
e = pop();
%3D
// e == edge(vu);
output ē;
else pred(v) = min(pred(v),pred(u)); // take a predecessor higher up in
else if u is not the parent of V
pred(v) = min(pred(v),num(u));// update when back edge(vu) is found;
// the tree;
blockSearch()
for all vertices V
num(v) = 0;
%3D
%3D
while there is a vertex V such that num(v) == 0
blockDFS(v);
Connectivity in undirected
granhs: example
blockDFS(a)
num(a) pred(a) = 1
push edge(ac)
blockDFS(C)red(c) = 2
%D
num
Transcribed Image Text:a 0 0: c d
b 0 0: d f
parent: 0
parent: 0
с о 0: а е
d 0 0: a be f
е 0 0: с d
fo 0: b dgh
parent: 0
parent: 0
parent: 0
parent: 0
g 0 0: f
h0 0: f
DFS (a)
parent: 0
parent: 0
num (a) = pred (a) = 1
trying edge (ac)
push (edge (ac))
DFS (c)
%3D
num (c) =
pred (c)
%3D
trying edge (ca)
trying edge (ce)
push (edge (ce))
DFS (e)
num (e)
pred (e) = 3
%3D
%3D
trying edge (ec)
trying edge (ed)
push (edge (ed))
DFS (d)
num (d)
pred (d) = 4
trying edge (da)
push (edge (da))
pred2 (d) = 1 (= num (a))
trying edge (db)
push (edge (db))
DFS (b)
%3|
=
trying edge (bd)
trying edge (bf)
push (edge (bf))
DFS (f)
num (b)
pred (b) = 5
num (f)
trying edge (fb)
trying edge (fd)
push(edge (fd))
pred2 (f) = 4 (= num (d))
trying edge (fg)
push (edge (fg))
DFS (g)
num (g) =
trying edge (gf)
BLOCK: edge (fg)
trying edge (fh)
push (edge (fh))
DFS (h)
pred (f) = 6
%3D
pred (g) = 7
num (h) = pred (h) = 8
trying edge (hf)
BLOCK: edge (fh)
%3D
pred (b) = 4 (= pred(f))
BLOCK: edge (fd) edge (bf) edge (db)
trying edge (de)
trying edge (df)
pred (e) = 1 (= pred(d))
%3D
%3D
pred (c) = 1 (= pred(e))
BLOCK: edge (da) edge (ed) edge (ce) edge(ac)
trying edge (ad)
a 1 1: с d
b 5 4: d f
%3D
parent: 0
parent: d
c 2 1:
d 4 1: a bef
e 3 1: c d
f 6 4: bdgh
g 7 7: f
h 8 8: f
a e
parent: a
parent: e
parent: c
parent: b
parent: f
parent: f
2.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question
Can I please get the c++ code for this as well? Thank you.
Solution
by Bartleby ExpertKnowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education