有向图中的深度优先搜索？

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

    }

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

推荐答案

void DFSUtil(int start)的问题在于start不是图形的节点，它只是访问邻接列表的索引，不能用于访问其邻居。在您的情况下，您需要使用label访问邻居列表。

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

并且应该使用该邻接列表来访问当前节点邻居。若要获取当前node的所有路径，请从当前node开始，并在没有剩余的nodes可访问时回溯。创建一个空list以跟踪当前路径，访问node时将其添加到list中，并在回溯时将其从list中删除。

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

若要获取图表中所有节点的所有路径，请为图表中的所有节点启动dfs。

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

这篇关于有向图中的深度优先搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！