邻接矩阵图实现

我想要实现使用邻接矩阵如下图：邻接矩阵图实现

被写入会发现所有其他商店从每家商店的距离最短的项目。这是正在使用的代码：

public class AdjacencyMatrix 
 
{  
 
    public static final int NUM_NODES = 100; 
 
    public static final int INF = 99999; 
 
    public static final int A = 20; 
 
    public static final int B = 18; 
 
    public static final int C = 47; 
 
    public static final int D = 44; 
 
    public static final int E = 53; 
 
    public static final int F = 67; 
 
    public static final int G = 95; 
 
    public static final int H = 93; 
 
    public static final int I = 88; 
 
    public static final int W = 66; 
 
    
 
    public static boolean even(int num) 
 
    { 
 
     return num%2==0; 
 
    } 
 

 
    public static boolean odd(int num) 
 
    { 
 
     return num%2==1; 
 
    } 
 

 
    public static void initialize(int [][] adjMat, int N) 
 
    { 
 
     for(int i = 0; i < N; i++) 
 
      for(int j = 0; j <N; j++) 
 
       adjMat[i][j]=INF; 
 

 
     for(int x = 0; x<N; x++) 
 
     { 
 
      int row = x/10; 
 
      int column = x%10; 
 

 
      if (even(row)) { 
 
       if (column!=9) 
 
        adjMat[x][x+1]=1; 
 
      } 
 
      if (odd(row)) { 
 
       if (column!=0) 
 
        adjMat[x][x-1]=1; 
 
      } 
 
      if (even(column)){ 
 
       if (row!=9) 
 
        adjMat[x][x+10]=1; 
 
      } 
 
      if (odd(column)) { 
 
       if (row!=0) 
 
        adjMat[x][x-10]=1; 
 
      } 
 
     } 
 
    } 
 
    
 
    public static int[][] floydWarshall(int[][] adjMat, int N) 
 
    { 
 
    \t adjMat = new int[N][N]; 
 
\t  initialize(adjMat, N); 
 

 
     for(int k = 0; k < N; ++k) 
 
     { 
 
      for(int i = 0; i < N; ++i) 
 
      { 
 
       for(int j = 0; j < N; ++j) 
 
       { 
 
       adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
 
       } 
 
      } 
 
     } 
 
     
 
     return adjMat; 
 
    } 
 
    
 
    public static int[][] arrayCondenser(int[][] adjMat, int N) 
 
    { 
 
    \t int[] array = {A,B,C,D,E,F,G,H,I,W}; 
 
    \t adjMat = floydWarshall(adjMat, N); 
 
    \t 
 
    \t 
 
    \t 
 
    \t 
 
    \t return adjMat; 
 
    } 
 

 
    public static void printGrid(int[][] adjMat) 
 
    { 
 
\t \t for (int i=0; i<NUM_NODES; ++i) 
 
\t \t { 
 
\t \t for (int j=0; j<NUM_NODES; ++j) 
 
\t \t { 
 
\t \t  if (adjMat[i][j]==INF) 
 
\t \t   System.out.printf("%5s", "INF"); 
 
\t \t  else 
 
\t \t   System.out.printf("%5d",adjMat[i][j]); 
 
\t \t } 
 
\t \t System.out.println(); 
 
\t \t } 
 
    } 
 
    
 
    public static void main(String[] args) 
 
    { 
 

 
     int adjMat[][] = new int[NUM_NODES][NUM_NODES]; 
 
     adjMat = floydWarshall(adjMat, NUM_NODES); 
 
    
 
     printGrid(adjMat); 
 
     
 
     int A,B,C,D,E,F,G,H,I,W; 
 
     
 
     
 

 
     System.out.println(); 
 
    } 
 
}

如何凝聚了100×100阵列下降到10×10，它包含了所有对最短路径只在图中突出显示的节点？

来源

2017-03-03 Nate

我没有看到在你的形式'adjMat的环的任何语句[X] [ x-1] = 1“，并且这些边缘存在于奇数行的图片中。 –

对于奇数行中的奇数列，应该有一个形式为'adjMat [x] [x-10] = 1'的语句，但只有偶数行中的奇数列发生这种情况。 –

另外，你需要在一个维度中有100个元素（索引0到99），而你只有99个。 –

我修改你的Floyd-Warshall实现为邻接矩阵的对角线元素正确初始化adjMat，它应该有一个值0.我也改变了floydWarshall方法不重新分配adjMat，该方法已在main方法中分配。我还在您的arrayCondenser方法中删除了floydWarshall的重复呼叫。我还修改了的arrayCondenser法计算密集阵列，并且加入了printCondensedGrid方法来显示密集阵列：

public class AdjacencyMatrix { 
    public static final int NUM_NODES = 100; 
    public static final int INF = 99999; 
    public static final int A = 20; 
    public static final int B = 18; 
    public static final int C = 47; 
    public static final int D = 44; 
    public static final int E = 53; 
    public static final int F = 67; 
    public static final int G = 95; 
    public static final int H = 93; 
    public static final int I = 88; 
    public static final int W = 66; 

    public static boolean even(int num) { 
     return num % 2 == 0; 
    } 

