2

グラフ内で相互接続されたN個のノードが与えられ、次に別のノードに接続されているノードをリストする行列が与えられた場合に問題が発生します（接続されている場合は1、そうでない場合は0）。この問題に最善の方法で取り組む方法を考えています。これらは隣接行列だと思いますか？しかし、どうすればそれを実装できますか...

基本的に私がこれらから抜け出そうとしているのは、特定のノードが特定のセット「S」内の他のすべてのノードに接続されているかどうかを見つけることです。そして、選択されたアイテムがクリークであるかどうか...

ヒントをいただければ幸いです。

4

6 に答える 6

7

これは、ブール値の 2 次元配列を使用して実装できます。したがって、ノード i がノード j に接続されている場合、myarray[i][j] は true になります。エッジに方向性がない場合、myarray[i][j] が常に true になります。

これは、配列の要素としてブール値の代わりに整数 (または別の数値型) を使用することにより、加重エッジに拡張することもできます。

于 2008-12-08T13:07:37.073 に答える
3

これを行う最も簡単な方法は、正方行列 (2 次元配列) を使用することです。これは、接続の有無を示すブール値か、トラバーサルのコストを表す整数のいずれかです。ただし、スパース グラフの場合は、ギザギザの配列を使用し、最初のノードに隣接するノードを保存することで、圧縮率を向上させることができます。List<List<Integer>>Java では、外側のリストが問題のノードに対応し、内側のリストがこのノードに隣接するすべてのノードになるようにすることで、おそらくこれを行うでしょう。

標準 (圧縮されていない) 行列を使用すると仮定すると、ノード i がリスト内のすべてのノード j に隣接しているかどうかを、リストを反復処理してから A[i][j] を検索することで確認できます。それらのいずれかが である場合false、それはリスト内のすべての項目に隣接していません。それ以外の場合は true です。クリークの場合、リスト内のすべてのアイテムに対してこれを行う必要があります (i=j のケースを削除し、無向グラフの最適化を行います)。

例 (ここでも Java)

public boolean isClique(boolean[][] A, List<Integer> nodes){
  for(int i : nodes){
    for(int j : nodes){
      if(i != j){
        if(!A[i][j]) return false;
      }
    }
  }
  return true;
}

最適化と Max-Clique 問題の解決策は、読者への演習として残されています。

于 2008-12-08T14:04:15.150 に答える
3

これを試して：

public class AdjacencyMatrix {

private String [] nodes;

private int [][] matrix;

public AdjacencyMatrix(String [] nodes,int [][] matrix){
    this.nodes = nodes;
    this.matrix = matrix;
}

boolean isSymmetric(){
    boolean sym = true;
     for(int i=0;i<matrix.length;i++){
         for(int j=i+1; j < matrix[0].length ; j++){
             if (matrix[i][j] != matrix[j][i]){
                 sym = false;
                 break;
             }
         }
     }
     return sym;
}

public Graph createGraph(){
    Graph graph = new Graph();
     Node[] NODES = new Node[nodes.length];

    for (int i=0; i<nodes.length; i++){
        NODES[i] =  new Node(nodes[i]);
        graph.addNode(NODES[i]);
    }

    for(int i=0;i<matrix.length;i++){            
         for(int j=i;j<matrix[0].length;j++){
             int distance = matrix[i][j];
             if (distance != 0){                     
                 graph.addEdge(new Edge(NODES[i], NODES[j], distance));
             } 
         }
    }

    return graph;
}


public long pathLength(int[] path){
    long sum = 0;
    for (int i=0; i<path.length - 1; i++){
        if (matrix[path[i]][path[i+1]] != 0)
            sum += matrix[path[i]][path[i+1]];
        else {
            sum = 0;
            break;
        }
    }

    return sum;
}


public static void main(String[] args){
    String[] nodes = {"A", "B", "C", "D", "E"};
    int [][] matrix= {  {0, 2, 2, 1, 0}, 
                        {2, 0, 1, 0, 0}, 
                        {2, 1, 0, 0, 1}, 
                        {1, 0, 0, 0, 4}, 
                        {0, 0, 1, 4, 7}};
    AdjacencyMatrix am = new AdjacencyMatrix(nodes, matrix);
    Graph graph  = am.createGraph();
    int[] a = {0, 2, 4, 4, 3, 0};
    int[] b = {0, 1, 2, 4, 4, 3, 0};
    graph.writeGraph(); 
    am.pathLength(a);
    am.pathLength(b);
}

}
于 2009-06-07T17:13:00.070 に答える
2

ヒント: M2 つのノードが直接接続されているかどうかを示す隣接行列があります。では、M^2 は何を与えるでしょうか? 2 つのノード間に長さ 2 のパスがあるかどうかがわかります。

M^3,... , M^inf (固定点に到達したとき)

于 2008-12-08T13:05:57.183 に答える
1

隣接行列を使用して、Floyd-Warshallアルゴリズムを適用すると、ノード間のすべてのパスが得られます。次に、特定のセットを確認できます。

于 2008-12-08T14:43:32.107 に答える
0

bool[][]の代わりにbitsetまたはbit_vectorを使用することをお勧めします。

ジャグ配列を使用せず、接続が対称である場合は、MIN（）およびMAX（）[マクロ]に基づくアクセサーでラップすることを検討してください。同じデータを2つの場所に保存することは、苦痛のレシピです。最終的に、array [i] [j]！= array[j][i]。

E.g: getValue( int i, int j ) { return array [ MIN(i,j) ] [ MAX(i,j) ] }
于 2008-12-08T19:28:18.053 に答える