By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,470 Members | 1,030 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,470 IT Pros & Developers. It's quick & easy.

Algorithm. Depth First Search or DFS for a Graph

P: 1
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).


Question:
Write a method that determines whether it is possible to delete a specific track, provided that the network should not break.

Would you recommend me ?
Create a new graph object and implementing it in a similar way? ( The graph is not a tree, it has many edges and loops)


Expand|Select|Wrap|Line Numbers
  1. lang="java">import java.util.*; 
  2.  
  3. public class GFG 
  4.     // This class represents a directed graph using adjacency 
  5.     // list representation 
  6.     static class Graph 
  7.     { 
  8.         int V; //Number of Vertices 
  9.  
  10.         LinkedList<Integer>[] adj; // adjacency lists 
  11.  
  12.         //Constructor 
  13.         Graph(int V) 
  14.         { 
  15.             this.V = V; 
  16.             adj = new LinkedList[V]; 
  17.  
  18.             for (int i = 0; i < adj.length; i++) 
  19.                 adj[i] = new LinkedList<Integer>(); 
  20.  
  21.         } 
  22.  
  23.         //To add an edge to graph 
  24.         void addEdge(int v, int w) 
  25.         { 
  26.             adj[v].add(w); // Add w to vís list. 
  27.         } 
  28.  
  29.         // prints all not yet visited vertices reachable from s 
  30.         void DFS(int s) 
  31.         { 
  32.             // Initially mark all vertices as not visited 
  33.             Vector<Boolean> visited = new Vector<Boolean>(V); 
  34.             for (int i = 0; i < V; i++) 
  35.                 visited.add(false); 
  36.  
  37.             // Create a stack for DFS 
  38.             Stack<Integer> stack = new Stack<>(); 
  39.  
  40.             // Push the current source node 
  41.             stack.push(s); 
  42.  
  43.             while(stack.empty() == false) 
  44.             { 
  45.                 // Pop a vertex from stack and print it 
  46.                 s = stack.peek(); 
  47.                 stack.pop(); 
  48.  
  49.                 // Stack may contain same vertex twice. So 
  50.                 // we need to print the popped item only 
  51.                 // if it is not visited. 
  52.                 if(visited.get(s) == false) 
  53.                 { 
  54.                     System.out.print(s + " "); 
  55.                     visited.set(s, true); 
  56.                 } 
  57.  
  58.                 // Get all adjacent vertices of the popped vertex s 
  59.                 // If a adjacent has not been visited, then push it 
  60.                 // to the stack. 
  61.                 Iterator<Integer> itr = adj[s].iterator(); 
  62.  
  63.                 while (itr.hasNext()) 
  64.                 { 
  65.                     int v = itr.next(); 
  66.                     if(!visited.get(v)) 
  67.                         stack.push(v); 
  68.                 } 
  69.  
  70.             } 
  71.         } 
  72.     } 
  73.  
  74.     // Driver program to test methods of graph class 
  75.     public static void main(String[] args) 
  76.     { 
  77.         // Total 5 vertices in graph 
  78.         Graph g = new Graph(5); 
  79.  
  80.         g.addEdge(1, 0); 
  81.         g.addEdge(0, 2); 
  82.         g.addEdge(2, 1); 
  83.         g.addEdge(0, 3); 
  84.         g.addEdge(1, 4); 
  85.  
  86.         System.out.println("Following is the Depth First Traversal"); 
  87.         g.DFS(0); 
  88.     } 
  89. }
2 Weeks Ago #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.