DFS와 사용자가 제공 한 인접성 매트릭스를 사용하여 Undirected Graph에 연결된 구성 요소의 양을 표시하는 Java 프로그램

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

솔루션이 거의 완료되었습니다. visited 배열을 검사하는 for 루프 내에 변수 범위를 조정해야했습니다. 또한 ArrayIndexOutOfBoundsException이 발생할 수 있으므로 0부터 시작하는 인덱스를 사용해야합니다. 또한 소스를 입력으로 제공 할 필요가 없습니다. 다음은 고정 코드입니다.

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();  
    } 
}