CODEWITHSUNDEEP
javaalgorithmgraphdepth-first-searchgraph-traversal
user14587018
user14587018

Reputation:

DFS (depth first search) sequence of nodes

I want to implement dfs for nodes that are of type long in Java.

My algorithm calculates correctly the number of nodes, and the number

of edges, but not the sequence of nodes. Could you please help me

modify my algorithm so I calculate the order in which the nodes are

visited, correctly?

This is my code:

private int getNumberOfNodes(long firstNode) {  
    List<Long> marked = new ArrayList<>();  //------------------------------------------->
    Stack<Long> stack = new Stack<Long>();  //step 1  Create/declare stack
    stack.push(firstNode);                  //Step 2 Put/push inside the first node
    while (!stack.isEmpty()) {              //Repeat till stack is empty:
       Long node = stack.pop();             //Step 3 Extract the top node in the stack
       marked.add(node);                    //------------------------------------------->
       long[] neighbors = xgraph.getNeighborsOf(node); //Get neighbors
       if (neighbors.length % 2 == 0) {
           
       } else {
           numOfNodesWithOddDegree++;
       }
       int mnt = 0;
       for (long currentNode : neighbors) {
           if (!marked.contains(currentNode) && !stack.contains(currentNode) ) { //&& !stack.contains(currentNode)  
               stack.push(currentNode);

           } else {
               
           }
           if (!marked.contains(currentNode)) {
               numOfEdges++;
           }
       }
    }
    return marked.size(); //(int) Arrays.stream(neighbors).count();
}

Upvotes: 0

Views: 561

Answers (1)

bob tang
bob tang

Reputation: 593

I guess you exam the marked list for the sequence.

As your graph is undirected, the sequence of traversals could be varied based on which neighbor you pushed into the stack first. which means the logic of your function:

 xgraph.getNeighborsOf(node)

could impact your sequence. see Vertex orderings from this wiki https://en.wikipedia.org/wiki/Depth-first_search

so my conclusion is: you may have a different traversal sequence, it does not mean your DFS is wrong, as long as it is Deep first search, it is ok to be a little bit different from the given answer.

Upvotes: 1

Related Questions