There is a network of tracks (list), tracks are of two types - standard (with one start and one end point) and with a fork ( one start and two end points). These points are called nodes. It is known that each track can only be connected to one other track. Thus, each node is connected to at least one other node, with a maximum of three nodes (if this is the starting point of the track with a fork).
Create a new graph object and implementing it in a similar way? ( The graph is not a tree, it has many edges and loops)
Write a method that determines whether it is possible to delete a specific track, provided that the network should not break.
lang="java">import java.util.*; public class GFG { // This class represents a directed graph using adjacency // list representation static class Graph { int V; //Number of Vertices LinkedList<Integer>[] adj; // adjacency lists //Constructor Graph(int V) { this.V = V; adj = new LinkedList[V]; for (int i = 0; i < adj.length; i++) adj[i] = new LinkedList<Integer>(); } //To add an edge to graph void addEdge(int v, int w) { adj[v].add(w); // Add w to v’s list. } // prints all not yet visited vertices reachable from s void DFS(int s) { // Initially mark all vertices as not visited Vector<Boolean> visited = new Vector<Boolean>(V); for (int i = 0; i < V; i++) visited.add(false); // Create a stack for DFS Stack<Integer> stack = new Stack<>(); // Push the current source node stack.push(s); while(stack.empty() == false) { // Pop a vertex from stack and print it s = stack.peek(); stack.pop(); // Stack may contain same vertex twice. So // we need to print the popped item only // if it is not visited. if(visited.get(s) == false) { System.out.print(s + " "); visited.set(s, true); } // Get all adjacent vertices of the popped vertex s // If a adjacent has not been visited, then push it // to the stack. Iterator<Integer> itr = adj[s].iterator(); while (itr.hasNext()) { int v = itr.next(); if(!visited.get(v)) stack.push(v); } } } } // Driver program to test methods of graph class public static void main(String[] args) { // Total 5 vertices in graph Graph g = new Graph(5); g.addEdge(1, 0); g.addEdge(0, 2); g.addEdge(2, 1); g.addEdge(0, 3); g.addEdge(1, 4); System.out.println("Following is the Depth First Traversal"); g.DFS(0); } }
O||OorO|\| \O O
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)