[TIL] 2022.07.26 | 트리와 그래프

 

Tree

노드들이 나무가지처럼 연결된 비선형 계층 구조로 나무를 거꾸로 뒤집어 높은 모양과 유사하다.

트리내에 다른 하위 트리들이 반복되어 있는 재귀적 구조자료라고도 한다.

 

노드의 특징은 아래의 리스트와 같다

• 하나의 루트 노드에 0개이상의 하위 트리로 기본 구성이 되어있다.
• 데이터를 순차적으로 저장하지 않는 비선형 자료구조이고 트리안에 또다른 트리가 있는 재귀적 구조자료이기도 하다.
• 노드간에 부모와 자식관계를 가지고 있는 계층형 구조자료인데 자식노드는 하나의 부모노드만 가진다.
• 노드가 n개인 트리는 항상 "n-1" 개의 간선을 가진다.

트리 용어 일람

• root: 최상위 노드 
• parent: child를 갖는 노드 
• child: parent를 갖는 노드 
• edge: 노드를 연결하는 선,
• depth: root부터 어떤 특정 노드까지의 깊이 
• height: 해당 노드까지 트리의 높이 (level-1) 
• leaf: 자식이 없는 최말단 노드 
• degree: 자식 수

트리 예제 코드

public class TreeEx { 
	private String value;
  private ArrayList<Solution> children;

  public Solution() {	//전달인자가 없을 경우의 생성자
    this.value = null;
    this.children = null;
  }
  public Solution(String data) {	//전달인자가 존재할 경우의 생성자
    this.value = data;
    this.children = null;
  }

  public void setValue(String data) {  
    this.value = data;
  }

  public String getValue() {      //현재 노드의 데이터를 반환
    return value;
  }
  public void addChildNode(Solution node) {
    if(children == null) children = new ArrayList<>();
    children.add(node);
  }
  public void removeChildNode(Solution node) {
    if(children == null) children.remove(node);
  }

  public ArrayList<Solution> getChildrenNode() {
    return children;
  }

  public boolean contains(String data) {      //재귀를 사용하여 값을 검색합니다.
    if(value.equals(data)) return true;

    if(children != null) {
      for(int i = 0; i < children.size(); i++) {
        return children.get(i).contains(data);
      }
    }
    return false;
  }
}

---

Graph

노드와 그 노드를 연결하는 간선을 하나로 모아둔 자료구조로 연결되어있는 객체간의 관계를 표현할 수 있는 

자료구조라고 할 수 있다.

 

트리와 비슷하지만 다른 형태를 가지고 있다 몇가지 이야기를 해보자면 그래프는 무방향을 가지고 있고 부모 자식 노드 개념등이 없다.

 

그래프의 특징은 아래와 같다.

• 그래프는 네트워크 모델 이다.
• 2개 이상의 경로가 가능하다.
• 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.
• 순회는 DFS나 BFS로 이루어진다.
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.

그래프 용어 일람

• 정점(vertex): 위치라는 개념. (node 라고도 부름)
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
• 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
• 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

주로 사용하는 부분은 포털 사이트의 검색 엔진이나 SNS 네비게이션등에서 사용하고 있는 자료구조기도 하다.

 

그래프 예제 코드

public class graphEx { 
	private int[][] graph;

  public void setGraph(int size) {
    graph = new int[size][size];

    for(int i = 0; i < size; i++) {
      for(int j = 0; j < size; j++) {
        graph[i][j] = 0;
      }
    }
  }
  public int[][] getGraph() {
    return graph;
  }
  public void addEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return;
    graph[from][to] = 1;
  }

  public boolean hasEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return false;
    else if(graph[from][to] == 1) return true;
    else return false;
  }

  public void removeEdge(int from, int to) {
    if(from >= graph.length || to >= graph.length) return;
    graph[from][to] = 0;
  }
}