Click here to Skip to main content
15,867,330 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
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).




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)


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


What I have tried:

 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); 
    } 
}
Posted
Comments
Richard MacCutchan 8-Mar-20 13:15pm    
what is the question?
Member 14179777 8-Mar-20 14:14pm    
I need a advice. How to implement this correctly ?
Richard MacCutchan 8-Mar-20 14:17pm    
Try it and see whether it works.
Stefan_Lang 9-Mar-20 3:53am    
It isn't possible to implement that, because the requirements are contradictory! Please make sure you provide the correct definitions and requirements.

I think your definition of 'track' isn't right, or maybe you have an odd interpretation of what 'connected' means.

According to your definition, a track could be visualized like this:

O
|
|
O

or

O
|\
| \
O O


The Os represent the nodes. Is that what you mean? I have to ask because 'track' has no special meaning in graph theory, and I have no idea what your application's understanding of this term is.

"Each track can only be connected to one other track" means that you can only have singular tracks, or a pair of tracks: you can't connect a third, because in a connected pair, each track is already connected to one other track." Note that 'connected' is a symmetric relationship and affects both operands, not just one! If you meant something differnt, you need to use a different term that expresses this, or specify what you mean by 'connected', or just adjust the restriction to appropriately.
Stefan_Lang 9-Mar-20 4:04am    
"Write a method that determines whether it is possible to delete a specific track, provided that the network should not break."

What is a network? (in this context) I have to ask this because according to your previous information there is no sensible interpretation of that term beyond 'set' - which doesn't really help.

Define "break". What does it mean when a network is *not* broken.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900