Wie wird ein bestimmter Knoten in einer Graphenstruktur in C gesucht?

Question

Nicht, dass ich Zeit habe, dies richtig zu diskutieren, um zu einer Schlussfolgerung zu gelangen und meinen Code anzupassen, weil die Phase eins (von drei) eines Schulprojekts in 24 Stunden ist, aber zumindest muss ich wissen, ob ich die richtige Entscheidung getroffen habe.

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; 

Grundsätzlich habe ich viele Städte und die Städte sind alle miteinander verbunden sind, wie ein Diagramm. Zum Beispiel A, B, C, D und E werden sie in dieser Reihenfolge in die Struktur City eingefügt. Dann verbinde ich A mit B, C und D, B mit C, D, E, C mit D und E und D mit E.

Nun, sagen wir, ich muss in die Stadt E gehen. Dies ist die letzte eine in der verknüpften Liste und es braucht Zeit, um die verknüpfte Liste vollständig zu durchlaufen. Vielleicht nicht in diesem Beispiel mit 5 Städten, aber in der echten App soll ich mindestens 10.000 Städte unterstützen. Aber der kürzeste Weg ist von A (was der Startpunkt ist) von C nach E (oder es könnte A-D-E oder A-B-E sein, spielt keine Rolle).

Erlauben meine Strukturen mir, den kürzesten Weg von A nach E zu finden, ohne die gesamte verkettete Liste einzeln zu durchlaufen? Wenn nicht, was mache ich falsch?

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

Answer 1

Es gibt zwei separate Probleme - eines, Sie möchten wahrscheinlich einen City-Zeiger für eine Stadt ID finden (zB. "E"). Sie können das nicht in weniger als linearer Zeit mit Ihren Strukturen tun; Wenn Sie es schneller benötigen, verwenden Sie eine Hashtabelle oder einen binären Suchbaum.

Zweitens möchten Sie einen Pfad zwischen zwei bestimmten Städten finden. Dazu würden Sie wahrscheinlich den BFS-Algorithmus verwenden, für den Ihre Datenstruktur gut ist. Beachten Sie, dass BFS die Zeit O (V + E) annimmt, wobei V und E die Ecken- und Kantenanzahl des induzierten Untergraphen sind, dessen Abstand der Scheitelpunkte vom Startscheitel nicht größer ist als der Abstand vom Anfangs- zum Endscheitelpunkt. Das bedeutet im schlimmsten Fall, dass es mehr Zeit in Anspruch nimmt, als die Liste der Städte zu durchlaufen.

Answer 2

Sie können einen Algorithmus namens Breadth-First Search (BFS) verwenden. Sie müssen ein "color" -Flag auf jedem Knoten implementieren, um es zu verwenden. Beachten Sie, dass dieser Algorithmus nur funktioniert, wenn Ihre Kanten ungewichtet sind - wenn 2 Städte verbunden sind, dann sind sie gleich weit entfernt. Wenn die Kanten Gewicht haben (was nicht so aussieht), benötigen Sie etwas wie Dijkstra's Algorithm oder A*.