4

I'm considering graph data structure implementations and am looking at the "incidence list" representation. There is a brief description of it here:

Incidence list

So each vertex in the graph stores a list of those edges upon which it is incident.

Given that my graph is a directed graph, I'm not very clear from this description on a couple of points:

  1. Does the graph itself also store a list of all edges?
  2. Do vertices only store outgoing edges, or incoming and outgoing?
  3. If both, are they in separate lists?

I'm quite familiar with the other graph representations (adjacency list, adjacency matrix, edge list, incidence matrix), so this isn't a question about graph implementations in general, just this particular one.

Any pointers would be much appreciated.

4

3 に答える 3

2

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

インシデンス リスト グラフ構造を作成したり、ダイグラフ用に微調整したりすることもできます。

LinkedList<Vertex>オブジェクトとオブジェクトを考えてみましょうLinkedList<Edge>。これにより、すべてのエッジとすべての頂点を反復処理できますが、すべてがどのように接続されているかについての情報は含まれていません。

次に、いくつかのLinkedList<Connection>オブジェクトを追加するとします。実際、各Vertex. AConnectionは単に anEdgeと a がVertex出会う場所です。したがって、Edgeには 2 つのConnectionオブジェクトがあり (無向グラフの場合)、Vertexには 1 つのLinkedList<Connection>オブジェクトがあり、接続されているすべてのものへの接続を表しますEdge。これは本質的に、発生リストです。

Connectionこれらのオブジェクトの一部を削除すると、これを変更して有向グラフを表すことができます。より具体的には、これらの参照を持たない場所を選択する必要があります。a からを表示したくない場合はConnection、関連付けられた からaを削除することを選択できます(上記の例では、N2 には空の があります)。代わりに、上で参照をオプションにすることを選択することもできます(上記の例では、E1 にはN2 を指すものと、N2 を指すものがあります)。LinkedList<Connection>EdgeVertexLinkedList<Connection>EdgeConnectionConnectionnull。E1 から N2 へのトラバーサルを許可しますが、N1 に戻ることはできません。これをどのように実装するかは、完全にあなた次第です。1 つはより直感的です。エッジは方向付けられているため、エッジの接続を削除して、エッジの方向を指示することは論理的に思えます。もう 1 つは、最初はもう少し複雑に見えるかもしれませんが、幅優先と深さ優先の検索を行うときに、どこにも通じないエッジに不必要に飛びつくのを防ぐことができます。

ポイント形式:

  1. 発生率リストの私の実装では、私は持っています。実装に必要ですか？

  2. 厳密に言えば、出力エッジのみを格納することで取得できます。ただし、バックトラッキング アルゴリズムは、移動した参照に沿ってバックトラックできることでメリットが得られる場合があります。もちろん、何らかの履歴を使用してこれを実装することはできるので、おそらくあまり考慮しません。

  3. 両方を行う場合、着信か発信かを区別する何らかの方法が必要になるでしょう。頂点に2 つのLinkedList<Connection>オブジェクトを配置するか、 にboolean pointingToVertexプリミティブを配置するConnectionか、またはその他の方法で行います。おそらく、あなたEdgeは有向であり、無向エッジは反対方向を指す2つのエッジで構成されます. 構造のニーズに応じて検討する必要があります。

于 2010-12-20T13:56:04.840 に答える
2

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

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

セットのマップを使用すると、頂点のルックアップに O(1) が保証され、エッジの挿入と削除に償却された O(1) の複雑さが保証されます。頂点の隣接リストの代わりにエッジのインシデンス リストを保持することは、エッジ自体の特定の情報を保持する方法にすぎません。これは、たとえば重みをエッジに関連付ける場合など、抽象的なアルゴリズムにも役立ちます。

編集：

「事件リスト」のトピックについて、ウィキペディアの講演を更新しました。

于 2011-01-08T14:11:18.917 に答える
0

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

アルマン

于 2010-10-12T11:53:20.770 に答える