[Data Structure2] Graph Matrix

인접 행렬 형태로 구현한 그래프.

class GraphMatrix{

  //######################################################//
  //인접행렬로 표현한 그래프 row & col 크기가 같아야 한다.#########//
  //#####################################################//
int[][] graph={
       {0, 1, 1, 1, 0, 0, 0},
       {1, 0, 0, 0, 1, 0, 0},
       {1, 0, 0, 0, 1, 1, 0},
       {1, 0, 0, 0, 0, 1, 0},
       {0, 1, 1, 0, 0, 0, 1},
       {0, 0, 1, 1, 0, 0, 1},
       {0, 0, 0, 0, 1, 1, 0}
  };
 
int nodeNum= graph.length;   //노드의 갯수. 인접행렬(변수명:graph)의 사이즈에 의존한다.
boolean[] visited= new boolean[nodeNum];    //방문했는지 아직 방문하지 않았는지 체크한다.

  //###############################################################//
  //그닥 필요는 없으나 일관성을 위해 적어 둠. 본 클래스 내의 함수 호출시 매개변수로 사용.
  //###############################################################//
public final int BFS=     11;     //너비 우선 탐색
public final int DFS=     12;     //깊이 우선 탐색
public final int MATRIX= 21;   //인접행렬 형태로 그래프 출력
public final int EDGE=     22;  //연결된 간선 형태로 그래프 출력

  //###############################################################//
  //그래프를 탐색한다. 매개변수 : sWay-탐색 방법(BFS, DFS), firstNode-처음 방문할 노드 번호
  //###############################################################//
public void search(int sWay, int firstNode){
   for(int i=0;i<nodeNum;i++){
        visited[i]=false;
       }

   switch(sWay){
        case BFS:
            BFS(firstNode);
            break;
        case DFS:
            DFS(firstNode);
            break;
        default:
            System.out.println("정의 되지 않은 매개 변수입니다.");
       }
  }

  //#######################################################//
  //그래프를 출력한다. 그래픽 형태로 출력하면 아주 멋지겠으나, 능력 부족.
  //매개변수 : sWay-출력 방법(Matrix, Edge)
  //######################################################//
public void print(int sWay){
   switch(sWay){
        case MATRIX:
            printMatrix();
            break;
        case EDGE:
            printEdge();
            break;
        default:
            System.out.println("정의 되지 않은 매개 변수입니다.");
       }
  }

  //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
  //--------------------------< 탐색 부분 >-------------------------//
  //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//

  //######################################################//
  //너비 우선 탐색##########################################//
  //#####################################################//
private void BFS(int sNode){
   if(visited[sNode]==false){
        System.out.print("\n//------ Breadth Fitst Search -----//\n");
        visited[sNode]=true;
        System.out.print(sNode+", ");
       }

   for(int i=0;i<nodeNum;i++){
        for(int j=0;j<nodeNum;j++){
            if(graph[i][j]==1 && visited[j]==false){    //현재 방문한 노드의 인접 노드 중 방문하지 않은 노드
                System.out.print(j+", ");
                visited[j]=true;
               }
           }
       }
  }

  //###############################################################//
  //깊이 우선 탐색#################################################//
  //###############################################################//
private void DFS(int sNode){
   if(visited[sNode]==false){    //첫 노드 방문시 한번만 실행된다.
        System.out.print("\n//------ Depth Fitst Search -----//\n");
        System.out.print(sNode+", ");
        visited[sNode]=true;
       }
      
   for(int i=0;i<nodeNum;i++){
        if(graph[sNode][i]==1 && visited[i]==false){    //현재 방문한 노드의 인접 노드 중 방문하지 않은 노드
            visited[i]=true;

            System.out.print(i+", ");
            DFS(i);    //recurrence
           }
       }
  }

  //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
  //---------------------< 그래프 출력 부분 >----------------------//
  //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//

  //######################################################//
  //인접 행렬 형태로 출력. 즉, graph[][]를 그대로 출력.############//
  //#####################################################//
private void printMatrix(){
   System.out.println("//------ Matrix 형태로 출력 -----//");
   for(int i=0;i<nodeNum;i++){
        for(int j=0;j<nodeNum;j++){
            System.out.print(graph[i][j]);
           }
        System.out.println();
       }
  }

  //###############################################################//
  //연결된 간선 형태로 출력  ex) (v1, v2)##########################//
  //###############################################################//
private void printEdge(){
   System.out.println("//----- Edge 형태로 출력 -----//");
   for(int i=0;i<nodeNum;i++){
        for(int j=i+1;j<nodeNum;j++){    //방향그래프 이므로 (v1, v2), (v2, v1)형태의 중복 회피.
            if(graph[i][j]==1){
                System.out.println("("+i+", "+j+")");
               }
           }
       }
  }
};

public class Test{
public Test(){
   GraphMatrix graph= new GraphMatrix();

   graph.print(graph.MATRIX);
   graph.print(graph.EDGE);

   graph.search(graph.BFS, 0);
   graph.search(graph.DFS, 0);
  }

public static void main(String args[]){
   Test t= new Test();
  }
};