비선형 자료구조

자료간의 관계가 1:n 또는 n:n 관계
계층적 구조를 나타내기 좋습니다.
대표적인 비선형 자료구조로는 트리, 그래프가 있습니다.

구분	그래프 (Graph)	트리 (Tree)
정의	노드(Node) 또는 객체를 간선(Edge)으로 연결한 구조	그래프의 한 종류, 방향성이 없고 순환하지 않음
방향	무방향(Undirected) 또는 유방향(Directed)	무방향 그래프 (Undirected Graph)
순환	순환(Cyclic), 자기 자신을 연결하는 간선(Self-Loop) 구조가 가능하다	순환 불가능(Acyclic), 자기 자신을 연결하는 간선(Self-Loop) 불가능
루트	존재 할 수도 있고 존재하지 않을 수도 있다	하나의 루트 노드(Root Node) 존재
모델	네트워크 모델(Network Model)	계층 모델(Hierarchical Model)
순회	넓이 우선 탐색(BFS), 깊이 우선 탐색(DFS)	전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)
간선	그래프에 따라 다르며, 간선이 없을 수도 있음	N개의 노드(Node)라면 N-1개의 간선(Edge) 존재

트리

트리 구성요소

root : 트리 구조를 형성하는 최상위 시작점 노드
edge (간선) : 노드와 노드를 연결선
parent : 자식 노드가 있는 노드
child : 부모 노드의 하위의 노드 (상위 노드와 부모 자식 관계)
leaf : 트리의 가장 하위의 노드들
sub tree : 트리의 하위의 트리 모향을 하고 있는 트리 형태 - 하나의 트리는 서브 트리가 모여서 만들어 진것
sibling : 같은 부모를 가지고 있는 노드들

size : root를 포함해서 트리내의 모든 스레드의 수
depth : 깊이, node에서 root까지의 거리,
root 노드를 기준으로 가장 깊숙히 위치한 노드까지 도착할때 필요한 edge 개수

사용처

• 폴더 경로, 가계도, 조직도
• DB 구조

트리 순회

• 중위 순회 (in-order traversal) left -> visit -> right
• 전위 순회 (pre-order traversal) visit -> left -> right
• 후위 순회 (post-order traversal) left -> right -> visit
• 레벨순회(Levelorder Traversal)
  중위, 전위, 후위 순회 = DFS Depth-First Search 깊이 우선 탐색
  레벨순회 = BFS Breadth-First Search 너비 우선 탐색

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

//중위 순회
public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.println(node.value);
            inOrderTraversal(node.right);
        }
}

//전위 순회
public void preOrderTraversal(TreeNode node) {
        if (node != null) {
        	System.out.println(node.value);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
}

//후위 순회
public void postOrderTraversal(TreeNode node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.println(node.value);
        }
}

이진트리

각 노드가 최대 2개의 child를 갖는 트리

이진 탐색 트리의 조건
왼쪽 child 노드 값 < parent 노드 값 < 오른쪽 child 노드 값
= 최하위 child 왼쪽 노드값 = 최솟값
= 최하위 child 오른쪽 노드값 = 최대값

//최소값
public T min() {
    return this.minNode(this.root);
}

private T minNode(Node node) {
    T minData = node.data;
    while (node.left != null) {
        minData = node.left.data;
        node = node.left;
    }
    return minData;
}

//최대값
public T max() {
    return this.maxNode(this.root);
}

private T maxNode(Node node) {
    T maxData = node.data;
    while (node.right != null) {
        maxData = node.right.data;
        node = node.right;
    }
    return maxnode
}

그래프

그래프 구성요소

vertex(정점): 노드(Node), 데이터가 저장된다.
edge(간선): 링크(arcs)라고도 하며, 노드간의 관계를 나타낸다.

사용처

• 길찾기, 네비게이션
• 캐릭터 이동
• 팔로우 팔로워 관계도
• 관련 검색어

종류

• 무방향 그래프(Undirected Graph):
  간선에 방향이 없고, 간선이 두 노드를 양방향으로 연결합니다.
• 방향 그래프(Directed Graph, Digraph):
  간선이 한 노드에서 다른 노드로 이어지며, 방향을 갖습니다.
• 가중치 그래프(Weighted Graph):
  간선에 가중치(Weight)가 할당된 그래프입니다. 가중치는 두 노드 간의 거리, 비용, 시간 등의 값을 나타낼 수 있습니다.
• 사이클 그래프(Cyclic Graph):
  노드가 순환하여 원래 노드로 돌아오는 경로(Cyclic)가 있는 그래프입니다.
• 비순환 그래프(Acyclic Graph):
  그래프에 사이클이 없는 경우입니다. ex) 트리

