0

设置（MySQL）：

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

这是我上一篇文章的 BFS 解决方案：

挑战，如何实现六度分离的算法？

但它的复杂性是什么？假设完全有n记录。

4

1 回答 1

2

假设有N个顶点和E条边。对于每个表，每对顶点之间都可以有一个连接，并且需要检查所有顶点是否相等。所以最坏情况下的性能将是 O(|V| + |E|)

更新：如果您正在考虑使用 Mysql，有很多事情会影响复杂性，如果您在字段上有主键索引，将使用 b-tree 索引。如果它是一个普通的非聚集索引，将使用散列索引。这些数据结构中的每一个都有不同的成本。

From your other question, I see this is your requirements 1. Calculate the path from UserX to UserY 2. For UserX,calculate all users that is no more than 3 steps away.

For the first one, best thing is to apply djikstra algorithm and construct a table in java and then update it in the table. Note that, adding every new node, needs complete processing.

Other solution to this will be to use recursive SQL introduced in SQL 1999 standard to create a view containing the path from UserX to UserY. Let me know if you need some references for recursive queries.

For the second one, the query you have written works perfectly.

于 2010-01-20T14:38:48.563 回答