有向图中的深度优先搜索？
Depth First Search in Directed Graph?
我有一小列数字。 [4、1、2、5、3、6、8、7]
我的图形设置方式是数组中的每个数字都指向数组中后面所有大于它的数字。 （4 指向 5、6、8 和 7。3 指向 6、8、7 等等）我将这些数字输入到图中，使用邻接表绘制出所有边。我正在尝试使用某种深度优先搜索方法来查找从图中任何起点开始的最长路径的长度。我只是在开始和设置遍历时遇到了一些麻烦，特别是因为后来我想将同一个图用于更大的随机数数组。
这是我的图形代码（我的 DFSUtil 中的计数变量应该用于计算每条路径上的边，然后我打算将它们放入数组或其他东西中以跟踪哪条路径有最多的边（最长路径））：
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);
}
}
这是我的 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 开始 dfs 并在没有 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<>());
}
Bag 类型表示具有开始和结束 Node 的图形。它有一个 Node 的链表（每个 Node 链接到它的 next 节点）。
Graph 类型实际上是一个图形构建器：它为 numbers 中的每个数字构建一个新图形 (Bag)，因此如果您有 100 个数字，它将构建 100 个图形.
无需构建多个图。
构建一个图，并多次运行 dfs，每次都从不同的起始节点开始（可能需要在Bag中进行一些修改）
例如 4, 1, 2, 5, 3, 6, 8, 7 应该用一个 Bag 表示。 运行上面有多个dfs：第一个运行开始一个4，第二个运行开始在1等等。
以下是 mre（可能需要更多测试）
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;
}
}
我有一小列数字。 [4、1、2、5、3、6、8、7]
我的图形设置方式是数组中的每个数字都指向数组中后面所有大于它的数字。 （4 指向 5、6、8 和 7。3 指向 6、8、7 等等）我将这些数字输入到图中，使用邻接表绘制出所有边。我正在尝试使用某种深度优先搜索方法来查找从图中任何起点开始的最长路径的长度。我只是在开始和设置遍历时遇到了一些麻烦，特别是因为后来我想将同一个图用于更大的随机数数组。
这是我的图形代码（我的 DFSUtil 中的计数变量应该用于计算每条路径上的边，然后我打算将它们放入数组或其他东西中以跟踪哪条路径有最多的边（最长路径））：
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);
}
}
这是我的 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 开始 dfs 并在没有 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<>());
}
Bag 类型表示具有开始和结束 Node 的图形。它有一个 Node 的链表（每个 Node 链接到它的 next 节点）。
Graph 类型实际上是一个图形构建器：它为 numbers 中的每个数字构建一个新图形 (Bag)，因此如果您有 100 个数字，它将构建 100 个图形.
无需构建多个图。
构建一个图，并多次运行 dfs，每次都从不同的起始节点开始（可能需要在Bag中进行一些修改）
例如 4, 1, 2, 5, 3, 6, 8, 7 应该用一个 Bag 表示。 运行上面有多个dfs：第一个运行开始一个4，第二个运行开始在1等等。
以下是 mre（可能需要更多测试）
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;
}
}