    public static boolean odd(int num) { 
     return num % 2 == 1; 
    } 

    public static void initialize(int[][] adjMat) { 
     for (int i = 0; i < adjMat.length; i++) 
      for (int j = 0; j < adjMat.length; j++) { 
       if (i == j) { 
        adjMat[i][j] = 0; 
       } else { 
        adjMat[i][j] = INF; 
       } 
      } 

     for (int x = 0; x < adjMat.length; x++) { 
      int row = x/10; 
      int column = x % 10; 

      if (even(row)) { 
       if (column != 9) 
        adjMat[x][x + 1] = 1; 
      } 
      if (odd(row)) { 
       if (column != 0) 
        adjMat[x][x - 1] = 1; 
      } 
      if (even(column)) { 
       if (row != 9) 
        adjMat[x][x + 10] = 1; 
      } 
      if (odd(column)) { 
       if (row != 0) 
        adjMat[x][x - 10] = 1; 
      } 
     } 
    } 

    public static void floydWarshall(int[][] adjMat) { 
     // commented this out because you are also allocating 
     // adjMat in the main method. 
     //adjMat = new int[adjMat.length][adjMat.length]; 
     initialize(adjMat); 

     for (int k = 0; k < adjMat.length; ++k) { 
      for (int i = 0; i < adjMat.length; ++i) { 
       for (int j = 0; j < adjMat.length; ++j) { 
        adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
       } 
      } 
     } 

     //return adjMat; 
    } 

    public static int[][] arrayCondenser(int[][] adjMat, int [] array) { 
     int[][] condensedArray = new int[array.length][array.length]; 
     //adjMat = floydWarshall(adjMat, N); 

     for (int storeFrom = 0; storeFrom < array.length; storeFrom++) { 
      for (int storeTo = 0; storeTo < array.length; storeTo++) { 
       condensedArray[storeFrom][storeTo] = adjMat[array[storeFrom]][array[storeTo]]; 
      } 
     } 

     return condensedArray; 
    } 

