c - 如何在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，它们按此顺序插入到结构 City 中。然后，我将 A 连接到 B、C 和 D、B 连接到 C、D、E、C 连接到 D、E 连接到 D。

现在，假设我需要去E市，这是链表中的最后一个，一路遍历链表需要时间。也许不是在这个有 5 个城市的例子中，但在真实的应用程序中我应该至少支持 10,000 个城市。但最短的路线是从A(这是起点)到C到E(也可以是A-D-E或A-B-E，无所谓)。

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

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

Answer 1

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

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