1

私はこの質問をさまざまな方法で行ってきました。

隣接リストがある場合、順序は重要ですか？隣接リスト{1、2、5}が{2、1、5}と同等であるとしましょう。または、順序は何かを意味するので、これら2つのリストは同等ではありませんか？

グラフが方向付けられており、順序が隣接するノードの配置と時計回りに関係していることを示している場合にのみ問題になるなど、いくつかの回答を受け取りました。私はまた、それは問題ではないという意見を与えられましたが、彼はインターネットの注文方法（ページランク付けアルゴリズム）などの重み（使用されている場合）に関して注文することを望んでいます。私は要点を伝えたと思いますが、これらの応答のいずれかを正確に言い換えるとは思いません。どんな考えでもありがたいです。

また、私は質問を洗練して、答えられた場合、私が求めている正確な答えを私に与えると思います：

有向グラフの隣接行列があるとします。

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

同等の隣接リストは次のとおりであると言われ、私の先生は、特に最後のリストに見られるように、任意の並べ替えではなく、意図的にこのようにリストしたと思います。

{2}

{2、3}

{0、1、3}

{2、1}

最後のリストは{2、1}です！同等の隣接行列で、{1、2}ではなく{1、1}である必要があることを警告するものは何ですか？

4

2 に答える 2

2

通常、いいえ、隣接リストの順序は重要ではありません。

...明示的に述べられていない限り。

実装では、さまざまな理由でリストが実際に順序付けられる場合があります。グラフの作成方法の結果として、または頂点の隣接ノードをある順序で処理するためです。しかし、概念的には、順序は重要ではありません。

私はあなたの場合の答えはノーであると信じています{2,1}、と同じ{1,2}です。おそらくあなたの先生は最初にそれを間違って書き（のように{2,3}）、それを修正した後に順序を変更しませんでした。または彼/彼女はあなたに順序が重要であるかどうか考えに行くことを望みました。あなたが先生に尋ねない限り、確かにわかりません。

于 2012-07-12T12:56:46.657 に答える
0

隣接リスト内のノードの値はセットです。セットは順序付けられていません。したがって、{1,2}は{2,1}と同じです。

于 2020-11-27T05:29:33.053 に答える