0

并不是说我有时间适当地讨论这个以得出结论并调整我的代码，因为学校项目的第一阶段（第三阶段）是在 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 它们按此顺序插入到结构City中。然后，我将 A 连接到 B，C 和 D，B 连接到 C，D，E，C 连接到 D，E 和 D 连接到 E。

现在，假设我需要去E市。这是链表中的最后一个，并且需要时间遍历链表。也许不是在这个有 5 个城市的例子中，但在真正的应用程序中，我应该至少支持 10,000 个城市。但是最短的路线是从A（这是起点）从C到E（或者可以是ADE或ABE，没关系）。

我的结构是否允许我找到从 A 到 E 的最短路径，而无需一一遍历整个链表？如果没有，我做错了什么？

如果是，我该怎么做？我不知道我怎么能找到这样的路径......

4

2 回答 2

1

您可以使用称为广度优先搜索(BFS) 的算法。您需要在每个节点上实现一个“颜色”标志才能使用它。请注意，此算法仅在您的边缘未加权时才有效——如果连接了 2 个城市，则它们的距离相等。如果边缘有重量（看起来不像它们），你需要像Dijkstra's Algorithm或A*这样的东西。

于 2009-03-22T00:27:04.937 回答
1

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

第二，你想找到两个给定城市之间的路径。为此，您可能会使用 BFS 算法，您的数据结构就可以了。请注意，BFS 需要 O(V+E) 时间，其中 V 和 E 是诱导子图的顶点和边数，其顶点到起始顶点的距离不大于从起始顶点到结束顶点的距离。这意味着在最坏的情况下，它比遍历城市列表需要更多的时间。

于 2009-03-22T00:29:49.030 回答