Can you explain what the program is doing?
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
100%
Can you explain what the
![2 mport java.io.*;
3 import java.util.*;
4 //Undirected Graph Class
5 class Main {
6 //Number of Vertices
7 private int V;
8 //Adjacency Lists
9 private LinkedList<Integer> adj[];
10 //Constructor
11 Main (int v) {
12 V = V;
13 adj = new LinkedList[v];
14 for (int i = 0; i < v; ++i)
15 adj[i] = new LinkedList();
16
}
17
18 // Function that adds an edge to the graph
19 void addEdge(int v, int w) {
20 adj[v].add(w);
21 adj [w].add(v);
22 }
24
// A recursive cyclicUtil function
25 ▼ Boolean isCyclicUtil(int v, Boolean visited [], int parent) {
26
27 //Marks the current node as visited
28 visited [v] = true;
29 Integer i;
30
31
32
33 while (it.hasNext()) {
34 iit.next();
35
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> it = adj[v]. iterator();
36 // If an adjacent is not visited, call for the cyclicutil method
37 if (!visited[i]) {
38 if (isCyclicUtil(i, visited, v))
39 return true;
40 }
41 // If an adjacent is visited and not parent of current vertex, then there is a cycle
42 else if (i != parent)
43 return true;
44 }
45 return false;
46 }
47 // Returns true if the graph contains a cycle, else false.
48 Boolean isCyclic() {
49
50
// Mark all the vertices as not visited and not part of
recursion stack
61
62
51
52 for (int i = 0; i < V; i++)
53 visited[i] = false;
54
55
56
57
58
59
60
Boolean visited [] = new Boolean [V];
// Begins iterating through the vertices
for (int i = 0; i < V; i++)
//Doesn't recur if already visited
if (!visited[i])
if (isCyclicUtil(i, visited, 1))
return true;
return false;
63}
64 //Driver Method
65 ▼ public static void main(String[] args) {
66 //Graph creation
67 Scanner Edges = new Scanner(System.in);
68
System.out.println("Enter the number of edges.");
69
int edges
70
Main g = new Main(edges);
71 ▼ for(int i = 0; i < (edges); i++) {
72 System.out.println("Enter the pair of vertices for this edge: ");
73
74
75
76
77
int holding1 = Edges.nextInt();
int holding2= Edges.nextInt();
g.addEdge (holding1, holding2);
}
Edges.nextInt();
78 //Cycle check
79
80
81
82
if (g.isCyclic())
System.out.println("Graph contains cycle");
System.out.println("Graph doesn't contain cycle");
else
83}
84 }](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F4cd5838b-3f34-487e-9642-7770197fe05c%2F2cccd462-2ea1-4406-9870-c666214e7501%2Fr0fyja_processed.png&w=3840&q=75)
Transcribed Image Text:2 mport java.io.*;
3 import java.util.*;
4 //Undirected Graph Class
5 class Main {
6 //Number of Vertices
7 private int V;
8 //Adjacency Lists
9 private LinkedList<Integer> adj[];
10 //Constructor
11 Main (int v) {
12 V = V;
13 adj = new LinkedList[v];
14 for (int i = 0; i < v; ++i)
15 adj[i] = new LinkedList();
16
}
17
18 // Function that adds an edge to the graph
19 void addEdge(int v, int w) {
20 adj[v].add(w);
21 adj [w].add(v);
22 }
24
// A recursive cyclicUtil function
25 ▼ Boolean isCyclicUtil(int v, Boolean visited [], int parent) {
26
27 //Marks the current node as visited
28 visited [v] = true;
29 Integer i;
30
31
32
33 while (it.hasNext()) {
34 iit.next();
35
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> it = adj[v]. iterator();
36 // If an adjacent is not visited, call for the cyclicutil method
37 if (!visited[i]) {
38 if (isCyclicUtil(i, visited, v))
39 return true;
40 }
41 // If an adjacent is visited and not parent of current vertex, then there is a cycle
42 else if (i != parent)
43 return true;
44 }
45 return false;
46 }
47 // Returns true if the graph contains a cycle, else false.
48 Boolean isCyclic() {
49
50
// Mark all the vertices as not visited and not part of
recursion stack
61
62
51
52 for (int i = 0; i < V; i++)
53 visited[i] = false;
54
55
56
57
58
59
60
Boolean visited [] = new Boolean [V];
// Begins iterating through the vertices
for (int i = 0; i < V; i++)
//Doesn't recur if already visited
if (!visited[i])
if (isCyclicUtil(i, visited, 1))
return true;
return false;
63}
64 //Driver Method
65 ▼ public static void main(String[] args) {
66 //Graph creation
67 Scanner Edges = new Scanner(System.in);
68
System.out.println("Enter the number of edges.");
69
int edges
70
Main g = new Main(edges);
71 ▼ for(int i = 0; i < (edges); i++) {
72 System.out.println("Enter the pair of vertices for this edge: ");
73
74
75
76
77
int holding1 = Edges.nextInt();
int holding2= Edges.nextInt();
g.addEdge (holding1, holding2);
}
Edges.nextInt();
78 //Cycle check
79
80
81
82
if (g.isCyclic())
System.out.println("Graph contains cycle");
System.out.println("Graph doesn't contain cycle");
else
83}
84 }
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 with 1 images
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