如何在C中搜索图结构中的特定节点?

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

现在,假设我需要去城市E.这是链表中的最后一个,并且一直遍历链表需要时间。 也许不是这个有5个城市的例子,但在真正的应用程序中,我应该至少支持10,000个城市。 但最短路径是从A到C(也就是起点)从E到E(或者它可能是ADE或ABE,无所谓)。

我的结构是否允许我找到从A到E的最短路径,而不是逐个遍历整个链表? 如果没有,我做错了什么?

如果是的话,我该怎么做? 我不知道怎样才能找到这样的路径……

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

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

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