Depth First Search in Directed Graph?

Question

I have a small array of numbers. [4, 1, 2, 5, 3, 6, 8, 7]

The way my graph is set up is that each number in the array is pointing to all numbers larger than it later on in the array. (4 is pointing to 5, 6, 8, and 7. 3 is pointing to 6, 8, 7. Etc.) I input these numbers into the graph, using an adjacency list to map out all the edges. I'm trying to use some sort of Depth First Search method to find the length of the longest path from any starting point in the graph. I'm just having some troubles getting the traversal started and set up, especially since later on I want to use this same graph for a much larger array of random numbers.

Here is my code for my Graph (also the count variable in my DFSUtil is supposed to be used to count the edges on each path, and then I was going to put those into an array or something to keep track of which path had the most edges (longest path)):

import java.util.NoSuchElementException;

public class Graph {
    private static final String NEWLINE = System.getProperty("line.separator");

    public final int V;                     // initializing variables and data structures
    private int E = 0;
    public Bag<Integer>[] adj;
    
    public Graph(int[] numbers) {
        
        try {
            this.V = numbers.length;    
            adj = (Bag<Integer>[]) new Bag[V];                      // bag initialized
            for (int v = 0; v < V; v++) {
                adj[v] = new Bag<Integer>();                            // indices are initialized
            }
            for (int i = 0; i < V; i++) {
                adj[i].label = numbers[i];
                int j = (i + 1);
                while (j < numbers.length) {
                    if (numbers[i] < numbers[j]) {
                        addEdge(i, numbers[j]);
                    }
                    j++;
                }
            }
        }
        catch (NoSuchElementException e) {
            throw new IllegalArgumentException("invalid input format in Graph constructor", e);
        }
    }
    
    public void addEdge(int index, int num) {
        E++;                                            // number of edges increases
        adj[index].add(num);                            // indexes into bag
    }
    
    public void print() {
        for (int i = 0; i < adj.length; i++) {
            System.out.print(adj[i].label + ": ");
            for (int w : adj[i]) {
                System.out.print(w + " ");
            }
            System.out.println("");
        }
    }
    
    
    public int getIndex(int num) {
        for (int i = 0; i < adj.length; i++) {
            if (adj[i].label == num) {
                return num;
            }
        }
        return -1;
        
    }
    
    void DFSUtil(int start)
    {
        while (start < adj.length) {
            System.out.print(start + " ");
            int a = 0;
            int count = 0;
     
            for (int i = 0; i < adj[start].edges; i++)  //iterate through the linked list and then propagate to the next few nodes
                {
                    int j = 0;
                    for (int num : adj[start]) {
                        if (j == i) {
                            a = getIndex(num);
                        }
                        j++;
                    }
                    count++;
                    DFSUtil(a);
                } 
            start++;
        }
    }

    void DFS()
    {
        DFSUtil(0);
    }
    
}

And here is the code for my Bag method:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;    // beginning of bag
    private Node<Item> end;
    private int n;               // number of elements in bag
    public int label;
    public int edges;

    public static class Node<Item> {
        private Item item;                  
        private Node<Item> next;
        public int label;
        public int edges;
    }

    public Bag() {
        first = null;                           // empty bag initialized
        end = null;
        n = 0;
    }
    
    public void add(Item item) {
        if (n==0) {
            Node<Item> head = new Node<Item>();     // if bag is empty
            first = head;
            end = head;
            head.item = item;           // new node both first and end of bag
            edges++;
            n++;
        }
        else {
            Node<Item> oldlast = end;           // old last assigned to end of node
            Node<Item> last = new Node<Item>();
            last.item = item;
            oldlast.next = last;                // new node added after old last
            end = last;
            n++;                                    // size increased
            edges++;
        }
    }
    
    public int size() {
        return n;
    }
    
    public void print() {
        Node<Item> current = first;
        for (int i = 0; i < n; i++) {               // starting at front of bag
            System.out.println(current.item);       // prints item, moves to next
            current = current.next;
        }
    }


    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);           // returns an iterator that iterates over the items in this bag in arbitrary order
    }


    public class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;                                            // iterator starts at head of bag
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();             // if there is next item, current is moved to next
            Item item = current.item;
            current = current.next; 
            return item;                                        // item is returned
        }
    }

}

And then this is all I have in my main function:

    public static void main(String[] args) {
        int[] num = {4, 1, 2, 5, 3, 6, 8, 7};
        Graph G = new Graph(num);
        G.print();
        G.DFS();

    }

