4

グラフと隣接行列に混乱しています。ノードのテキスト ファイルとエッジのテキスト ファイルがあるクラスの割り当てを行っています。それぞれを読み取り、グラフを作成して、グラフが接続、最小スパニング ツリーの検索、トラバーサル、およびパスの検索。私はこれまでグラフを扱ったことはありませんでしたが、全体に本当に混乱しており、誰かがこれについて説明するのを手伝ってくれるかどうか疑問に思っていました.

まず、グラフを独自に作成し (おそらくノードとエッジのクラスを使用して)、それから隣接行列を作成しますか? それとも隣接行列自体がグラフですか？

そして、隣接する行列をプログラムに実装する方法について混乱しています。ノードは「ND5」や「NR7」などの名前であるため、[ND5][NR7] のエッジを設定して読み取る必要がありますが、そのような文字列を使用して 2D 配列を設定する方法がわかりません外側と内側に数字。

私はインターネット全体を検索し、教科書のグラフに関する章全体を読んでいますが、このグラフを設定するための最初の基本的な手順だけを本当に理解していません. 助けていただければ幸いです。ありがとう。

4

1 に答える 1

15

まず、グラフを独自に作成し (おそらくノードとエッジのクラスを使用して)、それから隣接行列を作成しますか? それとも隣接行列自体がグラフですか？

課題の指示を実際に読まずに、誰もその質問に確実に答えることはできません。ただし、割り当てNodeでEdgeクラスまたは何かが具体的に言及されていない限り、グラフを表すために隣接行列を使用することになっていると思います。

そして、隣接する行列をプログラムに実装する方法について混乱しています。ノードは「ND5」や「NR7」などの名前であるため、エッジを設定して読み取る[ND5][NR7]必要がありますが、外側に文字列、内側に数字を使用してそのような2次元配列を設定する方法がわかりません.

ここであなたの混乱を完全に理解できます。実際にやりたいことは、ノード名とマトリックスのインデックスの間に全単射(1 対 1 の関係) を作成することです。たとえば、グラフにn 個のノードがある場合、 n×n行列 (つまり) が必要であり、各ノードは 0 からn (n を含まない)new boolean[n][n]までの範囲の単一の整数に対応します。

これまでにクラスでどのようなデータ構造を扱ってきたかはわかりませんが、これを行う最も簡単な方法はおそらく を使用するMap<String, Integer>ことです。"ND5".

もう 1 つの良い方法は、配列を使用することです。すべてのノード名を配列に入れ、 でソートし、ソートしたら、その配列内の特定のノード名のインデックスを見つけるためにArrays.sort使用できます。このソリューションは、両方の方法でルックアップを実行できるためArrays.binarySearch、実際には a を使用するよりも優れていると思います。Map以前Arrays.binarySearchは名前からインデックスへのルックアップを行っていましたが、配列にインデックスを付けてインデックスから名前へのルックアップを行うだけです。

例: 次のグラフがあるとします。

AB、AD、BD、CD

そのグラフを考えると、これを行う方法のサンプルコードを次に示します: (警告! テストされていません)

import java.util.Arrays;

// Add all your node names to an array
String[] nameLookup = new String[4];
nameLookup[0] = "A";
nameLookup[1] = "B";
nameLookup[2] = "C";
nameLookup[3] = "D";

// Our array is already properly sorted,
// but yours might not be, so you should sort it.
// (if it's not sorted then binarySearch won't work)
Arrays.sort(nameLookup);

// I'm assuming your edges are unweighted, so I use boolean.
// If you have weighted edges you should use int or double.
// true => connected, false => not connected
// (entries in boolean arrays default to false)
boolean[][] matrix = new boolean[4];
for (int i=0; i<matrix.length; i++) matrix[i] = new boolean[4];

// I don't want to call Arrays.binarySearch every time I want an index,
// so I'm going to cache the indices here in some named variables.
int nodeA = Arrays.binarySearch(nameLookup, "A");
int nodeB = Arrays.binarySearch(nameLookup, "B");
int nodeC = Arrays.binarySearch(nameLookup, "C");
int nodeD = Arrays.binarySearch(nameLookup, "D");

// I'm assuming your edges are undirected.
// If the edges are directed then the entries needn't be semmetric.
// A is connected to B
matrix[nodeA][nodeB] = true;
matrix[nodeB][nodeA] = true;
// A is connected to D
matrix[nodeA][nodeD] = true;
matrix[nodeD][nodeA] = true;
// B is connected to D
matrix[nodeB][nodeD] = true;
matrix[nodeD][nodeB] = true;
// C is connected to D
matrix[nodeC][nodeD] = true;
matrix[nodeD][nodeC] = true;

// Check if node X is connected to node Y
int nodeX = Arrays.binarySearch(nameLookup, stringNameOfX);
int nodeY = Arrays.binarySearch(nameLookup, stringNameOfY);

if (matrix[nodeX][nodeY]) { /* They're connected */ }

// Print all of node Z's neighbors' names
int nodeZ = Arrays.binarySearch(nameLookup, stringNameOfZ);
for (int i=0; i<matrix.length; i++) {
  if (matrix[nodeZ][i]) {
    System.out.println(nameLookup[nodeZ] + " is connected to " + nameLookup[i]);
  }
}
于 2013-11-16T22:05:14.277 に答える