鄰接矩陣圖實現

我想要實現使用鄰接矩陣如下圖：鄰接矩陣圖實現

被寫入會發現所有其他商店從每家商店的距離最短的項目。這是正在使用的代碼：

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）。 –

鄰接矩陣圖實現

回答

相關問題