I've been trying to get some sort of recursive method going for my search, but I'm having troubles getting the logistics down. Any help would be appreciated!

Answer 1

Bag type represents a graph with a start and end Node. It has a linked list of Nodes (each Node is linked to its next node).

Graph type is actually a graph builder: it builds a new graph (Bag) for every number in numbers, so if you have 100 numbers it will build 100 graphs.
There is no need to build multiple graphs.
Build one graph, and run dfs multiple times, each starting at a different start node (it may require some modifications in Bag)
For example 4, 1, 2, 5, 3, 6, 8, 7 should be represented with one Bag. Run multiple dfs on it: first run starts a 4, second run starts at 1 and so on.

The following is a mre (which may require some more testing)

    import java.util.*;
    
    public class Driver {
    
        public static void main(String[] args) {
    
            List<Integer> num1 =  Arrays.asList(1,2,3,4, 1, 2, 5, 3, 6, 8, 7);
            DFS dfs = new DFS(num1);
            System.out.println(dfs.getGraph());
            System.out.println("The length of longest path for this sequence with graph is: " + dfs.dfsStart());
        }
    }
    
    class DFS {
    
        public int longestPath;
        private final Graph graph;
    
        public DFS(List<Integer> numbers) {
            graph = new Graph(numbers);
        }
    
        public int dfsStart() {
            for (Node node :  graph.nodes) {
                depthFirstSearch(node,new ArrayList<>());
            }
            return longestPath;
        }
    
        public void depthFirstSearch(Node src, List<Node> current) {
            current.add(src);
            Node next = src.getNext();
            if (next != null) {
                longestPath = Math.max(longestPath, current.size());
                depthFirstSearch(next, current);
            }
        }
    
        public Graph getGraph(){
            return graph;
        }
    }
    
    class Graph {
    
        List<Node> nodes;
    
        public Graph(List<Integer> numbers) {
    
            nodes = new ArrayList<>();
            for(int number : numbers){
                nodes.add(new Node(number));
            }
    
            for (int i = 0; i <nodes.size()-1; i++) {
                Node next = null;
                for(int j = i+1; j < nodes.size(); j++){
                    if(nodes.get(j).getLabel() > nodes.get(i).getLabel() ){
                        if(next == null || next.getLabel() > nodes.get(j).getLabel() ) {
                            next = nodes.get(j);
                        }
                    }
                    nodes.get(i).setNext(next);
                }
            }
        }
    
        @Override
        public String toString() {
    
            StringBuilder sb  = new StringBuilder();
            for(Node node: nodes){
                sb.append(node.getLabel());
                if(node.getNext() != null){
                    sb.append(" next > "  + node.getNext().getLabel());
                }
                sb.append("\n");
            }
            return sb.toString();
        }
    }
    
    class Node {
    
        private Node next = null;
        private final int label;
    
        public Node(int label) {
            this.label = label;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    
        public int getLabel() {
            return label;
        }
    }

Answer 2

The problem with your void DFSUtil(int start) is that start is not a node of your graph, it's just an index to access your adjacency list and cannot be used to access its neighbors. In your case, you need to use the label to access the neighbor list.

public Bag<Integer> getAdjList(int src) {
    Bag<Integer> adjList = null;
    for (Bag<Integer> list : adj) {
        if (list.label == src) {
            adjList = list;
            break;
        }
    }
    return adjList;
}

And this adjacency list should be used to access current node neighbors. To get all the paths from a current node start dfs from the current node and backtrack when there are no nodes left to visit. Create an empty list to track the current path, when visiting a node add it to the list and remove it from the list when backtracking.

public void dfs(int src, ArrayList<Integer> curr) {
    curr.add(src);
    Bag<Integer> srcAdj = getAdjList(src);
    if (srcAdj.size() == 0) {
        // Leaf node
        // Print this path
        System.out.println(curr.toString());
    }
    for (int neighbor : srcAdj) {
        dfs(neighbor, curr);
    }
    curr.remove(curr.size()-1);
}

To get all the paths from all nodes in your graph, start dfs for all the nodes in your graph.

int[] num = {4, 1, 2, 5, 3, 6, 8, 7};
Graph G = new Graph(num);
G.print();
for (int i=0;i<num.length;i++) {
    // Print all paths from current node
    G.dfs(num[i],new ArrayList<>());
}