Как найти всех соседей узла, если граф не в форме матрицы смежности?

Question

Я пытался гуглить реализации BFS в C, но все они, похоже, ожидают граф в виде матрицы смежности, и, насколько я понял, это позволяет быстро обнаружить все смежные узлы.

1. Но что я должен делать, чтобы узнать соседние узлы, если вход имеет форму пары узлов?
2. Должен ли я хранить края и перебирать их каждый раз, когда ищу соседей? Но это звучит медленно и похоже на то, что сделал бы я, как на меня :(.
3. Или я как-то должен преобразовать входные данные в матрицу смежности?

Пример ввода

{
    Nodes:
    0
    1
    2
    3
    Edges:
    0 2
    1 3
    2 3
    0 1
}

1016 *

Pseducode

BFS (G, s)   //Where G is the graph and s is the source node
      let Q be queue.
      Q.enqueue( s )
      mark s as visited.
      while ( Q is not empty)
           v  =  Q.dequeue( )

          for all neighbours w of v in Graph G  /* <---------------------------------------- HOW? */
               if w is not visited 
                        Q.enqueue( w )             
                        mark w as visited.

от https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/

Answer 1

Я пытался гуглить реализации BFS в C, но все они, похоже, ожидают граф в виде матрицы смежности, и из того, что я понял, это позволяет быстро обнаружить все смежные узлы.

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

1. Но что я должен делать, чтобы узнать соседние узлы, если вход имеет форму пары узлов?

Как насчет построения матрицы смежности, списка смежности или альтернативного представления, а затем его использования?

2. Должен ли я хранить края и проходить по ним каждый раз, когда ищу соседей? Но это звучит медленно и похоже на то, что сделал бы я, как на меня :(.

Плоский список ребер является одним из возможных представлений. Есть способы сделать такой список более эффективным для работы (например, отсортировав его и / или проиндексировав), но зависит ли это от победы, зависит от проблемы.

3. Или я как-то должен преобразовать входные данные в матрицу смежности?

Если вы действительно хотите создать матрицу смежности, начните с создания матрицы, представляющей все узлы без ребер. Прочитайте список ребер и заполните соответствующую запись для каждого ребра в нем, или две соответствующие записи, если график не ориентирован.