An algorithm about 6 degrees

xtfvvv

The table structure is as follows, just two fields

 user char (10) // user
 friend char (10) // friend (s) of this user


Data demo:
   user friend
--------------------
   alex tom
   alex john
   alex diana
   john simeno
   john cooker
   john coco
   wendy kk47
   wendy stephen

Take two users from the user column randomly, how to determine whether they can be contacted from friends, friends of friends, or friends of friends of friends?
   For example, alex can know coco through his friend john, but alex has no way to contact stephen. When the amount of data is relatively large, what algorithm should be used?

   This should be considered a connectivity problem for the graph?

fangaibi

Well, it's connectivity!
1. If you want to know if any two people can reach O (1) time, I only think of O (n ^ 3) algorithm. Passing closures can be, Freud can also, just a little Change it!
2. Of course, if you don't need to judge in O (1) time, you can divide the graph into several connected sets. This can consider the spanning tree method (the minimum spanning tree is not necessary), and dfs can also, depending on the situation The complexity of this creation is low
If the graph does not change much, it is mainly for query, or use 1, otherwise use 2

I can only think of these, expecting more efficient algorithms

ivor1982

And check the set, the search time is almost O (1)

xiaobaixi

I messed up ...


If only for querying O (1)
You can first build a matrix

Figure:
  A B C D E F
A
B
C
D
E
F

Then calculate their relationship
Then
Just check the matrix for the next query

guess12300

Just like it

lhc6847069

ivor1982positive solution
And check set.
Find time is O(1)

The input is O(n). Haha.