如何在搜索在C图结构特定节点？

Question

这并不是说我有时间好好讨论这个问题达成结论和适应我的代码，因为学校项目的第一阶段（三）是24小时，但至少我需要知道，如果我做了正确的决定。

我使用链表，这里是我的结构：

typedef struct sCity {
    int cityID;
    char *cityName;

    struct sCityLink *links;
    struct sCity *next;
} nCity, *City;

typedef struct sCityLink {
    City cityLinkParent;
    City cityLinkTo;

    struct sCityLink *next;

} nCityLink, *CityLink;

基本上，我有很多城市和那些城市链接一起，像的图。例如，A，B，C，d和E它们被插入以该顺序进入结构的城市即可。然后，I A连接到B，C和d，B到C，d，E，C到d和E和d至E

现在，让我们说我需要去城市E.这是链表中的最后一个，它需要时间来遍历链表的所有道路。也许不是在这个例子中有5个城市，但在实际应用我应该支持像至少10,000个城市。但是最短的路线是从C A（其为起点）到E（或者它可以是A-d-E或A-B-E，并不重要）。

做我的结构，让我找到从A到E的最短路线，而无需遍历一个链表一个整体？如果不是这样，我在做什么错了？

如果是，我该怎么办呢？我没有线索，我怎么能找到这样的路径...

Answer 1

有两个不同的问题 - 一个，你可能想找到一个市指针城市ID（如“E”）。你不能这样做，在不到你的结构线性时间;如果你需要更快，使用哈希表或二叉搜索树。

二，你想找到两个给定的城市之间的路径。为此，您可能会使用的BFS算法，对此您的数据结构就好了。需要注意的是BFS取其中V和E是导出子的顶点距离起始顶点不大于从开始到结束顶点的距离的顶点和边缘计数O（V + E）的时间。这意味着在最坏的情况下，它需要更多的时间比穿过城市的列表。

Answer 2

您可以使用名为广度优先搜索（BFS）。您需要实现每个节点上的“颜色”标志使用它。请注意，如果您的边缘该算法只适用的加权 - 如果2个城市连接，那么它们是相等的距离。 如果边缘有重量（它并不像他们这样做），你需要像 Dijkstra算法或 A * 。