Tag: 图论 理论

如何在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的最短路径，而不是逐个遍历整个链表？ 如果没有，我做错了什么？ 如果是的话，我该怎么做？ 我不知道怎样才能找到这样的路径……