Программа Java для отображения количества подключенных компонентов в ненаправленном графике с использованием DFS и матрицы смежности, предоставленной пользователем

Question

Как говорится в названии, мне нужно создать программу Java, которая будет вычислять, сколько подключенных компонентов находится в ненаправленном графе, используя матрицу смежности, предоставленную пользователем. Я провел много часов и сумел успешно получить матрицу смежности и вычислить, сколько вершин не связано с моей «исходной» вершиной. Однако я не могу его обернуть и подсчитать связанные компоненты. Это слишком сложно для меня. Пожалуйста, помогите, спасибо. Это текущее состояние моего кода:

import java.util.InputMismatchException; 
import java.util.Scanner; 
import java.util.Stack; 
import java.util.Arrays; 

public class UndirectedConnectivityDfs 
{ 
    private Stack<Integer> stack; 

    public UndirectedConnectivityDfs() 
    { 
     stack = new Stack<Integer>(); 
    } 

    public void dfs(int adjacency_matrix[][], int source) 
    { 
     int number_of_nodes = adjacency_matrix[source].length - 1; 
     int visited[] = new int[number_of_nodes + 1]; 
     visited[0]=1; 
     int element = source;  
     int i = source; 
     int cc=1; 
      for (int k = 1; k <= number_of_nodes; k++){ 
      if (visited[k] == 0) 
      { 
     visited[source] = 1;  
     stack.push(source);   
     while (!stack.isEmpty()) 
     { 
      element = stack.peek(); 
      i = element;  
     while (i <= number_of_nodes) 
     { 
       if (adjacency_matrix[element][i] == 1 && visited[i] == 0) 
      { 
        stack.push(i); 
        visited[i] = 1; 
        element = i; 
        i = 1; 
       continue; 
       } 
       i++; 
     } 
      stack.pop();  
     } 
     boolean connected = false; 

     for (int vertex = 1; vertex <= number_of_nodes; vertex++) 
     { 
      if (visited[vertex] == 1) 
      { 
       connected = true; 
      } else 
      { 
       connected = false; 
          } 
     } 

      }else 
     { 
      System.out.print("There are "); 
      System.out.print(cc); 
      System.out.println(" connected compoments"); 
     } 
} 
} 

    public static void main(String...arg) 
    { 
     int number_of_nodes, source; 
     Scanner scanner = null; 
    try 
     { 
     System.out.println("Enter the number of nodes in the graph"); 
      scanner = new Scanner(System.in); 
      number_of_nodes = scanner.nextInt(); 

     int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; 
     System.out.println("Enter the adjacency matrix"); 
     for (int i = 1; i <= number_of_nodes; i++) 
      for (int j = 1; j <= number_of_nodes; j++) 
        adjacency_matrix[i][j] = scanner.nextInt(); 

     for (int i = 1; i <= number_of_nodes; i++) 
      { 
       for (int j = 1; j <= number_of_nodes; j++) 
       { 
        if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) 
        { 
         adjacency_matrix[j][i] = 1; 
        } 
       } 
      }   

     System.out.println("Enter the source for the graph"); 
      source = scanner.nextInt(); 

      UndirectedConnectivityDfs undirectedConnectivity= new UndirectedConnectivityDfs(); 
      undirectedConnectivity.dfs(adjacency_matrix, source); 

     }catch(InputMismatchException inputMismatch) 
     { 
      System.out.println("Wrong Input format"); 
     } 
     scanner.close();  
    } 
} 

Answer 1

Ваше решение почти выполнено. Вы должны были настроить область переменных в пределах цикла for, который проверяет массив visited. Также вам нужно использовать индексы, начинающиеся с 0, так как u может вызвать ArrayIndexOutOfBoundsException. Также вам не нужно указывать источник в качестве входных данных. Вот фиксированный код:

public class UndirectedConnectivityDfs 
{ 
    private Stack<Integer> stack; 
    public UndirectedConnectivityDfs() 
    { 
      stack = new Stack<Integer>(); 
    } 

    public void dfs(int adjacency_matrix[][]) 
    { 
     int number_of_nodes = adjacency_matrix[0].length; 
     int visited[] = new int[number_of_nodes];  
     int cc = 0; 
     for (int vertex = 0; vertex < number_of_nodes; vertex++) 
     { 
      if (visited[vertex] == 0) 
      { 
       int element = vertex;    
       int i = vertex;  
       visited[vertex] = 1; 
       cc++; 
       stack.push(vertex); 
       while (!stack.isEmpty()) 
       { 
        element = stack.peek(); 
        i = element;  
        while (i < number_of_nodes) 
        { 
         if (adjacency_matrix[element][i] == 1 && visited[i] == 0) 
         { 
          stack.push(i); 
          visited[i] = 1; 
          element = i; 
          i = 1; 
          continue; 
          } 
          i++; 
        } 
        stack.pop();  
       } 
      } 
     } 
     System.out.println("Number of Connected Components: " + cc); 
    } 

    public static void main(String...arg) 
    { 
     int number_of_nodes; 
     Scanner scanner = null; 
     try 
     { 
      System.out.println("Enter the number of nodes in the graph"); 
      scanner = new Scanner(System.in); 

      number_of_nodes = scanner.nextInt(); 
      int adjacency_matrix[][] = new int[number_of_nodes][number_of_nodes]; 

      System.out.println("Enter the adjacency matrix"); 

      for (int i = 0; i < number_of_nodes; i++) 
       for (int j = 0; j < number_of_nodes; j++) 
         adjacency_matrix[i][j] = scanner.nextInt(); 

      for (int i = 0; i < number_of_nodes; i++) 
      { 
       for (int j = 0; j < number_of_nodes; j++) 
       { 
        if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) 
        { 
          adjacency_matrix[j][i] = 1; 
        } 
        } 
      }   
      UndirectedConnectivityDfs undirectedConnectivity= new UndirectedConnectivityDfs(); 
      undirectedConnectivity.dfs(adjacency_matrix); 

     }catch(InputMismatchException inputMismatch) 
     { 
      System.out.println("Wrong Input format"); 
     } 
     scanner.close();  
    } 
}