| [Data Structure] 그래프(Graph) (0) | 2019.11.09 |
|---|---|
| 배열을 이용한 리스트 구현 (0) | 2019.11.08 |
그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관걔를 표현한다.
그래프는 정점(Vertex)과 정점을 연결하는 간선(Edge)의 집합로 객체간의 관계를 표현할 수 있는 자료구조이다.
선형 자료구조나 트리 자료구조로 표현하기 어려운 $N:N$ 관계를 가지는 원소들을 표현하기 용이하다.
서로 대칭적인 관계를 연결해서 나타낸 그래프
간선에 방향이 없는 그래프
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
간선을 화살표로 표현, 방향성의 개념이 포함이된다.
간선에 방향이 있는 그래프
정점 A에서 정점 B로만 갈수 있는 간선은 <A, B>와 같이 표현한다.
이동하는 데 드는 비용을 간선에 부여한 그래프
가중치는 두 정점 사이의 거리, 지나는 시간, 금액등이 될수 있으며 또한 음수인 경우도 존재한다.
두 정점 간의 이동방향이 다를경우 가중치가 다를 수 있음.
어떠한 정점 v에서 시작하여 다시 v로 가는 경로가 없는 그래프
위상정렬이 있는 유향그래프
정점들에 대해 가능한 모든 간선들을 가진 그래프
원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
G=(V, E)로 표현, V=정점의 집합, E=간선의 집합
두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
정점에 인접한 정점의 수
방향그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분
시작 정점부터 도착 정점까지의 정점들을 나열하여 표현
단순 경로(Simple Path)
사이클(Cycle)
그래프는 주로 2가지 방법을 이용하여 표현한다
메모리나 성능을 고려해서 결정해야한다.
두 정점을 연결하는 간선의 유무를 행렬로 표현
배열의 인덱스는 정점을 의미
정점 i와 j 사이에 간선이 없으면 $a[i][j]=0$, 간선이 있으면 $a[i][j]=1$로 표현
대각선의 요소는 무의미
정점의 개수 $N$이 커지면 필요한 메모리 크기는 $N^2$에 비례하여 커짐
어떤 정점의 인접 정점을 찾을때마다 $N$개의 정점을 탐색해야한다.
정점의 개수에 비례하여 시간도 증가한다.
그래프를 인접리스트로 표현하여 불필요한 메모리사용과 비용을 줄일 수 있음.
각 정점에 대한 인접 정점들을 순차적으로 표현
하나의 정점에 인접한 모든 노드를 연결 리스트 형태로 저장
가중치 정보를 표시하려면 노드에 가중치 필드를 추가하여 표현한다.
모든 자료(정점)을 빠짐없이 탐색하는 것을 의미한다.
그래프에서는 2가지 방식으로 모든 정점을 탐색한다.
가장 마지막 정점으로 돌아가 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용하거나 재귀 호출을 이용하여 구현한다.
import java.util.List;
public class DFS {
static class Edge {
int adjvertex; // 선분의 다른쪽 정점
public Edge(int v) { // 생성자
adjvertex = v;
}
}
int N; // 그래프 정점의 수
List<Edge>[] graph;
private boolean[ ] visited; // DFS 수행 중 방문한 정점을 true로 만든다.
public DFS(List<Edge>[] adjList) { // 생성자
N = adjList.length;
graph = adjList;
visited = new boolean [N];
for (int i = 0; i < N; i++) visited[i] = false; // 배열 초기화
for (int i = 0; i < N; i++) if (!visited[i]) dfs(i);
}
private void dfs(int i) {
visited[i] = true; // 점점 i가 방문되어 visited[i]를 true로 만든다.
System.out.print(i+" "); // 정점 i가 방문되었음을 출력한다.
for (Edge e: graph[i]) { // 정점 i에 인접한 각 정점에 대해
if (!visited[e.adjvertex]) { // 정점 i에 인접한 정점이 방문 안되었으면 재귀호출
dfs(e.adjvertex);
}
}
}
}인접한 정점들에 대해 탐색 후 차례로 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용한다.
import java.util.*;
public class BFS {
static class Edge {
int adjvertex;
public Edge(int v) {
adjvertex = v;
}
}
int N; // 그래프 정점의 수
List<Edge>[] graph;
private boolean[ ] visited; // BFS 수행 중 방문한 정점의 원소를 true로 만든다.
public BFS(List<Edge>[] adjList) { // 생성자
N = adjList.length;
graph = adjList;
visited = new boolean [N];
for (int i = 0; i < N; i++) visited[i] = false; // 배열 초기화
for (int i = 0; i < N; i++) if (!visited[i]) bfs(i);
}
private void bfs(int i) {
Queue<Integer> q = new LinkedList<Integer>(); // 큐 선언
visited[i] = true;
q.add(i); //큐에 시작 정점 s를 삽입
while (!q.isEmpty()) {
int j = q.remove(); // 큐에세 정점 j를 가져옴
System.out.print(j+" ");
for (Edge e: graph[j]) { // 정점 j에 인접한 정점들 중 방문안된 정점 하나씩 방문
if (!visited[e.adjvertex]) {
visited[e.adjvertex] = true;
q.add(e.adjvertex); // 새로이 방문된 정점을 큐에 삽입
}
}
}
}
}『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)
| # 자료구조 개요 (0) | 2020.03.10 |
|---|---|
| 배열을 이용한 리스트 구현 (0) | 2019.11.08 |
import java.util.NoSuchElementException;
public class ArrayList{
static class List<E> {
private E a[]; // 리스트의 항목들을 저장할 배열
private int size; // 리스트의 항목 수
// 생성자
public List() {
a = (E[]) new Object[1]; // 최초로 1개의 원소를 가진 배열 생성
size = 0; // 항목 수를 0으로 초기화
}
// 리스트가 empty이면 true 리턴
public boolean isEmpty() {
return size == 0;
}
// 가장 뒤에 새 항목 삽입
public void insertLast(E newItem) {
if (size == a.length) // 배열에 빈 공간이 없으면
resize(2 * a.length); // 배열 크기 2배로 확장
a[size++] = newItem; // 새 항목 삽입
}
// 새 항목을 k-1번쨰 항목 다음에 삽입
public void insert(E newItem, int k) {
if (size == a.length) // 배열에 빈 공간이 없으면
resize(2 * a.length); // 배열 크기 2배로 확장
// 한 칸씩 뒤로 이동
for (int i = size - 1; i >= k; i--)
a[i + 1] = a[i];
a[k] = newItem;
size++;
}
// k번째 항목 삭제
public E delete(int k) {
// underflow 경우에 프로그램 정지
if (isEmpty())
throw new NoSuchElementException();
E item = a[k];
// 한 칸씩 앞으로 이동
for (int i = k; i < size; i++)
a[i] = a[i + 1];
size--;
if (size > 0 && size == a.length / 4) // 배열에 항목들이 1/4만 차지한다면
resize(a.length / 2); // 배열을 1/2 크기로 축소
return item;
}
// k번째 항목을 리턴, 단순히 읽기만 한다.
public E peek(int k) {
// underflow 경우에 프로그램 정지
if (isEmpty())
throw new NoSuchElementException();
return a[k];
}
// 배열 크기 조절
private void resize(int newSize) {
Object[] t = new Object[newSize]; // newSize 크기의 새로운 배열 t 생성
for (int i = 0; i < size; i++)
t[i] = a[i]; // 배열 s를 배열 t로 복사
a = (E[]) t; // 배열 t를 배열 s로
}
// 배열의 항목들을 출력
public void print() {
if (isEmpty())
System.out.print("배열이 비어있음.");
else
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + "\t ");
System.out.println();
}
}
public static void main(String[] args) {
// TO-DO
}
}『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)
| # 자료구조 개요 (0) | 2020.03.10 |
|---|---|
| [Data Structure] 그래프(Graph) (0) | 2019.11.09 |