穿越一个无向、无权图的技巧：最少访问每个节点。

Question

我正在尝试编写遍历无向、无权图的代码。实际上，该方法将传递一个节点（该节点知道其所有邻居）。然后，该方法必须通过从节点到节点并收集连接彼此的节点的信息来有效地建立图形模型。最终，该方法将拥有完整的节点列表和连接它们的所有顶点的列表。

问题的关键在于“有效”这个词以及我的意思是什么。让我引起您对这个小图的注意：

让我们假设我从节点G开始。我可以访问C、B、F、D、H、J或E。我想要最小化访问节点的次数，并且为了访问一个节点，我必须通过通往该节点的所有节点。

例如：假设我决定访问节点C。下一个要访问的节点可以是A、B、F、D、H、J或E。但是，要访问除A以外的任何节点，我都必须再次经过G，这被认为是低效的。而要访问A，我必须再次访问G和C，然后穿过C再回到图的其他部分。所以我决定访问A。这意味着我必须再次穿过C才能到达G。因此，从逻辑上讲，最好最后访问C分支。

然而，当程序从节点G开始时，不知道分支C通向死路。当我写这篇文章时，我认为这是不可能的，但我还是问了一下：有没有办法仅使用给定的信息（即程序只知道它访问过的节点和从这些节点发出的边缘）尽可能有效地遍历这个图？或者我应该采用Dijkstra算法的变化来确保我访问每个节点？

如果需要，所有内容将用Java编写。

- Smipims

Answer 1

您是想简单遍历整个图（不考虑路径），并对每个节点执行某些操作，还是想计算从一个节点到任何其他节点的最短路径？（我可能不理解您的目标。）

在第一种情况下，请使用遍历算法，例如广度优先搜索。对于另一种情况，您可以考虑使用Dijkstra算法，使用相同权重的边（即= 1）。

当您只关心一个起始节点且所有边具有相同的权重时，可以将BFS视为Dijkstra的特殊情况。如果成本不同，则可以使用统一成本搜索。

- rano

---

考虑到存在许多循环，使用 DFS 是否更有效率？我想我可以编写两个算法并通过多个数据集进行实验来找出答案。我不敢相信我居然忘了这个，但这可能是最好的答案。谢谢！ - Smipims

@Smipims，广度优先搜索或Djikstra算法在循环方面与递归并没有更好或更差的表现。为了访问所有节点，您需要访问所有节点。使用非递归解决方案可能有优势，可以避免太深的调用堆栈（对于大型图形）。 - Martin Algesten

我想这完全取决于你拥有的资源以及你更加重视的是什么：时间和/或内存空间。请考虑，您必须跟踪BFS中已扩展但尚未访问的节点。如果您的图可以全部保存在内存中，那么我想这并不重要（但请想象一下您只能逐个节点地探索的隐式图）。 - rano

@Martin Algesten：所有图遍历算法（BFS、DFS、UCS等）都可以视为广义图搜索;) - rano

确实。唉，我只是讨厌我的答案没有被接受，因为提问者不理解所提出的解决方案之间的区别。但是感谢您理解我的困境 - 这里有一票支持广度优先 :) - Martin Algesten

Answer 2

一个有趣的问题...但是从迄今为止的回复中仍然不清楚原始问题/目标是什么。

这是问题的有效重新陈述吗？：

- 指定起始节点 - 访问每个节点的成本为“1” - 目标：访问每个节点 - 目标：规划一条最小化成本的路线 - 约束条件：未指定最终节点（可以是任何节点） - 算法在产生任何成本之前就已经完全了解图形（搜索每条可能的路径本身不会产生任何成本）

如果这是您问题的正确“读取”，那么请考虑以下观察：

- 如果“访问节点”的成本为“1”，那么“遍历任何边缘”的成本也为“1”...因为“访问节点”和“遍历边缘”之间存在一对一的对应关系。 （您不能通过遍历其入边进入节点。） - 如果两个节点没有直接连接，则它们仍然“传递性连接”，因为您可以简单地遍历介于它们之间的节点。 （或者：您似乎没有约束“您不能重新访问节点”。）

因此：所有节点都通过某种“距离”相互“连接”，您希望访问所有节点，同时最小化所需的“距离”。

是这样吗？

如果是这样，我认为您的问题几乎与经典的“旅行商问题”完全相同。我唯一看到的区别是有时TSP的陈述要求“起始节点和结束节点相同”。但是 - 我认为 - 您允许起始节点和结束节点不同。

如果听起来正确 - 并且您真的只是试图以有效的方式“解决”TSP - 那么请加入前面已经尝试过做同样事情的人们！可能没有比“尝试所有组合，对每个进行评分并取最小值”更好的解决方案。

- Dan H

Answer 3

只需要一个带有收集参数的简单递归，不就可以了吗？

public void traverse(Node n, Set<Node> visisted) {

  visited.add(n);

  for (Node neighbour : n.getNeighbours()) {

    if (!visited.contains(neighbour)) {
      traverse(neighbour, visited);
    }

  }

}

- Martin Algesten

---

不，我不这么认为，因为在这种情况下遍历的顺序很重要。我的想法是我要亲自访问每个节点。所以从G到H再到G再到J与从G到H再到J是不同的。你可能是对的，而我可能在整天工作后想太多了。 - Smipims

“遍历顺序很重要”是什么意思 - 你需要的是哪个顺序？访问节点是否有相关成本？ - Martin Algesten

访问节点的成本是到达该节点所需的步骤数。因此，通过 G 到 H 再到 G 再到 J 访问 J 的成本为 3，但通过 G 到 H 到 J 访问 J 的成本为 2。但我认为 rano 给出了我要找的答案。感谢您的帮助。 - Smipims

Answer 4

这是遍历图的所有节点并计算最小遍历成本的方法，希望能对您有所帮助。

package capgemni;
/**
*
* @author amit
*/
public class Graphtraversing {
public static void main(String[] args) {
    int res = 0;
    String[] input1= {"A", "B", "C", "D"};
    int[] input2 = {4, 8, 6, 3, 3, 5};

    res = minimum_cost(input1, input2);
    System.out.println(res);

}
static int minimum_cost(String[] input1,int[] input2)
{
    int d = input1.length;
    int costmatrix[][]=new int[input1.length][input1.length];
    int i=0,j=0,k=0;


    for(i=0;i<input1.length;i++){
    for(j=i;j<input1.length;j++){
        costmatrix[i][j]=0;
    }
    }

    for(i=0;i<input1.length;i++){
    for(j=i;j<input1.length;j++){
        if(i==j){
        costmatrix[i][j] = 0;
        }
else{
        costmatrix[i][j] = input2[k];
        k++;
}

    }
    }

for(i=0;i<input1.length;i++){
for(j=0;j<input1.length;j++){
    costmatrix[j][i] = costmatrix[i][j];
}
}

int cost = 0;
int mcost = 0;
int first = 1;
for(i=0; i<input1.length; i++){

for(j=0; j<input1.length; j++){

    cost = cost + costmatrix[i][j];

}
if(first == 1 ){
mcost = cost;
first = 0;
}
else if(cost < mcost){
mcost = cost;
}
cost = 0;
}


    return mcost;
}
}

- Amit Singh Tariyal