Tree & Graph

⭐ Tree

• 그래프의 여러 구조 중 단방향 그래프의 한 구조 (비선형 구조)
• 데이터 타입을 Custom으로 정의하고, new 키워드를 통해 새로운 객체(인스턴스) 생성 가능하며 Method 사용 가능

Full Binary Tree

 

📌 Tree 구조의 요소

• Depth = root ~ leef node 까지의 depth 표현가능 / root(A) = 0    B,I = 1     C,F,J,M = 2
• Level = root(A) = 1    B,I = 2  ...
• Height = leef node를 기준으로 root 까지 0 ~ 올라감
• Sub Tree = Sub node 를 가지고 있으면 그 영역은 1개의 Sub Tree라고 봄

 

📌 Tree Method

• addChildNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 함
• removeChildNode(node): 입력받은 node를 Tree에서 삭제할 수 있어야 함
• getChildrenNode(): 현재 트리에서 존재하는 children을 리턴
• contains(value): 트리에 포함된 데이터를 찾을 수 있어야 함

---

⭐ Graph

 통상적인 그래프가 아닌 네트워크망 구조의 형태를 가진 그래프

 

• setGraph(size): 그래프에 size만큼의 버텍스를 추가해야 합니다.
• getGraph(): 인접 행렬 정보가 담긴 배열을 반환합니다.
• addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
• hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
• removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.

 

 

📌 Graph의 구성요소

• 정점 (Vertex / Node)
  그래프에서 위치를 나타냄
• 간선 (Edge / Link / Branch)
  그래프에서 위치간의 관계를 나타냄, 즉 각 정점(노드)를 연결하는 선을 의미
• 인접 정점 (Adjacent Vertex)
  간선(Edge)에 의해 직접 연걸된 정점을 의미함
• G (V, E)
  그래프는 정점과 간선의 집합이므로 G(V, E)는 그래프 자체를 의미함

 

📌 그래프의 종류

• 무방향 그래프
  간선을 통해 양방향으로 이동할 수 있는 그래프
  G(A,B)는 G(B,A)와 동일
• 방향 그래프
  간선에 방향이 존재하는 그래프
  G(A,B)와 G(B,A)는 다름
• 가중치 그래프
  간선에 비용 또는 가중치가 할당된 그래프
  '네트워크' 라고도 함
• 연결 그래프
  무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
• 비연결 그래프
  무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
• 순환 그래프
  단순 경로의 시작 정점과 종료 정점이 동일한 경우
  ※ 단순 경로(Simple Path) : 반복되는 정점이 없는 경로
• 비순환 그래프
  순환이 없는 그래프

 

 

📌 Graph의 표현방식
- 일반적으로 인접행렬과 인접리스트 방식이 있음 (인접행렬 <-> 인접리스트 | 정반대의 특징)

🎃 인접행렬

- 두 정점을 이어주는 간선 존재 시 이 두 정점은 인접하다

- 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄

- 이어지면 1(true), 아니면 0(false)     * 가중치 그래프라면 1대신 관계에서 의미 있는 값 저장

 

 

Graph의 정점과 정점간의 관계

 

 

🎃 인접리스트

인접리스트를 이용한 그래프 구현

 

📌 ArrayList를 이용하여 구현한 인접리스트

import java.util.ArrayList;
 /*
 * @ TITLE Adjacency List (인접리스트)
 */
 // 그래프(리스트) 클래스
class ListGraph {
    private ArrayList<ArrayList<Integer>> listGraph;
     // 그래프 초기화
    public ListGraph(int initSize) {
        this.listGraph = new ArrayList<ArrayList<Integer>>(); // 그래프 생성
        // 그래프 초기화
        // put(int x, int y) 에서 입력되는 정점의 값은 0 이상의 정수이나
        // ArrayList의 index는 0 부터 시작이므로
        // ArrayIndexOutOfBoundsException 방지를 위해
        // 정점을 담는 인접리스트의 size는 1을 더하여 초기화해줌
        // ex) initSize = 3
        // graph[0]
        // graph[1] -> 2 -> 3
        // graph[2] -> 1 -> 3 -> 4
        // graph[3] -> 1 -> 2 -> 4 -> 5
        for(int i=0; i<initSize+1; i++) {
            listGraph.add(new ArrayList<Integer>());
        }
    }
     // 그래프 return
    public ArrayList<ArrayList<Integer>> getGraph() {
        return this.listGraph;
    }
     // 그래프의 특정 노드 return
    public ArrayList<Integer> getNode(int i) {
        return this.listGraph.get(i);
    }
     // 그래프 추가 (양방향)
    public void put(int x, int y) {
        listGraph.get(x).add(y);
        listGraph.get(y).add(x);
    }
     // 그래프 추가 (단방향)
    public void putSingle(int x, int y) {
        listGraph.get(x).add(y);
    }
        // 그래프 출력 (인접리스트)
    public void printGraphToAdjList() {
        for(int i=1; i<listGraph.size(); i++) {
            System.out.print("정점 " + i + "의 인접리스트");
            
            for(int j=0; j<listGraph.get(i).size(); j++) {
                System.out.print(" -> " + listGraph.get(i).get(j));
            }
            System.out.println();
        }
    }
}
public class AdjacencyList {
    public static void main(String[] args) {
        int initSize = 6;
        ListGraph adjList = new ListGraph(initSize);
        
        adjList.put(1, 2);
        adjList.put(1, 3);
        adjList.put(2, 3);
        adjList.put(2, 4);
        adjList.put(3, 4);
        adjList.put(3, 5);
        adjList.put(4, 5);
        adjList.put(4, 6);
        adjList.printGraphToAdjList();
    }
 }