3

私は次の問題に取り組んでいます.2つの列を持つCSVファイルがあり、ファイル名は「友達」であると言えます。両方の列には、A から Z までの文字が含まれています。

A B
B C
A E
D F
E F

各行には 2 つの異なる文字があります (行に重複はありません)。AさんはBさんの友達、CさんはDさんの友達など…AさんがBさんと話し、BさんがCさんと話すと、BさんとCさんが知り合いになります。Aquintaces は、共通の友人を共有する人です。誰がより多くの分母を持っているかを調べる必要がありますか?

私は、ハッシュマップ、アレイリスト、スタックなどの異なるデータ構造を使用する方法と、グラフ理論 (JGraphT ライブラリ) を使用する方法の 2 つの異なる方法を試してきました。しかし、データ strcutres を使用するとロジックに固執し、グラフ理論を使用するとグラフ内のトラバーサルに固執します。

次の質問があります:-

  1. データ構造またはグラフを使用するためのより良いアプローチは何ですか? または、これよりも優れたアプローチ/ロジック/アルゴリズムはありますか?
  2. JgraphT Library でグラフをトラバースする方法を知っている人はいますか。私はこれを行うことができません。ライブラリに関するドキュメントは非常に限られています。

お願いします、どんな助けでも本当にありがたいです。

4

2 に答える 2

1

一般に、HashMapは最も高速で使いやすいものの1つです。一部のライブラリが必要なことやコーディングに時間がかかることを簡単に実行できることが確実な場合を除いて、カスタムライブラリではなくそれらを使用することをお勧めします。

あなたの場合は、各人をキーとして使用し、彼の友人のリストをオブジェクトが指すオブジェクトとして使用することができます。以前のコメントで指摘したように、.csvファイルを解析し、それに応じてHashMapに入力すると、問題が解決します。

于 2013-01-09T11:51:48.733 に答える
0

最初に、すべての文字をその友人のセットにマップするハッシュ テーブルを作成できます。たとえば、A は { B } にマップされ、B は { C } にマップされます。Z に 2 つの友人 Y と W がいる場合、Z は { Y, W にマップされます。 }。これは、文字から文字セットへのハッシュ マップです。

知人を計算するには、ハッシュ マップを反復処理します。エントリ A -> { B, C, F } にいるときは、セット B、C、F を介して内部ループで反復します。友人 (3 つのセット) を 1 つのセットに収集します (要素を一時セットに挿入するだけです)。 ) A が見つかった場合は、そのセットから A を削除します。そのセットのサイズは、A の知り合いの数です。すすぎと繰り返し。

于 2012-05-12T05:30:07.840 に答える