[JAVA] 인접행렬과 인접리스트

//

//

인접 행렬

  package AdjGraph;
  ​
  public class GraphNode {
      int vertex;
      GraphNode link;
  ​
  }

  package AdjGraph;
  ​
  public class AdjMatrix {
      //"인접 행렬" 출력하기 위한 클래스
      private int matrix[][] = new int[10][10];
      private int totalV = 0;
      
      public void insertVertex(int v){
          totalV++;
      }
      
      public void insertEdge(int v1, int v2){
          if(v1>=totalV || v2>=totalV){
              //총 정점의 개수보다 초과하면
              System.out.println("그래프에 없는 정점입니다.");
          }
          else{
              matrix[v1][v2] = 1;
          }
      }
      
      public void printMatrix(){
          for(int i = 0; i < totalV; i++){
              for(int j = 0; j < totalV; j++){
                  System.out.printf("%2d", matrix[i][j]);
              }
              System.out.println();
          }
      }
  ​
  }
  ​

  package AdjGraph;
  import java.util.*;
  import java.io.*;
  ​
  public class AdjMatrixMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          AdjMatrix am = new AdjMatrix();
          
          //정점 추가
          for(int i=0; i<4; i++){
              am.insertVertex(i);
          }
          
          am.insertEdge(0, 3);
          am.insertEdge(0, 1);
          am.insertEdge(1, 3);
          am.insertEdge(1, 2);
          am.insertEdge(1, 0);
          am.insertEdge(2, 3);
          am.insertEdge(2, 1);
          am.insertEdge(3, 2);
          am.insertEdge(3, 1);
          am.insertEdge(3, 0);
      
          System.out.println("그래프 G의 인접행렬 : ");
          am.printMatrix();
          
      }
  ​
  }

인접 리스트

  package AdjList;
  ​
  public class GraphNode {
      int vertex;
      GraphNode link;
  ​
  }

  package AdjList;
  ​
  public class AdList {
      private GraphNode head[] = new GraphNode[10];
      private int totalV = 0;
      
      public void insertVertex(int v){
          totalV++;
      }
      
      public void insertEdge(int v1, int v2){
          if(v1 >= totalV || v2 >= totalV){
              System.out.println("그래프에 없는 정점입니다");
          }
          else{
              //삽입하는 간선은 항상 인접 리스트의 첫번째 노드로 삽입하도록 함.
              GraphNode node = new GraphNode();
              node.vertex = v2;
              node.link = head[v1];
              head[v1] = node;
              //head를 앞으로 옮김
          }
      }
      
      public void printAdList(){
          GraphNode gNode = new GraphNode();
          for(int i=0; i < totalV; i++){
              System.out.printf("정점 %c의 인접리스트", i+65);
              gNode = head[i];
              while(gNode != null){
                  System.out.printf("-> %c", gNode.vertex+65);
                  gNode=gNode.link;
              }
              System.out.println();
          }
      }
      
  ​
  }

  package AdjList;
  ​
  import AdjGraph.AdjMatrix;
  ​
  public class AdListMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
  ​
          AdList am = new AdList();
          
          //정점 추가
          for(int i=0; i<4; i++){
              am.insertVertex(i);
          }
          
          am.insertEdge(0, 3);
          am.insertEdge(0, 1);
          am.insertEdge(1, 3);
          am.insertEdge(1, 2);
          am.insertEdge(1, 0);
          am.insertEdge(2, 3);
          am.insertEdge(2, 1);
          am.insertEdge(3, 2);
          am.insertEdge(3, 1);
          am.insertEdge(3, 0);
      
          System.out.println("그래프 G의 인접행렬 : ");
          am.printAdList();
          
      }
  ​
  }