Как искать конкретный узел в структуре графа в C? - PullRequest
Новая
       60

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

0 голосов
/ 22 марта 2009

Не то, чтобы у меня было время обсудить это должным образом, чтобы прийти к выводу и адаптировать мой код, потому что первый этап (из трех) школьного проекта длится 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, не имеет значения).

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

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

Ответы [ 2 ]

1 голос
/ 22 марта 2009

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

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

1 голос
/ 22 марта 2009

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

...