Comment rechercher un nœud spécifique dans une structure graphique en C?

Question

Non que j'ai le temps de discuter correctement pour arriver à une conclusion et d'adapter mon code parce que la première phase (trois) d'un projet d'école est en 24 heures, mais au moins je dois savoir si je l'ai fait la bonne décision.

Je suis en utilisant des listes chaînées et voici ma 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;

En fait, j'ai beaucoup de villes et ces villes sont reliées tous ensemble, comme un graphique. Par exemple, A, B, C, D et E ils sont insérés dans cet ordre dans la structure Ville . Ensuite, je relie A à B, C et D, B à C, D, E, C et D et E et D à E.

Maintenant, disons que je dois aller à la ville E. Ceci est le dernier dans la liste, et il faut du temps pour parcourir la liste chaînée tout le chemin. Peut-être pas sur cet exemple avec 5 villes mais dans la vraie application que je suis censé soutenir comme 10.000 villes au moins. Mais le plus court chemin de A (qui est le point de départ) à partir de C à E (ou il pourrait être A-D-E ou A-B-E, n'a pas d'importance).

Est-ce que mes structures me permettent de trouver la route la plus courte de A à E sans traverser toute la liste chaînée un par un? Sinon, ce que je fais mal?

Si oui, comment puis-je faire? Je n'ai pas la moindre idée comment puis-je trouver un chemin ...

Answer 1

Il y a deux questions distinctes - l'une, vous voudrez probablement trouver un pointeur City pour un ID de ville (par exemple « E ».). Vous ne pouvez pas le faire en moins de temps linéaire avec vos structures; si vous en avez besoin plus rapidement, utilisez un arbre de recherche Hashtable ou binaire.

Deux, vous voulez trouver un chemin entre deux villes données. Pour cela, vous auriez probablement utiliser l'algorithme BFS, pour lequel votre structure de données est très bien. Notez que BFS prend O (V + E) temps où V et E sont le sommet et le comptage de bord du sous-graphe induit dont la distance de sommets à partir du sommet de départ ne soit pas supérieure à la distance du début à la fin de sommet. Ce qui signifie que dans le pire des cas, il faut plus de temps que parcourir la liste des villes.

Answer 2

Vous pouvez utiliser un algorithme appelé en largeur de recherche (BFS). Vous devez mettre en œuvre un drapeau « couleur » sur chaque nœud à l'utiliser. Notez que cet algorithme ne fonctionne que si vos bords sont non pondéré - si 2 villes sont connectées, ils sont de distance égale. Si les bords ont un poids (ce qui ne semble pas comme ils le font), vous avez besoin quelque chose comme algorithme de Dijkstra ou A * .