グラフの発生率リスト実装

Question

グラフデータ構造の実装を検討しており、「発生率リスト」の表現を検討しています。ここに簡単な説明があります：

発生率リスト

したがって、グラフ内の各頂点には、インシデントであるエッジのリストが保存されます。

私のグラフが指示されたグラフであることを考えると、私はこの説明からいくつかの点であまり明確ではありません：

1. グラフ自体には、すべてのエッジのリストも保存されていますか？
2. 頂点は、発信エッジのみを保存しますか、それとも着信して発信しますか？
3. 両方の場合、それらは別々のリストにありますか？

私は他のグラフ表現（隣接リスト、隣接マトリックス、エッジリスト、発生率マトリックス）に非常に精通しているので、これは一般的なグラフの実装に関する質問ではありません。

どんなポインターも大歓迎です。

Answer 1

それについてさらに調査し、考えてみたところ、私は発生率のグラフデータ構造がないという結論に達しました。ウィキペディアの記事は、著者の心の混乱の産物だったと思います。この質問を読んで、それに時間を費やしてくれたすべての人に感謝します。

アルマンド

Answer 2

私はおそらく死者から古い質問を提起していることを知っていますが、コメントするのが適切だと感じました。

発生率リストグラフ構造を作成することもできます。また、gigraphのために調整することもできます。

aを検討してください LinkedList<Vertex> オブジェクトとa LinkedList<Edge> 物体。これにより、すべてのエッジとすべての頂点を繰り返すことができますが、すべてがどのように接続されているかについての情報は含まれていません。

それから、いくつか追加するとします LinkedList<Connection> オブジェクト。実際、それぞれに1つ Vertex. 。 a Connection 単にどこです Edge そしてa Vertex 会う。したがって、 Edge 2つあります Connection オブジェクト（無向グラフ用）、および Vertex 1つあります LinkedList<Connection> すべてへの接続を表すオブジェクト Edge それはそれに接続されています。これは、本質的に、発生率リストです。

これらのいくつかを削除すると、これを変更するためにディグラフを表すことができます Connection オブジェクト。より具体的には、これらの参照を持たない場所を選択する必要があります。削除することを選択できます Connection関連するものから LinkedList<Connection> あなたが見たくないなら Edge から Vertex （上記の例では、N2には空があります LinkedList<Connection>）。代わりに、参照をオプションにすることを選択できます Edge（上記の例では、E1には1つあります Connection N2と1を指す Connection null、E1からN2へのトラバーサルを許可しますが、N1に戻ることはできません。これを実装する方法の選択は完全にあなた次第です。 1つはより直感的です - エッジが指示されるため、エッジの接続を削除して、どの方向に進むかを指示します。もう1つは最初はもう少し複雑に見えるかもしれませんが、最初の幅および深さの最初の検索を行うときにどこにもつながるエッジに不必要にホッピングするのを止めます。

ポイントフォーム：

1. 発生率リストの実装には、持っています。あなたはあなたの実装のためにする必要がありますか？

2. 厳密に言えば、発信エッジのみを保存することで得ることができます。ただし、バックトラッキングアルゴリズムは、旅行した参照に沿ってバックトラックできることから利益を得ることができます。もちろん、これを中心に何らかの歴史を実装することができるので、おそらくそれほど考慮事項ではありません。

3. 両方を行う場合、おそらく、それが受信または発信であるかどうかを区別する何らかの方法が必要です。それが2つあるかどうか LinkedList<Connection> 頂点上のオブジェクト、またはaを持つことによって boolean pointingToVertex 原始 Connection, 、または何でも。多分あなた Edge 指示され、無向エッジが作られます 2 反対の方法を指すエッジ。構造のニーズに応じて行われる考慮事項。

Answer 3

私は次の方法で発生率リストを実装しましたが、の問題は見つかりませんでした 無向グラフ. 。いくつかのグラフトポロジーアルゴリズムも実装しました。

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

セットのマップを使用して、頂点の検索と償却o（1）の複雑さのためにO（1）を保証します。頂点の隣接するリストの代わりにエッジの発生リストを保持することは、エッジ自体の特定の情報を運ぶ方法にすぎません。これは、たとえば重量をエッジに関連付ける場合の抽象アルゴリズムにも役立ちます。

編集：

更新しました 話し合い ウィキペディアでは、「発生率」トピックについて。