How to search a specific node in a graph structure in C?

Question

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;

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.

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).

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...

Answer 1

You can use an algorithm called Breadth-First Search (BFS). You need to implement a "color" flag on each node to use it. Note that this algorithm only works if your edges are unweighted -- if 2 cities are connected, then they are of equal distance. If the edges have weight (which it does not look like they do), you need something like Dijkstra's Algorithm or A*.

Answer 2

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.

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.