    public static void printGrid(int[][] adjMat) { 
     System.out.println("Adjacency Matrix: "); 
     System.out.printf("%5s", " "); 
     for (int i = 0; i < adjMat.length; i++) { 
      System.out.printf("%5d", i); 
     } 
     System.out.println(); 
     System.out.printf("%4s+", " "); 
     for (int i = 0; i < adjMat.length; i++) { 
      System.out.printf("%5s", "==="); 
     } 
     System.out.println(); 
     for (int i = 0; i < adjMat.length; ++i) { 
      System.out.printf("%4d|", i); 

      for (int j = 0; j < adjMat[i].length; ++j) { 
       if (adjMat[i][j] == INF) 
        System.out.printf("%5s", "INF"); 
       else 
        System.out.printf("%5d", adjMat[i][j]); 
      } 
      System.out.println(); 
     } 
    } 
    public static void printCondensedGrid(int[][] adjMat, int stores[]) { 
     System.out.println("Condensed grid: "); 
     System.out.printf("%5s", " "); 
     for (int i = 0; i < stores.length; i++) { 
      System.out.printf("%5d", stores[i]); 
     } 
     System.out.println(); 
     System.out.printf("%4s+", " "); 
     for (int i = 0; i < adjMat.length; i++) { 
      System.out.printf("%5s", "==="); 
     } 
     System.out.println(); 
     for (int i = 0; i < adjMat.length; ++i) { 
      System.out.printf("%4d|", stores[i]); 

      for (int j = 0; j < adjMat[i].length; ++j) { 
       if (adjMat[i][j] == INF) 
        System.out.printf("%5s", "INF"); 
       else 
        System.out.printf("%5d", adjMat[i][j]); 
      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) { 

     int adjMat[][] = new int[NUM_NODES][NUM_NODES]; 
     int[] stores = { A, B, C, D, E, F, G, H, I, W }; 

     floydWarshall(adjMat); 

     printGrid(adjMat); 
     int condensedArray[][] = arrayCondenser(adjMat, stores); 
     printCondensedGrid(condensedArray, stores); 

     System.out.println(); 
    } 
}

来源

2017-03-06 17:14:27

我相信下面的初始化（搬到initialize方法）应该更准确地反映你的图片。

在偶数行中，从每个节点到其右侧都有边。在奇数行中，从每个节点到其左侧都有边。在每一个偶数列中，都有从每个节点到下面节点的边。在每一个奇数列中，都有从每个节点到上面节点的边。

我也改变了矩阵的维数，以反映事实，即有100个节点，而不是99

要测试初始化，我加的测试方法testInit。此方法贯穿图中的每个节点，并检查左侧，右侧，上方和下方的节点，以查看这些节点是否存在边。您可以检查测试方法的输出并与上面的图片进行比较。

从main调用initialize和testInit。

EDIT：我已经实现使用100 X 4矩阵，其中的4个数字表示N，S，E，W方向的Gene的建议，因为这些是唯一的方向，其中链路可以存在。 Gene建议使用4位，但我使用了4个使用更多空间的阵列位置，但我已将实际相邻节点放置在这些位置（如果非零）。

public class AdjacencyMatrix 
{  
    public static final int NUM_NODES = 100; 
    public static final int NUM_DIRECTIONS = 4; 
    public static final int NORTH = 0; 
    public static final int EAST = 1; 
    public static final int SOUTH = 2; 
    public static final int WEST = 3; 
    public static boolean even(int num) { 
     return num%2==0; 
    } 

    public static boolean odd(int num) { 
     return num%2==1; 
    } 

    public static void initialize(int [][] adjMat, int N, int DIR) { 
     for(int i = 0; i < N; i++) 
      for(int dir = 0; dir <DIR; dir++) 
       adjMat[i][dir]=0; 

     for(int x = 0; x<N; x++) 
     { 
      int row = x/10; 
      int column = x%10; 

      if (even(row)) { 
       if (column!=9) 
        adjMat[x][EAST]=x+1; 
      } 
      if (odd(row)) { 
       if (column!=0) 
        adjMat[x][WEST]=x-1; 
      } 
      if (even(column)){ 
       if (row!=9) 
        adjMat[x][SOUTH]=x+10; 
      } 
      if (odd(column)) { 
       if (row!=0) 
        adjMat[x][NORTH]=x-10; 
      } 
     } 
    } 



    public static void main(String[] args) 
    { 

     int adjMat[][] = new int[NUM_NODES][NUM_DIRECTIONS]; 
     initialize(adjMat, NUM_NODES, NUM_DIRECTIONS); 
     testInit(adjMat, NUM_NODES, NUM_DIRECTIONS);    

    } 

    private static void testInit(int[][] adjMat, int N, int DIR) { 
     for(int fromNode=0; fromNode < N; fromNode++) { 
      System.out.print(fromNode + "-->"); 
      for (int num=0; num<DIR; num++) { 
       if (adjMat[fromNode][num]>0) { 
        System.out.print(adjMat[fromNode][num] + ", "); 
       } 
      } 
      System.out.println(); 
     } 
    } 
}

样本输出：

0-->1, 10, 
1-->2, 
2-->3, 12, 
3-->4, 
4-->5, 14, 
5-->6, 
6-->7, 16, 
7-->8, 
8-->9, 18, 
9--> 
10-->20, 
11-->1, 10, 
12-->22, 11, 
13-->3, 12, 
14-->24, 13, 
15-->5, 14, 
16-->26, 15, 
17-->7, 16, 
18-->28, 17, 
19-->9, 18, 
20-->21, 30, 
21-->11, 22, 
22-->23, 32, 
23-->13, 24, 
24-->25, 34, 
25-->15, 26, 
26-->27, 36, 
27-->17, 28, 
28-->29, 38, 
29-->19, 
30-->40, 
31-->21, 30, 
32-->42, 31, 
33-->23, 32, 
34-->44, 33, 
35-->25, 34, 
36-->46, 35, 
37-->27, 36, 
38-->48, 37, 
39-->29, 38, 
40-->41, 50, 
41-->31, 42, 
42-->43, 52, 
43-->33, 44, 
44-->45, 54, 
45-->35, 46, 
46-->47, 56, 
47-->37, 48, 
48-->49, 58, 
49-->39, 
50-->60, 
51-->41, 50, 
52-->62, 51, 
53-->43, 52, 
54-->64, 53, 
55-->45, 54, 
56-->66, 55, 
57-->47, 56, 
58-->68, 57, 
59-->49, 58, 
60-->61, 70, 
61-->51, 62, 
62-->63, 72, 
63-->53, 64, 
64-->65, 74, 
65-->55, 66, 
66-->67, 76, 
67-->57, 68, 
68-->69, 78, 
69-->59, 
70-->80, 
71-->61, 70, 
72-->82, 71, 
73-->63, 72, 
74-->84, 73, 
75-->65, 74, 
76-->86, 75, 
77-->67, 76, 
78-->88, 77, 
79-->69, 78, 
80-->81, 90, 
81-->71, 82, 
82-->83, 92, 
83-->73, 84, 
84-->85, 94, 
85-->75, 86, 
86-->87, 96, 
87-->77, 88, 
88-->89, 98, 
89-->79, 
90--> 
91-->81, 90, 
92-->91, 
93-->83, 92, 
94-->93, 
95-->85, 94, 
96-->95, 
97-->87, 96, 
98-->97, 
99-->89, 98,

如果你想保持原来的索引，你可以修改if语句在initialize方法，像这样：

 if (even(row)) { 
      if (column!=9) 
       adjMat[x][x+1]=1; 
     } 
     if (odd(row)) { 
      if (column!=0) 
       adjMat[x][x-1]=1; 
     } 
     if (even(column)){ 
      if (row!=9) 
       adjMat[x][x+10]=1; 
     } 
     if (odd(column)) { 
      if (row!=0) 
       adjMat[x][x-10]=1; 
     }

来源

2017-03-04 04:10:56

评论不适用于扩展讨论;这个对话已经[转移到聊天]（http://chat.stackoverflow.com/rooms/137361/discussion-on-answer-by-david-choweller-adjacency-matrix-graph-implementation）。 –

邻接矩阵图实现

回答

相关问题