Wie man einen bestimmten Knoten in einem Graphen-Struktur in C suchen?

Question

Nicht, dass ich Zeit, dies zu diskutieren, richtig zu einem Abschluss zu erreichen und meinen Code anzupassen, da die Phase eins (von drei) eines Schulprojektes in 24 Stunden ist, aber zumindest ich muss wissen, ob ich die richtige Entscheidung war.

Ich bin verkettete Listen mit und hier ist meine Strukturen:

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;

Im Grunde genommen, ich habe viele Städte und die Städte sind alle miteinander verbunden sind, wie ein Diagramm. Zum Beispiel, A, B, C, D und E sie in dieser Reihenfolge in die Struktur eingefügt werden City . Dann habe ich eine Verbindung von A nach B, C und D, B zu C, D, E, C bis D und E und D bis E.

Nun lassen Sie uns sagen, dass ich nach Stadt E. gehen müssen Dies ist die letzte in der verknüpften Liste und es braucht Zeit, um die verknüpften Liste den ganzen Weg zu durchqueren. Vielleicht nicht in diesem Beispiel mit 5 Städten, sondern in der realen App soll ich wenigstens wie 10.000 Städte unterstützen. Aber der kürzeste Weg von A (das ist der Ausgangspunkt ist) von C bis E (oder es könnte A-D-E oder A-B-E sein, spielt keine Rolle).

Haben meine Strukturen erlauben Sie mir den kürzesten Weg von A bis E zu finden, ohne die ganze Liste eins nach dem anderen verknüpft durchqueren? Wenn nicht, was ich falsch mache?

Wenn ja, wie kann ich das tun? Ich habe keine Ahnung, wie kann ich einen solchen Weg finden ...

Answer 1

Es gibt zwei getrennte Fragen - ein, haben Sie wahrscheinlich eine Stadt Zeiger für eine Stadt ID finden möchten (zB „E“.). Sie können das nicht in weniger als lineare Zeit mit Ihren Strukturen; wenn Sie sie schneller benötigen, verwenden Sie einen Hash-Tabelle oder binären Suchbaum.

Zwei, möchten Sie einen Weg zwischen zwei bestimmten Städten zu finden. Dazu würden Sie wahrscheinlich den BFS-Algorithmus verwenden, für die Ihre Datenstruktur nur in Ordnung ist. Beachten Sie, dass BFS O (V + E) Zeit in Anspruch nimmt, wobei V und E ist der Scheitelpunkt und Kantenzählung des Untergraphen, deren Eckpunkt Distanz vom Anfangspunkt nicht größer ist als der Abstand vom Anfang bis zum Endknoten. Was im schlimmsten Fall bedeutet es mehr Zeit in Anspruch nimmt als die Liste der Städte durchqueren.

Answer 2

Sie können einen Algorithmus verwenden namens Breitensuche (BFS). Sie müssen eine „Farbe“ Flagge auf jedem Knoten implementieren, es zu benutzen. Beachten Sie, dass dieser Algorithmus funktioniert nur, wenn Ihre Ränder sind ungewichteten - wenn 2 Städten verbunden sind, dann sind sie gleich weit entfernt. Wenn die Kanten Gewicht haben (was sie nicht aussehen wie sie es tun), müssen Sie so etwas wie Dijkstra-Algorithmus oder A * .