无向图邻接（计算机科学）
我有一个无向图 G=(V,E)，其节点标记为 1, 2, 3,...,n，并且 V 中有一个特定节点 k。
我如何确定节点 k 是否与图中的所有其他节点相邻？这是我遇到的一个更大问题的一部分。
我不需要具体的伪代码或解决方案，只需要简单的英语，我将在数据结构中扫描什么以及如何确定这一点。 （请保持尽可能低的复杂性）
谢谢
I have an undirected graph G=(V,E) with nodes labelled 1, 2, 3,...,n, and a specific node k in V.
I have two representations of this graph: Adjacency-Matrix and Adjacency-List
How would I go about figuring out if node k is adjacent to all other nodes in the graph? This is part of a bigger problem that I have.
I don't want concrete pseudocode or solution, just in plain English what I would scan in the data structure and how I would determine this. (Please keep the complexity as low as possible)
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可能只检查每个节点，如果其中任何一个与 k 不相邻，则返回 false。我认为您无法避免检查每个顶点，因此进行短路失败将是一个好主意。
You could probably just check every node and return false if any of them is not adjacent to k. I don't think you can avoid checking every vertex so doing a short-circuit fail would be a good idea.
使用 adj 矩阵，检查除第 k 行之外的所有组件中的第 k 行是否为 1。
使用 adj 列表（假设您没有多重图，并且
n是图顶点的数量），检查列表大小n-1，它应该是 O(1) 。最好的问候，卡斯滕
using adj matrices, check row
kto be 1 in all components but thek-th.using adj lists (assuming you do not have a multigraph and
nis the number of graph vertices), check for list sizen-1, which should be O(1).best regards, carsten