有向图中的深度优先搜索？-Java问题

Depth First Search in Directed Graph?(有向图中的深度优先搜索？)

本文介绍了有向图中的深度优先搜索？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有一个小数字数组。[4，1，2，5，3，6，8，7]

我的图表的设置方式是，数组中的每个数字都指向数组中比它后面更大的所有数字。(4指向5、6、8和7.3。3指向6、8、7等。)我将这些数字输入到图表中，使用邻接列表绘制出所有的边。我正在尝试使用某种深度优先搜索法来找出从图中的任何起点开始的最长路径的长度。我只是在开始和设置遍历时遇到了一些问题，特别是因为稍后我想使用相同的图来处理更大的随机数组。

以下是我的Graph代码(DFSUtil中的count变量也应该用来计算每条路径上的边，然后我打算将这些变量放入一个数组或其他东西中，以跟踪哪条路径的边最多(最长路径))：

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);
    }
    
}

以下是My Bag方法的代码：

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
        }
    }

}

然后这就是我的主函数中的全部内容：

    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();

    }

我一直在尝试使用某种递归方法进行搜索，但在执行后勤工作时遇到了麻烦。如有任何帮助，我们将不胜感激！