1

I have been tasked with an assignment where I have to check if a group of people have a "close friendship". This is defined as a group of people where all persons in the group are friends with all other persons in the group. So far I have this as my algorithm:

1) Initialize vertices as not visited

2) Do a DFS traversal of the graph starting from any arbitrary vertex v, marking visited vertices as visited

3) If the DFS traversal visits all vertices, return true

4) If it does not, return false.

Now I have to calculate the time complexity. However, I am having a hard time with time complexity in general, and I am not entirely sure how to do this. The way I see it is that I go through all the vertices in my set, which would be... O(v)? Is this correct? And if it is, what do I do from here?

Improve this question
1
  • 1
    Correct me if I am wrong, isn't it enough to just count edges? According to your definition, the group of n people is in close relationship if it forms a complete graph, and as such must have precisely n*(n-1)/2 distinct edges. Commented Apr 7, 2019 at 19:02

1 Answer 1

Reset to default
1

Since in DFS you visit all vertices only once, but you travel every edge to see whether that edge is taking you to a new vertex or to an already seen vertex, a very accurate measure of the complexity of DFS is O(#edges).

But O(#vertices) is generally an acceptable answer too to the complexity for DFS question, because when you see that an edge is not taking you to a new vertex, you don't explore it further.

So when asked, you can give either answer and explain the reasoning, because neither of them is wrong with supporting explanation.

But this may not be the answer to the actual question you are trying to solve. You are trying to find a closely connected group.

In graph terminology, a closely connected group of friends would be one where each friend node shares an edge with every other friend node. (Re-read your question - it actually literally says that.)

In the image below, majority of the graph is connected and other nodes are reachable from one node using DFTraversal. But close cohorts are the group of nodes with same color.

enter image description here

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

So the way I am doing it right now is not the correct way, if I want to check if everyone is connected to each other? Do you have an idea of what my algorithm would look like instead?
@Suicidalllama: You want to know whether the group is closely connected. For that you should count the total number of nodes in the graph and then for each node you should calculate the number of nodes each individual node is connected with. If the ratio of connections to total nodes is high (maybe a "friend factor" higher than 0.75) for all nodes, then that group can be considered close. Just a suggestion.
Perfect, thank you. I have an idea how to do it now. :-)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.