为何图结构需使用DFS或BFS算法？邻接表实现的疑问

你采用邻接表实现了图，但对图遍历的理解存在关键误区：你写的代码只是遍历了节点A的邻接链表，并没有真正遍历整个图的所有节点，也无法处理节点间的分支邻接关系。

你提到的示例代码：

struct Node* temp = A;
while(temp != NULL)
{
 //do something
 temp = temp->next;
}

这段代码的作用仅仅是顺着A的next指针遍历它的直接邻接节点，完全覆盖不了图的完整结构，比如以下两种场景：

• 多连通分量场景：如果图中存在和A不相连的节点（比如单独的节点B及其邻接节点），你的代码根本访问不到这部分节点。
• 带分支的连通图场景：假设A的邻接节点是C，C同时连接了D和E，那你的代码只会按链表顺序遍历A→C→D，完全不会处理C的另一个邻接节点E，也不会去遍历D的邻接节点（如果有的话）。

BFS（队列实现）和DFS（栈实现）的核心价值，就是系统地管理所有待访问的节点，确保图中每个节点都被访问到，同时处理每个节点的所有邻接关系：

• 遍历开始时，将起始节点加入队列/栈并标记为已访问；
• 每次取出队列/栈中的节点，遍历它的所有邻接节点，把未访问过的节点加入队列/栈并标记；
• 重复操作直到队列/栈为空，这样就能覆盖所有可达节点，哪怕是多连通分量的图，只需要依次对未访问的节点启动遍历即可。

简单来说，你的代码只处理了邻接表中的某一条链表，而图是由多条链表组成的网状结构，必须借助队列或栈来追踪待访问节点，才能完成完整的遍历。

内容的提问来源于stack exchange，提问作者zogac