Undirected Graph adjacency (Computer Science)

Question

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

Answer 1

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.

Answer 2

using adj matrices, check row k to be 1 in all components but the k-th.

using adj lists (assuming you do not have a multigraph and n is the number of graph vertices), check for list size n-1, which should be O(1).

best regards, carsten