問題タブ [adjacency-list]

予想される出力は、値 1 を持つノードであり、隣接リストにそれ自体があり、1 -> 1 のような出力です。

ここで私の問題は、2 つの異なるノードがあるように見えることです。それらの1つを変更しても、もう1つは変更されず、別のノードのように機能します。

たとえば、リストを作成した後、ノードの値を変更すると、3 -> 3 のような出力が得られます。しかし、3 -> 1 になります。ノードの変更は、他のノードには影響しません。adj[0] を t->next に向けようとすると、無限ループが発生します...

隣接リストを使用して無向グラフを表すための一般的なサンプル コードを入手できる場所を知っている人はいますか?

グラフ データは .txt ファイルから取得されます。ノードは最初の行で指定され、スペースで区切られます。エッジは次の行で指定され、各エッジは別の行にあります。

このような...

.txt ファイルがグラフ メソッドに接続されていません。次の NPE エラーも表示されます。

隣接リストを作成し、無向グラフの標準的な Graph ADT メソッドを実行します。

まず、構造が正しいことを確認したいと思います。私の知る限り、グラフを表す隣接リストは次のようになります。

AdjList は、各要素がオブジェクトである ArrayList です。各オブジェクトには、接続された頂点を表す ArrayList が内部に含まれています。たとえば、上の画像では、頂点 1 (AdjList の最初のインデックス) が AdjList のインデックス 2、4、および 5 の頂点に接続されています。隣接リストのこの表現は正しいですか? (ps: インデックスが 0 から始まることはわかっています。簡単にするためにここに 1 を入れます)。

正しい場合、2 つの頂点間の最短経路を見つけるにはどのアルゴリズムを使用すればよいですか?

次の3つの方法を手伝ってくれる人はいますか？

addVertex: 単一の頂点を追加します

removeEdge: 2 つの頂点間のエッジを削除します。

removeVertex: 単一の頂点を削除します

隣接リストを使用して無向グラフを表現します。データは .txt ファイルにあります (以下の例)。

1 2 3 4 5 6 7 8 9

1 2

1 4

1 3

2 4

2 5

3 6

4 6

5 7

5 8

6 9

7 9

8 9

コード：

BFS が O(m+n) である方法を理解しようとしています。ここで、n は頂点の数、m はエッジの数です。

アルゴリズムは次のとおりです。

隣接リストでは、頂点を配列/ハッシュ テーブルに格納し、各頂点が他の頂点と形成するエッジのリンク リストを格納します。

私の主な質問はこれです: get unvisited child node をどのように実装しますか? ノードを訪問済みとしてマークすることは明らかですが、トラバースするときに、リンクされたすべてのリストを通過するため、すべてのエッジを 2 回カウントするため、複雑さは O(2m+n) ですよね? それはO（m + n）に切り捨てられますか？

また、隣接行列に同様の戦略を採用できますか? サイズ nxn の行列が与えられ、特定の要素が存在するかどうかを知りたい場合、それを把握するために BFS を実行できますか?

ありがとう。

潜在的なクラスターまたはノードのグループ（この場合はフォーラムメッセージ）を見つけようとしています。

現在のデータでは、各ノード（メッセージ）は他のn個のメッセージと一緒に暫定的にグループ化されており、そのグループに名前が付けられています。つまり、msgID1がmsgID3、および7と一緒に表示されていることがわかります。

私は現在、その情報を使用してエッジリストを作成し（グループ化されている場合はエッジが存在します）、ウォークトラップコミュニティを使用して樹状図を作成しています。

エッジリストを前提として、グループまたはクラスターを引き出す他の方法はありますか？（私はRを使用していますが、何かへのポインターが役立ちます）。

御時間ありがとうございます！

MySQLスキーマには、category(id, parentid, name)テーブルがあります

MSSQLには、そのCTEクエリがあります（指定されたカテゴリIDのカテゴリツリーを下から上に構築するため）。

そのクエリをMySQLに「変換」する方法は？

隣接リスト方式を使用して、MySQL データベースにツリーを保存します

ツリーをプレビューしたい場合、PHP はデータベースからツリー全体を取得し、再帰を使用してプレビューします。

しかし、反復は再帰よりもパフォーマンスが優れているため、パフォーマンスを向上させるために for ループを使用してツリーを作成したいと考えています。

MySQL の関数、メソッド、またはトリガーを使用したくありません。繰り返し (for ループ) を使用してツリーにデータを入力したいだけです。

CLRS物品税22.1-8で（私は独学であり、どの大学にも所属していません）

リンクされたリストの代わりに、各配列エントリ Adj[u] が (u,v) ∈ E である頂点 v を含むハッシュ テーブルであると仮定します。エッジはグラフにありますか? このスキームにはどのような欠点がありますか? これらの問題を解決する各エッジ リストの代替データ構造を提案します。ハッシュテーブルと比較して、代替案には欠点がありますか?

したがって、各リンク リストをハッシュ テーブルに置き換えると、次のような疑問が生じます。

1. エッジがグラフにあるかどうかを判断するのに予想される時間は?
2. 短所は何ですか？
3. これらの問題を解決する各エッジ リストの代替データ構造を提案する
4. ハッシュテーブルと比較して、代替案には欠点がありますか?

次の部分的な回答があります。

1. Hashtable t = Adj[u] を実行してから t.get(v); を返すだけなので、予想される時間は O(1) だと思います。
2. 欠点は、Hashtable がリンクされたリストよりも多くのスペースを取ることだと思います。

他の 2 つの質問については、手がかりが得られません。

誰でも私に手がかりを与えることができますか？

PHPを使用して、次のテーブルデータをネストされた配列に変換しようとしています。私はほぼ完了しましたが、ある時点で立ち往生しています。

このコードの使用

これにより、次の JSON が生成されます。

JSONが好きな場所