本文介紹了有向圖中的深度優(yōu)先搜索？的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧！
問題描述
我有一個小數(shù)字?jǐn)?shù)組。[4，1，2，5，3，6，8，7]
我的圖表的設(shè)置方式是，數(shù)組中的每個數(shù)字都指向數(shù)組中比它后面更大的所有數(shù)字。(4指向5、6、8和7.3。3指向6、8、7等。)我將這些數(shù)字輸入到圖表中，使用鄰接列表繪制出所有的邊。我正在嘗試使用某種深度優(yōu)先搜索法來找出從圖中的任何起點(diǎn)開始的最長路徑的長度。我只是在開始和設(shè)置遍歷時遇到了一些問題，特別是因?yàn)樯院笪蚁胧褂孟嗤膱D來處理更大的隨機(jī)數(shù)組。
以下是我的Graph代碼(DFSUtil中的count變量也應(yīng)該用來計算每條路徑上的邊，然后我打算將這些變量放入一個數(shù)組或其他東西中，以跟蹤哪條路徑的邊最多(最長路徑))：
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
}
}
}
然后這就是我的主函數(shù)中的全部內(nèi)容：
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();
}
我一直在嘗試使用某種遞歸方法進(jìn)行搜索，但在執(zhí)行后勤工作時遇到了麻煩。如有任何幫助，我們將不勝感激！
推薦答案
void DFSUtil(int start)的問題在于start不是圖形的節(jié)點(diǎn)，它只是訪問鄰接列表的索引，不能用于訪問其鄰居。在您的情況下，您需要使用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;
}
并且應(yīng)該使用該鄰接列表來訪問當(dāng)前節(jié)點(diǎn)鄰居。若要獲取當(dāng)前node的所有路徑，請從當(dāng)前node開始，并在沒有剩余的nodes可訪問時回溯。創(chuàng)建一個空list以跟蹤當(dāng)前路徑，訪問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);
}
若要獲取圖表中所有節(jié)點(diǎn)的所有路徑，請為圖表中的所有節(jié)點(diǎn)啟動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<>());
}
這篇關(guān)于有向圖中的深度優(yōu)先搜索？的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
