通過鄰接矩陣java的簡單連通圖

我想用一個程序來決定一個圖是否簡單連接或不使用鄰接矩陣。我設法讓代碼告訴我所有的節點都有一個鏈接，但這並不能保證我在第一個和最後一個節點（簡單連接圖的定義）之間有一條路。我是一名初學者，所以我不知道這種問題是否可以在這裏發佈。任何想法我怎麼能這樣做？這是我的代碼到目前爲止。任何建議表示讚賞。通過鄰接矩陣java的簡單連通圖

package lab41; 

import java.util.Scanner; 

public class Graf { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     System.out.println("Introduceti nr de noduri:"); 
     int n = s.nextInt(); 
     int[][] a = new int[n + 1][n + 1]; 
     int i, j, k; 
     System.out.println("Introduceti matricea adiacenta:"); 

     for (i = 1; i <= n; i++) 
      for (j = 1; j <= n; j++) { 
       System.out.println("a[" + i + "][" + j + "]="); 
       a[i][j] = s.nextInt(); 
      } 

     int x = 0; 
     j = 1; 
     i = 1; 
     do { 
      if (a[i][j] == 1) { 
       i++; 
       j = 1; 
       x++; 
      } else 
       j++; 

     } 
     while (i < n && j <= n); 

     if (x == n - 1) 
      System.out.println("Graful este conex"); 
     else 
      System.out.println("Graful nu este conex"); 
    } 


}

來源

2014-05-06 123123d

要了解如果圖形連接就可以執行任意節點開始DFS & BFS如果被訪問的所有節點，這意味着圖是連通的。

算法：

分配列表，visitedNodes = {}，和一隊列= {}
挑選任何節點，說節點0
開始BFS從節點0隊列= {節點0}
彈出隊列的頭部，比如節點是x。如果節點x在visitedNodes中，則轉到步驟3.否則，將x放入visitedNodes列表中。
訪問節點X的所有鄰居，並將其放置在一個隊列
繼續步驟3到5，直到隊列爲空

來源

2014-05-06 16:35:12 Kakarot

通過鄰接矩陣java的簡單連通圖

回答

相關問題