私はこれまで聞いたことがありませんか、それとも他の言葉で聞いたことがありますか？コンテキストは、隣接リストの場合、 u
に隣接するすべての頂点をリストする時間はです。 同様に、（u、v）∈Eであるかどうかを判断する時間。隣接リストの実装が配列である場合、配列内でu を見つけるのは一定の時間であると思います。隣接するすべての頂点がuに リンクされている場合、すべての頂点を一覧表示または検索するには時間がかかると思います。ここで、nは隣接する頂点の数です。 それは本質的にどういう意味ですか？Θ(deg(u))
O(deg(u))

O(n)
Θ(deg(u))

json オブジェクトを使用して隣接リストを作成したいと考えています。隣接リストのjsonオブジェクトを次の形式で実装したいと思います。

私の疑問は、次のように動的に座標リストに値を追加できるかどうかJSONobj.node3[0]={x4,y4}です。または、オブジェクト宣言の外から JSONobj に値を追加するより良い方法はありますか?

いくつかのフィールドを含む2つの構造体があります：structMyNodeDataとstructMyEdgeDataです。VertexListをvecSとしてグラフを作成する場合、頂点などの記述子にアクセスするのに問題はありません。次に例を示します。

しかし、私は通常、グラフからエッジと頂点を追加/削除する必要があります。したがって、vecSでは、vecSの代わりにsetSまたはlistSをVertexListとして使用したいと思います。これは、vecSでは、インデックスの1つを削除すると、インデックスが無効になるためです。問題は、VertexListをsetSまたはlistSとして定義すると、以前のように頂点/エッジのリストを参照してそこの記述子にアクセスできないことです。

簡単に言うと、私の質問は次のとおりです。頂点コンテナとしてlistSまたはsetSを使用するadjacency_listは、このvertex_idプロパティを自動的に提供しないので、上記のコードに追加するにはどうすればよいですか？

これは、隣接リストのSO 投稿です。ただし、単一リンクリストとの違いはありませんか? また、これはウィキペディアの記事で、パスグラフではないグラフがある場合、リスト内のすべてのエッジ (グラフ、離散数学タイプ) であると述べています。隣接リストをコーディングするにはどうすればよいですか?

現在、隣接リストとして保存されている単純な3レベルのツリーがあります。

これは読み取り専用であり、特定のカテゴリのルートカテゴリを知る必要があることがよくあります。したがって、root_id列を追加して永続化し、面倒なWHERE句やCTEなどを回避したいと思います。

私の最初の試みは：

ただし、複数の行を生成するUPDATE結合を処理することはできません。（このクエリはレベル2のカテゴリのみを対象としていました。私は、第3レベルでも同様のクエリを実行します。）

答えは結合をサブクエリに変えることですが、自己結合とサブクエリを一度に考えることはできません。私たちはPostgreSQL9.0を使用しているので、書き込み可能なCTEはありません（ただし、これがどのように見えるか知りたいです）。

これを行う正しい方法は何ですか？

基本的な隣接リストを考えてみましょう。idプロパティ、parent_id、およびを持つ Node クラスによって表されるノードのリストname。最上位ノードのparent_id = None。

リストを順序付けされていない html メニュー ツリーに変換する Pythonic の方法は次のとおりです。

• ノード名
• ノード名
  • サブノード名
  • サブノード名

しばらくの間、私は SQL で階層を処理する最善の方法と格闘してきました。隣接リストの制限と MPTT/ネストされたセットの複雑さに不満を感じた私は、単純なnode_key/node_key/...文字列として代わりにキー パスを単純に保存することを考え始めました。3 つの手法の長所と短所をまとめることにしました。

ノードの作成/削除/移動に必要な呼び出しの数:

• 隣接性 = 1
• MPTT = 3
• パス = 1 (そのパスを含むすべてのノードで、古いノード パスを新しいノード パスに置き換えます)

ツリーを取得するために必要な呼び出しの数:

• 隣接性 = [サブレベルの数]
• MPTT = 1
• パス = 1

ノード/祖先へのパスを取得するために必要な呼び出しの数:

• 隣接性 = [スーパーレベルの数]
• MPTT = 1
• パス = 0

サブノードの数を取得するために必要な呼び出しの数:

• 隣接性 = [サブレベルの数]
• MPTT = 0 (左右の値から算出可能)
• パス = 1

ノードの深さを取得するために必要な呼び出しの数:

• 隣接性 = [スーパーレベルの数]
• MPTT = 1
• パス = 0

必須の DB フィールド:

• 隣接性 = 1 (親)
• MPTT = 3 (親、右、左)
• パス = 1 (パス)

結論

ストアド パス手法は、1 つを除くすべてのユース ケースで、他の手法と同じか、または少ない呼び出しを使用します。この分析によると、パスの保存は明らかに勝者です。言うまでもなく、実装がはるかに簡単で、人間が読めるなどです.

問題は、保存されたパスは MPTT よりも強力な手法と見なされるべきではないということです。保存されたパスがより一般的に使用される手法ではないのはなぜですか? また、特定のインスタンスで MPTT を介して保存されたパスを使用しないのはなぜですか?

また、この分析が不完全だと思われる場合は、お知らせください。

アップデート：

保存されたパス ソリューションではできなくても、MPTT ですぐに実行できることが少なくとも 2 つあります。

1. 追加のクエリなしで、各ノードのサブノード数を計算できます (上記)。
2. 特定のレベルでノードに順序を課します。他のソリューションは順不同です。

隣接するリストを正しい順序で作成するのに問題があります。CreateAdjList(void)メソッドに問題があると思います。アイデアが尽きた。ヒントを教えてください。基本的に、接続されたエッジにグラフと隣接リストを作成しています。

実際のプログラム出力 - 間違った順序。出力リストを印刷して添付しました。

入力：

私の実際の出力は間違った順序で表示されます。ノードを見ると、正しい順序は 2 ->3->6->5 のはずです

隣接リストを使用してグラフを表現しようとしていますが、ポインターに問題があります。

私が構築しようとしているものは、実際には単純です。1 --> 1,2 . しかし、私が書いたコードは機能しませんでした。何が問題なのですか？

編集済み: OK、NULL を修正しました。予想される出力は 1 -->> 1,2 です。2 つのノード 1 を持つグラフは、それ自体と値 2 を持つ次のノードを指します。私の問題は、リスト 1 --> 1,2; を取得した後にグラフを作成するときです。3 つの異なるノードがあるようです。後でノードの値を 1 から 3 に変更すると、3 --> 1,2 が得られますが、ノードは 2 つしかないはずなので、その変更を行った後、目的の出力は 3 --> 3,2 になるはずです。