如何搜索中在C图结构特定节点？ [英] How to search a specific node in a graph structure in C?
问题描述
这并不是说我有时间好好讨论这个问题得出结论，适应我的code学校项目的，因为一个阶段（三）是24小时，但至少我需要知道，如果我做了正确的决定。
Not that I have time to discuss this properly to reach a conclusion and adapt my code because the phase one (of three) of a school project is in 24hrs, but at least I need to know if I did the correct decision.
我使用链表，这里是我的结构：
I'm using linked lists and here's my structures:
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它们插入这个顺序进入结构的城市。然后，我一连接到B，C和D，B到C，D，E，C到D和E和D到E
Basically, I have lots of cities and those cities are linked all together, like a graph. For instance, A, B, C, D and E they are inserted in this order into the structure City. Then, I connect A to B, C and D, B to C, D, E, C to D and E and D to E.
现在，让我们说我需要去城市E.这是链表中的最后一个，它需要时间来遍历链表的所有道路。也许不是在这个例子中有5个城市，但真正的应用程序我应该支持像至少10,000个城市。但是，最短的路线是从C A（这是起点）到E（也可能是A-D-E或A-B-E，无所谓）。
Now, let's say I need to go to city E. This is the last one in the linked list and it takes time to traverse the linked list all the way. Maybe not on this example with 5 cities but in the real app I'm supposed to support like 10,000 cities at least. But the shortest route is from A (which is the starting point) from C to E (or it could be A-D-E or A-B-E, doesn't matter).
做我的结构，让我找到从A到E的最短路径，而无需遍历一个链表一个整体？如果不是这样，我在做什么错了？
Do my structures allow me to find the shortest route from A to E without traversing the whole linked list one by one? If not, what I'm doing wrong?
如果有，我该怎么办呢？我没有线索我怎么能找到这样的路径...
If yes, how can I do that? I don't have a clue how can I find such a path...
推荐答案
有两个不同的问题 - 一个，你可能想找到一个城市的指针对于一个城市ID（如E）。你不能这样做，在不到你的结构线性时间;如果你需要它速度更快，使用哈希表或二叉搜索树。
There are two separate issues - one, you probably want to find a City pointer for a city ID (eg. "E"). You cannot do that in less than linear time with your structures; if you need it faster, use a hashtable or binary search tree.
二，你想找到两个特定城市之间的路径。为此，您可能会使用的BFS算法，对此您的数据结构是就好了。请注意，BFS需要其中V和E是引起子的顶点'的距离从一开始顶点并不比从开始到结束顶点的距离更大的顶点和边缘计数O（V + E）的时间。这意味着在最坏的情况下，它需要更多的时间比遍历城市列表
Two, you want to find a path between two given cities. For this you'd probably use the BFS algorithm, for which your data structure is just fine. Note that BFS takes O(V+E) time where V and E are the vertex and edge count of the induced subgraph whose vertices' distance from the start vertex is not greater than the distance from start to end vertex. Which means in the worst case, it takes more time than traversing the list of cities.
这篇关于如何搜索中在C图结构特定节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
