Как выполнить поиск по определенному узлу в структуре графа на C?

Question

Не то чтобы у меня было время обсудить это должным образом, чтобы прийти к выводу и адаптировать свой код, потому что первая фаза (из трех) школьного проекта начинается через 24 часа, но, по крайней мере, мне нужно знать, принял ли я правильное решение.

Я использую связанные списки, и вот мои структуры:

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 они вставляются в структуру в таком порядке Город.Затем я соединяю A с B, C и D, B с C, D, E, C с D и E, а D с E.

Теперь, допустим, мне нужно съездить в город E.Это последний в связанном списке, и требуется время, чтобы пройти весь связанный список до конца.Может быть, не в этом примере с 5 городами, но в реальном приложении я должен поддерживать как минимум 10 000 городов.Но самый короткий маршрут - от A (который является отправной точкой) из C в E (или это может быть A-D-E или A-B-E, не имеет значения).

Позволяют ли мои структуры мне найти кратчайший маршрут от A до E, не проходя весь связанный список один за другим?Если нет, то что я делаю не так?

Если да, то как я могу это сделать?Я понятия не имею, как я могу найти такой путь...

Answer 1

Есть две отдельные проблемы - во-первых, вы, вероятно, хотите найти указатель города для идентификатора города (например."E").Вы не можете сделать это менее чем за линейное время с вашими структурами;если вам это нужно быстрее, используйте хэш-таблицу или бинарное дерево поиска.

Во-вторых, вы хотите найти путь между двумя заданными городами.Для этого вы, вероятно, использовали бы алгоритм BFS, для которого ваша структура данных просто великолепна.Обратите внимание, что BFS занимает O (V + E) времени, где V и E - количество вершин и ребер индуцированного подграфа, расстояние вершин которого от начальной вершины не больше расстояния от начальной до конечной вершины.Это означает, что в худшем случае это займет больше времени, чем просмотр списка городов.

Answer 2

Вы можете использовать алгоритм, называемый Поиск по ширине в первую очередь (BFS).Вам нужно внедрить флаг "color" на каждом узле, чтобы использовать его.Обратите внимание, что этот алгоритм работает только в том случае, если ваши ребра невзвешенный -- если 2 города соединены, то они находятся на равном расстоянии.Если ребра имеют вес (на который, похоже, они не похожи), вам нужно что-то вроде Алгоритм Дейкстры или A*.