Let G = (V, E) be a connected, undirccted graph. The goal is to determine if there is a cycle of length e >0 (i.c., the mumber of edges in the eycle is e> 0) in G such that ( is divisible by 2. If so, output the cycle, otherwise output Null. You must use depth-first scarch to design an a lgorithm for the p roblem. That is, let s be a vertex in G. We do depth-first scarch (DFS) starting from a, i.c., we will construct a depth-first s panning t ree r ooted at s.A part from t he g raph G ( represented a s an adjacency list), the only other data structures you uill need in your algorithm are the arrays visited, parent, and length. The visited and parent arrays are as discussed in class. Initially, visited(v) = False for all v e V and parent u) = Null for all v. The array length is defined as follows. For a ny node v, length(u), is the number of tree odges in the (unique) path from the root a to the vertex v in the depth-first spanning troo. Initially, only the length of the root is defined, i.e., lengthls] 0 and is undefined for all other vertices in the graph. When a node is visited for the first timo, i ts length is set accordingly. Algorithm DFS based algorithm to determine if a positive even cycle exists. 1: procedure POSITIVE-EVEN-CYCLE(G, a) 2: for each v e V do visitedju) - False parent e Null length(u) 0 length(a) +0 DFS-V ISIT(a) 3: 4: 5: D Length from root is 0. 6: 7: (i) Provide the pseudocode for DFS-VISIT that outputs the required solution. Your psoudocode should be appropriately commented. (ii) Explain your psOudocode and argue its correctness. (iii) Illustrate your algorithm by running it on the graph G (Figure 1, ignore the weights), starting at node s (sox Weights and Source Node). Show the length values for all nodes in the DFS tre.
Let G = (V, E) be a connected, undirccted graph. The goal is to determine if there is a cycle of length e >0 (i.c., the mumber of edges in the eycle is e> 0) in G such that ( is divisible by 2. If so, output the cycle, otherwise output Null. You must use depth-first scarch to design an a lgorithm for the p roblem. That is, let s be a vertex in G. We do depth-first scarch (DFS) starting from a, i.c., we will construct a depth-first s panning t ree r ooted at s.A part from t he g raph G ( represented a s an adjacency list), the only other data structures you uill need in your algorithm are the arrays visited, parent, and length. The visited and parent arrays are as discussed in class. Initially, visited(v) = False for all v e V and parent u) = Null for all v. The array length is defined as follows. For a ny node v, length(u), is the number of tree odges in the (unique) path from the root a to the vertex v in the depth-first spanning troo. Initially, only the length of the root is defined, i.e., lengthls] 0 and is undefined for all other vertices in the graph. When a node is visited for the first timo, i ts length is set accordingly. Algorithm DFS based algorithm to determine if a positive even cycle exists. 1: procedure POSITIVE-EVEN-CYCLE(G, a) 2: for each v e V do visitedju) - False parent e Null length(u) 0 length(a) +0 DFS-V ISIT(a) 3: 4: 5: D Length from root is 0. 6: 7: (i) Provide the pseudocode for DFS-VISIT that outputs the required solution. Your psoudocode should be appropriately commented. (ii) Explain your psOudocode and argue its correctness. (iii) Illustrate your algorithm by running it on the graph G (Figure 1, ignore the weights), starting at node s (sox Weights and Source Node). Show the length values for all nodes in the DFS tre.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Transcribed Image Text:W1
a
W2
w6
w7
6.
-1
4
W3
W5
e
W4
Figure 1: Weighted, undirected graph G.
Weights and Source Node
All problems use weights wi through w7. To determine these weights, look at your 7
digit ID. The weight wi corresponds to the first digit of your ID, the weight w2
corresponds to the second digit of your ID, and so on.
For problems 2 and 4, we use a source node or starting node s, determined as
follows: find the digit in your ID that has the highest value. If it is the first digit then s =
a, if it is the second digit, then s = b, and so on. If there is more than one digit with the
same highest value, choose the first occurrence of that digit. For example, if your ID is
4526767, then the highest value is 7, and you choose the first 7, i.e., digit 5, and set s =
е.
![Problem 4
Let G = (V, E) be a connected, undirected graph. The goal is to determine if there is a
cycle of length >0 (i.e., the mumber of edges in the cycle is { > 0) in G such that l is
divisible by 2. If so, output the cycle, otherwise output Null.
You must use depth-first search todesign an algorithm for the p roblem. That is, let s
be a vertex in G. We do depth-first search (DFS) starting from s, i.c., we will construct
a depth-first s panning t ree r ooted ats .A part from t he g raph G ( represented a s an
adjacency list), the only other data structures you will need in your algorithm are the
arrays visited, parent, and length. The visited and parent arrays are as discussed
in class. Initially, visited[u] = False for all v e V and parentlv] = Null for all v.
The array length is defined as follows. For any node v, length u), is the number of
tree edges in the (unique) path from the root s to the vertex v in the depth-first spanning
tree. Initially, only the length of the root is defined, i.e., length s] = 0 and is undefined
for all other vertices in the graph. When a node is visited for the first time, its length is
set accordingly.
Algorithm DFS based algorithm to determine if a positive even cycle exists.
1: procedure POSITIVE-EVEN-CYCLE(G, 8)
for each v e V do
visited[u] + False
parent v] + Null
length(u]
length s] 0
DFS-VISIT(s)
2:
3:
4:
5:
6:
D Length from root is 0.
7:
(i) Provide the pseudocode for DFS-VISIT that outputs the required solution. Your
pseudocode should be appropriately commented.
(ii) Explain your pseudocode and argue its correctness.
(iii) Illustrate your algorithm by running it on the graph G (Figure 1, ignore the weights),
starting at node s (see Weights and Source Node). Show the length values for all
nodes in the DFS tree.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F646a794d-e587-473e-a1b8-2a8879d17700%2Fd622f951-1cb3-447f-baf6-80895abe6674%2Fyu2zk5_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Problem 4
Let G = (V, E) be a connected, undirected graph. The goal is to determine if there is a
cycle of length >0 (i.e., the mumber of edges in the cycle is { > 0) in G such that l is
divisible by 2. If so, output the cycle, otherwise output Null.
You must use depth-first search todesign an algorithm for the p roblem. That is, let s
be a vertex in G. We do depth-first search (DFS) starting from s, i.c., we will construct
a depth-first s panning t ree r ooted ats .A part from t he g raph G ( represented a s an
adjacency list), the only other data structures you will need in your algorithm are the
arrays visited, parent, and length. The visited and parent arrays are as discussed
in class. Initially, visited[u] = False for all v e V and parentlv] = Null for all v.
The array length is defined as follows. For any node v, length u), is the number of
tree edges in the (unique) path from the root s to the vertex v in the depth-first spanning
tree. Initially, only the length of the root is defined, i.e., length s] = 0 and is undefined
for all other vertices in the graph. When a node is visited for the first time, its length is
set accordingly.
Algorithm DFS based algorithm to determine if a positive even cycle exists.
1: procedure POSITIVE-EVEN-CYCLE(G, 8)
for each v e V do
visited[u] + False
parent v] + Null
length(u]
length s] 0
DFS-VISIT(s)
2:
3:
4:
5:
6:
D Length from root is 0.
7:
(i) Provide the pseudocode for DFS-VISIT that outputs the required solution. Your
pseudocode should be appropriately commented.
(ii) Explain your pseudocode and argue its correctness.
(iii) Illustrate your algorithm by running it on the graph G (Figure 1, ignore the weights),
starting at node s (see Weights and Source Node). Show the length values for all
nodes in the DFS tree.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY