graph - 无向图邻接（计算机科学）

Question

我有一个无向图 G=(V,E)，节点标记为 1、2、3、...、n，以及 V 中的特定节点 k。

我有这个图的两种表示形式：Adjacency-Matrix和Adjacency-List

我将如何确定节点 k 是否与图中的所有其他节点相邻？这是我遇到的一个更大问题的一部分。

我不想要具体的伪代码或解决方案，只需要简单的英语，我将在数据结构中扫描什么以及我将如何确定这一点。（请尽量降低复杂度）

谢谢

Answer 1

使用 adj 矩阵，检查除-thk之外的所有组件中的行为 1 。k

使用 adj 列表（假设您没有多重图并且n是图顶点的数量），检查列表大小n-1，它应该是 O(1)。

最好的问候，卡斯滕

Answer 2

您可能只检查每个节点，如果其中任何一个不与 k 相邻，则返回 false。我认为您无法避免检查每个顶点，因此短路失败将是一个好主意。