c - 如果图不是邻接矩阵的形式，如何找到节点的所有邻居？

Question

我曾尝试用 C 语言搜索 BFS 实现，但它们似乎都期待邻接矩阵形式的图形，据我了解，它能够立即找出所有相邻节点。

1. 但是如果输入是一对节点的形式，我应该怎么做才能找出相邻节点？
2. 我是否应该在每次寻找邻居时存储边缘并循环遍历它们？但这听起来很慢，就像我这样的傻瓜会做的事:( .
3. 或者我是否应该以某种方式将输入转换为邻接矩阵？

输入示例

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

伪代码

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

I have tried to google BFS implementations in C but all of them seem to be expecting graph in form of adjacency matrix, and from what I have understood it enables to find out all adjacent nodes in no time.

嗯，不。邻接矩阵允许您在与节点数无关的非零时间内找到相邻节点的集。但是仍然需要与节点数成正比的时间来确定该集合的所有元素是什么。其他表示，例如邻接列表，可以允许在相同的常数时间内找到集合，并及时找到与其数量成正比的元素(这可能比节点总数少得多) .

1. But what am I supposed to do to find out adjacent nodes if the input is in form of pair of nodes?

如何构建邻接矩阵或邻接列表或替代表示，然后使用它？

2. Am i supposed to store the edges and loop through them each time I am looking for neighbours? But that sounds slow and like something dummy like me would do :( .

平面的边列表是一种可能的表示。有一些方法可以使这样的列表更有效地使用(例如，通过对其进行排序和/或对其进行索引)，但这是否真的成功取决于问题。

3. Or am I somehow supposed to convert the input to adjacency matrix?

如果您确实想创建一个邻接矩阵，那么首先创建一个表示所有节点且没有边的矩阵。阅读边列表，并为其中的每条边填写适当的条目，或者如果图是无向的，则填写适当的两个条目。