2

我正在尝试使用有向图（我知道但从未实现）编写一个程序来模拟交通网络。

用户将输入一个行星名称，后跟一个整数，表示图中的总节点数。然后用户将一个一个地遍历每个节点。他们会给它一个名字，给出节点的邻居数量，然后是具体的名字。输入将如下所示。

some_planet 4
node1 2 node2 node3
node2 1 node4
node3 1 node4
node4 1 node1

然后我只输出 node1 无法到达的节点。但是，我对实现这一点有一些疑问。

1）大的正在存储这些东西。什么是简单的方法？我在考虑一个 LinkedList，并认为我会链接这些位置。然后我可以将指针弹出到它们对应于输入的任何内容。但是，我不知道如何做最后一部分。

2) 下一个大问题是搜索图表。我正计划进行递归深度优先搜索。你看到的这个算法有什么问题吗？我需要以这种方式单独搜索每个节点，所以我必须增加它。我可以把所有东西都放在一个 for 循环中吗？

recursive-d-first-search(graph G, node start, node find)
  if(start == find)
    return true;

  else
    for every neighbor n of start
      success = recursive-d-first-search(graph G, node n, node find);
      if(success)
        return true;

  return false;
4

2 回答 2

2

  1. 我认为你只需要使用邻接矩阵来存储整个图的连接关系。在你的情况下，它应该是这样的：

        1    2    3    4

1   0    1    1    0

2   0    0    0    1

3   0    0    0    1

4   1    0    0    0

  2. 如果您使用邻接矩阵，我认为这breadth-first search可能是一个不错的选择，因为它易于理解和实现。同时，您需要一个队列来存储下一个要检查的节点，以及一个列表来存储哪些节点已经被检查

    例如，您想检查哪些节点node1无法到达，您只需检查第 1 行并查看它有2and 3，然后将 and 放入2队列3。然后检查行2以查看它是否具有4，放入2列表并放入4队列。然后只需使用 for 循环来执行相同的操作。

    最后，您只需要检查哪些节点不在列表中。

于 2012-12-07T03:44:02.387 回答
1

如果您不想重新发明轮子，也可以使用Boost::Graph ...

于 2013-01-09T00:06:03.407 回答