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 ソリューションです。

チャレンジ、6次分離のアルゴリズムを実装する方法は?

しかし、それの複雑さは何ですか?完全にnレコードがあるとします。

4

1 に答える 1

2

N個の頂点とE個のエッジがあると仮定します。すべてのテーブルでは、頂点のすべてのペア間に結合が存在する可能性があり、すべての頂点が等しいかどうかをチェックする必要があります。したがって、最悪の場合のパフォーマンスは O(|V| + |E|) になります。

更新: Mysql を検討している場合、複雑さに影響するものがたくさんあります。フィールドに主キー インデックスがある場合、B ツリー インデックスが使用されます。通常の非クラスター化インデックスの場合、ハッシュ インデックスが使用されます。これらのデータ構造ごとに異なるコストがあります。

あなたの他の質問から、これがあなたの要件だと思います 1. UserX から UserY へのパスを計算します 2. UserX については、3 ステップ以内のすべてのユーザーを計算します。

最初のものについては、djikstra アルゴリズムを適用して Java でテーブルを作成し、それをテーブルで更新するのが最善の方法です。すべての新しいノードを追加するには、完全な処理が必要であることに注意してください。

これに対する他の解決策は、SQL 1999 標準で導入された再帰 SQL を使用して、UserX から UserY へのパスを含むビューを作成することです。再帰クエリの参照が必要な場合はお知らせください。

2 番目のクエリでは、作成したクエリが完全に機能します。

于 2010-01-20T14:38:48.563 に答える