그래프 표현 방법

1. 인접 행렬(Adjacency Matrix):
   2차원 배열
   장점: 노드 간의 연결 정보를 빠르게 조회할 수 있습니다.
   단점: 메모리 사용량이 많아질 수 있습니다
   (ex 희소 그래프 - 연결 안된 노드도 모두 파악).
2. 인접 리스트(Adjacency List):
   리스트로 표현하는 방법
   장점: 메모리 효율적
   (ex 희소 그래프 - 연결 안된 노드는 생략).
   단점: 특정 노드 간의 연결 여부를 찾기 위해 리스트를 탐색해야 합니다.

• 희소 그래프 : 최소한의 간선을 가진 형태의 그래프

참고 예시)

• 인접 리스트

노드 0: [1, 4]
노드 1: [0, 2, 3, 4]
노드 2: [1, 3]
노드 3: [1, 2, 4]
노드 4: [0, 1, 3]

• 인접 행렬

	0	1	2	3	4
0	0	1	0	0	1
1	1	0	1	1	1
2	0	1	0	1	0
3	0	1	1	0	1
4	1	1	0	1	0

인접리스트

import java.util.*;

class Graph {
    private int V;   // 노드의 수
    private LinkedList<Integer>[] adj; // 인접 리스트

    // 그래프 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 노드를 연결하는 메서드
    void addEdge(int v, int w) {
        adj[v].add(w); // v에서 w로 가는 간선을 추가
        adj[w].add(v); // 무방향 그래프이므로 w에서 v로도 간선을 추가
    }
}

인접 행렬

class Graph {
    private int V;   // 노드의 수
    private int[][] adjMatrix; // 인접 행렬

    // 그래프 생성자
    Graph(int v) {
        V = v;
        adjMatrix = new int[v][v];
    }

    // 노드를 연결하는 메서드
    void addEdge(int v, int w) {
        adjMatrix[v][w] = 1;
        adjMatrix[w][v] = 1; // 무방향 그래프이므로 반대 방향도 1로 설정
    }
}

탐색

DFS(Depth First Search)

하나의 방향을 정해서 끝까지 도달하는 형태로 탐색합니다.
재귀 함수를 사용해서 탈출 조건을 만들어 두고 탐색해 나갑니다.
예상한 동작 순서대로 탐색하기 때문에 동작 검증을 하기 좋습니다. (모두 더해 보기 -> 모두 빼 보기)
최악의 경우 가장 마지막에 모든 경우의 수를 탐색했을때에 결과가 도출 될 수 있습니다.

private final int V; // 노드의 개수
private final List<List<Integer>> adj; // 인접 리스트
 // DFS 탐색 함수
void DFS(int v, boolean[] visited) {
	visited[v] = true; // 현재 노드를 방문 처리
	System.out.print(v + " "); // 노드 출력

	// 인접 노드 재귀적으로 방문
	for (int next : adj.get(v)) {
		if (!visited[next]) {
			DFS(next, visited);
  		}
	}
}

// DFS 탐색 시작 함수
void DFS(int v) {
	boolean[] visited = new boolean[V];
		DFS(v, visited);
	}

BFS(Breadth First Search)

현재 노드에서 가능한 경우의 수를 하나씩 탐색 해보는 형태입니다.
순서가 보장 되어야 하기 때문에 Queue / LinkedList 를 사용합니다.
1. 가장 먼저 넣었던 것을 꺼내서
2. 연결된 점을 Queue에 넣기
3. Queue가 빌 때 까지 반복
여러 경우를 하나씩 탐색하기 때문에 검증하기에 어려운 점이 있을 수 있습니다.
(+ -> - -> + -> -)
하나씩 해당 노드의 모든 경우의 수를 탐색하기 때문에 한번에 결과를 도출하기는 어려워도 모든 경우의 수를 다해봐야 하는 확률은 낮습니다.
= 시간복잡도가 낮습니다.

private final int V; // 노드의 개수
private final List<List<Integer>> adj; // 인접 리스트
 // BFS 탐색 함수
void BFS(int s) {
	boolean[] visited = new boolean[V];
	Queue<Integer> queue = new LinkedList<>();

	visited[s] = true; // 시작 노드를 방문 처리
	queue.add(s); // 큐에 추가

	while (!queue.isEmpty()) {
		int v = queue.poll(); // 큐에서 노드를 하나 꺼냄
		System.out.print(v + " "); // 노드 출력
		// 인접 노드 중 방문하지 않은 노드를 큐에 추가
		for (int next : adj.get(v)) {
			if (!visited[next]) {
				visited[next] = true;
				queue.add(next);
			}
		}
	}
}