Graph class 만들기!

안녕하세요 ☺️

지난번에 알아보았던 Graph! 그렇다면 코드로는 어떻게 나타낼 수 있는지 알아보겠습니다.

크게 Adjacency matrix(인접 행렬)와 Adjacency list(인접 리스트)가 있었는데, 두 가지 모두 코드로 설계해보겠습니다. 

 

---

먼저!

코드를 작성하기 전에 Graph에는 어떤 것들이 필요한 지 생각해 보면 작성하기 훨씬 수월합니다.

 

1) Graph를 구성하는 것에는 Vertex가 있죠

2) 또, vertex들을 연결하는 edge가 있습니다.

 

그렇다면 

1) vertex를 추가할 수 있는 코드

2) edge를 추가할 수 있는 코드

이렇게 두개는 필수적으로 들어가야 겠다는 사실을 인지하고 코드를 작성해주면 됩니다!

---

Graph를 이루고 있는 것은 Vertex이죠. Vertex는 node입니다.

그러므로 Node class도 미리 준비되어 있어야 Graph를 만들 수 있습니다.

 

 
public class Node {
    
    char data;
    
    public Node(char data){
        this.data = data;
    }
}
 

 

Graph는 Tree와 다르게 left, rigth node의 개념은 없으므로 따로 만들어 주지 않아도 됩니다.

 

그럼 이제 인접 행렬 그래프부터 코드를 작성해보겠습니다. 

 

1. Adjacency matrix(인접 행렬)

 

 
import java.util.ArrayList;
 
public class GraphMatrix {
    
    int size;
    ArrayList<Node> vertices; //그래프를 이루는 vertex를 담기 위한 ArrayList 선언
    int[][] matrix; //Edge 정보를 담을 2D array 선언
    
    public GraphMatrix(int size) { //size를 받을 수 있는 constructor
        
        //size를 설정해주고, vertices와 matrix 인스턴스화 하기 
        this.size = size;
        vertices = new ArrayList<>();
        matrix = new int[size][size];
        
    }
 
    //Vertex 추가하는 메서드
    public void addVertex(Node vertex) { //추가할 Node type의 vertex를 파라미터로 설정
        
        vertices.add(vertex); 
        
    }
    
    //Edge 추가하는 메서드 : vertex 간 edge를 추가해줍니다.
    public void addEdge(int from, int to) { //어떤 vertex에서 어떤 vertex 사이에 edge를 추가할 지를 파라미터로 설정 
        
        matrix[from][to] = 1;
        
    }
    
    
}
 

 

 

2. Adjacency list(인접 리스트)

 

import java.util.ArrayList;
import java.util.LinkedList;
 
public class GraphList {
    
    /*
        vertexAndEdges = {
                            {'A','B','C'}
                            {'B','A','D'}
                            {'C','A','B'}
                            {'D','B','C'}
                         }
                         
         와 같은 형태로 리스트를 만들게 됩니다.
         vertex와 edge정보가 담긴 부분은 LinkedList로, 
         LinkedList들을 담는 부분은 ArrayList로 만듭니다. 
         
         각 LinkedList의 0번째 요소가 바로 Vertex가 됩니다! 
                           
     */
    
    ArrayList<LinkedList<Node>> vertexAndEdges;
    
    public GraphList() {
        vertexAndEdges = new ArrayList<>();
    }
    
    public void addVertex(Node vertex) {
        //Vertex를 추가할 때는 앞으로 해당 vertex와 연결된 edge 정보를 같이 담을 수 있도록
        //LinkedList를 하나 새로 생성하고, 그 안에 0번째 요소로 vertex를 추가하면 됩니다. 
        LinkedList<Node> vertexList = new LinkedList<>();
        vertexList.add(vertex);
        
        //LinkedList를 담는 vertexAndEdges에 넣어줍니다.
        vertexAndEdges.add(vertexList);
    }
    
    public void addEdge(int from, int to) {
        //from번째에 위치한 vertex list를 찾아서 currentVertex 변수에 할당해줍니다.
        LinkedList<Node> currentVertex = vertexAndEdges.get(from);
        //to번째에 해당하는 vertex를 찾아서 dstVertex 변수에 할당합니다.
        Node dstVertex = vertexAndEdges.get(to).get(0);
        
        //from에 해당하는 vertex list의 요소(edge)로서 dstVertex를 넣어줍니다.
        currentVertex.add(dstVertex);
    }
}
 

 

앞에서 얘기한 vertex 추가와 edge 추가 이 두개와

matrix와 list 각각에서 어떤 데이터 구조를 사용 하는지만 잘 알고 있다면 

코드를 작성해내는데는 큰 무리가 없을 것 같습니다. ☺️