06-2 그래프의 구현

※ 그래프의 구현

 - 그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 한다.

   순차 자료구조 방식을 이용하는 2차원 배열의 인접행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다.

   만들고자 하는 그래프의 특성과 필요한 연산에 따라 적당한 표현 방법을 만들자.

※ 순차 자료구조 방식을 이용한 그래프의 구현 : 인접 행렬

 - 두 정점이 인접하면 1 인접하지 않으면 0으로 표현

  - n개의 정점을 가지는 그래프를 n * n 의 인접 행렬로 표현하면 간선의 개수에 상관없이 n*n의 메모리를 사용하기 때문에 간선이 적은 경우엔 메모리 낭비가 일어날 수 있다.

※ 연결 자료구조 방식을 이용한 그래프의 구현 : 인접 리스트

 - 각 노드의 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성

 - 리스트 내의 정렬은 오름차순으로 한다.

AdjMatrix

public class AdjMatrix {

       private int matrix[][];

       private int vertexSize;

       public AdjMatrix() {

              // TODO Auto-generated method stub

              matrix = new int[50][50];

              vertexSize = 0;

       }

       public void insertVertex(int v){

              vertexSize++;

       }

       public void insertEdge(int v1, int v2){

              if(v1 >= vertexSize || v2 >= vertexSize){

                     System.out.println("vertex 값이 올바르지 않습니다.");

              }else{

                     matrix[v1][v2]=1;

              }

       }

       public void printAdjMatrix(){

              for(int i=0; i<vertexSize;i++){

                     for(int j =0; j<vertexSize; j++){

                           System.out.print(matrix[i][j] + " ");

                     }

                     System.out.println();

              }

       }

}

GrapNode

public class GraphNode {

       GraphNode link;

       private int vertex;

       public GraphNode(int v) {

              // TODO Auto-generated constructor stub

              this.link = null;

              vertex = v;

       }

       public int getVertex(){

              return vertex;

       }

       public void setVertex(int v){

               vertex = v;

       }

}

AdjList

public class AdjList {

       private GraphNode[] headList;

       private int headListSize;

       public AdjList() {

              // TODO Auto-generated constructor stub

              headList = new GraphNode[10];

              headListSize = 0;

       }

       public void insertVertex(int i){

              headListSize++;

       }

       public void insertEdge(int v1, int v2){

              if(v1 >=headListSize || v2 >= headListSize){

                     System.out.println("vertex 값이 올바르지 않습니다.");

              }else{

                     GraphNode gn = new GraphNode(v2);

                     gn.link=headList[v1];

                     headList[v1]= gn;

                     GraphNode temp = headList[v1];

                     int tempValue;

                     //오름차준 정렬

                     while(temp.link != null){

                           if(temp.getVertex() > temp.link.getVertex()){

                                  tempValue = temp.link.getVertex();

                                  temp.link.setVertex(temp.getVertex());

                                  temp.setVertex(tempValue);

                           }

                           temp = temp.link;

                     }

              }

       }

       public void printAdjList(){

              for(int i =0; i <headListSize; i++){

                     GraphNode temp = headList[i];

                     System.out.printf("정점 %c 의 인접리스트 -> ",(i+65));

                     while(temp.link != null){

                           System.out.printf("%c -> ", temp.getVertex()+65);

                           temp = temp.link;

                     }

                     System.out.printf("%c\n",(temp.getVertex()+65));

              }

       }

}

Main

public class Main {

       public static void main(String[] args) {

              AdjMatrix m = new AdjMatrix();

              for(int i =0; i<4 ;i++){

                     m.insertVertex(i);

              }

              m.insertEdge(0, 3);

              m.insertEdge(0, 1);

              m.insertEdge(1, 3);

              m.insertEdge(1, 2);

              m.insertEdge(1, 0);

              m.insertEdge(2, 3);

              m.insertEdge(2, 1);

              m.insertEdge(3, 2);

              m.insertEdge(3, 1);

              m.insertEdge(3, 0);

              System.out.println("\n그래프 G의 인접행렬 : ");

              m.printAdjMatrix();

              System.out.println();

              AdjList l = new AdjList();

              for(int i =0; i<4 ;i++){

                     l.insertVertex(i);

              }

              l.insertEdge(0, 3);

              l.insertEdge(0, 1);

              l.insertEdge(1, 3);

              l.insertEdge(1, 2);

              l.insertEdge(1, 0);

              l.insertEdge(2, 3);

              l.insertEdge(2, 1);

              l.insertEdge(3, 2);

              l.insertEdge(3, 1);

              l.insertEdge(3, 0);

              System.out.println("\n그래프 G의 인접행렬 : ");

              l.printAdjList();

              System.out.println();

       }

}