关于如何接近有向图的想法

我正在尝试使用有向图（我知道但从未实现过）来模拟运输网络来编写程序。关于如何接近有向图的想法

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

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;

来源

2012-12-07 ViscousRandom

图形通常存储为[邻接表（http://en.wikipedia.org/wiki/ Adjacency_list）或[adjacency matrices]（http://en.wikipedia.org/wiki/Adjacency_matrix）。您在问题中的输入实际上是一个邻接列表。 – YXD

我想你只需要使用邻接矩阵来存储整个图形的连接关系。在你的情况下，它应该是这样的：
```
1 2 3 4 

1 0 1 1 0 

2 0 0 0 1 

3 0 0 0 1 

4 1 0 0 0 
```
如果使用邻接矩阵，我觉得breadth-first search可能是一个不错的选择，因为它很容易理解和执行。同时，您需要一个队列来存储要检查的下一个节点，以及一个列表来存储已检查哪些节点。

例如，要检查node1无法到达的节点，只需检查第1行并查看它有2和3，并把2和3排队。然后检查行2以查看它有4，将2列出，并将4放入队列。然后使用for循环来执行相同的操作。

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

来源

2012-12-07 03:44:02 bhuang3

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

来源

2013-01-09 00:06:03 DanDan

关于如何接近有向图的想法

回答

相关问题