[260623]그래프

목차

• 그래프의 개념 및 용어
• 그래프 표현 방법

그래프의 개념 및 용어

그래프의 개념

그래프(Graph)는 점(Node)와 선(Edge)을 이용하여 객체관의 관계를 표현하는 비선형 자료구조이다. 이는 거미줄다발 형태로 퍼져나가는 지하철 노선도나 SNS, 지도와 같은 복잡한 연결망을 쉽게 모델링하기 위해 사용된다. 트리와는 달리 계층적이지 않은 연결관계를 표현할 수 있다.

그래프의 용어

1)구성요소

• 정점(Vertex | Node)

  	그래프를 구성하는 기본 원소로서 보통 객체 그 자체가 이에 해당한다.

• 간선(Edge | Link)

  	정점을 잇는 선을 의미하며 두 객체간의 관계를 나타낸다.

• 가중치(Weight)

  간선의 비용, 시간, 거리 등의 값을 표현한다. 가중치가 표시되어 있지 않은경우 모두 동일한 가중치이다. 
  ex)제일 가까운 길 찾기, 제일 값이 싼 통신경로 찾기 등

  
  

2)간선의 종류

• 방향이 있는 간선

  	한 방향으로만 이동 가능한 간선이다
  	이미지로 표현할때는 화살표를 그려서 방향을 표시한다

• 방향이 없는 간선

  양방향으로 이동 가능한 간선이다
  실선으로 표시한다

  
  

3)그래프 종류

• 무방향 그래프

  	방향이 없는 그래프이다

• 유향 그래프

  	방향이 있는 그래프이다

4)정점 관련 용어

• 차수(Degree)

  무방향 그래프에선 한 정점에 연결된 간선의 수, 방향 그래프에선 들어오고 나가는 간선의 수를 나타낸다.

  
  

5)경로 관련 용어

• 경로(Path)

  	이는 한 정점에서 다른 정점까지 가는 길을 나타낸 것이다.

  보통 경로를 계산할때는 같은 정점을 두번 방문하지 않는다

• 사이클(Cycle)

  	경로가 `1->2->3->1` 이런 식으로 순환이 있으면 사이클이라 부른다. 시작 노드에 다시 방문하는 경우 사이클이다.

그래프 표현 방법

// 무방향 그래프의 인접 리스트 표현
List<List<Integer>> graph = new ArrayList<>();

// 그래프 초기화 (인덱스 0은 빈 리스트로 유지)
graph.add(new ArrayList<>());         // 인덱스 0 (사용하지 않음)
graph.add(Arrays.asList(2));          // 정점 1 -> 2
graph.add(Arrays.asList(1, 3, 4));    // 정점 2 -> 1, 3, 4
graph.add(Arrays.asList(2, 5));       // 정점 3 -> 2, 5
graph.add(Arrays.asList(2));          // 정점 4 -> 2
graph.add(Arrays.asList(3));          // 정점 5 -> 3



// 방향 그래프의 인접 리스트 표현 (가중치 포함)
List<List<int[]>> graph = new ArrayList<>();

graph.add(new ArrayList<>());                    // 인덱스 0 (사용하지 않음)
graph.add(new ArrayList<>());                    // 정점 1 (연결 없음)
graph.add(Arrays.asList(new int[]{1, 1},         // 정점 2 -> 1(1)
                        new int[]{3, 1},         // 정점 2 -> 3(1)
                        new int[]{4, 2}));       // 정점 2 -> 4(2)
graph.add(Arrays.asList(new int[]{2, 2},         // 정점 3 -> 2(2)
                        new int[]{5, 4}));       // 정점 3 -> 5(4)
graph.add(new ArrayList<>());                    // 정점 4 (연결 없음)
graph.add(new ArrayList<>());                    // 정점 5 (연결 없음)

이런식으로 각 정점에서 인접한 정접들을 리스트로 표현하는 것을 인접 리스트(Adjacency List)라고 부른다.
실제 간선 수 만큼 저장하기 때문에 메모리 공간을 효율적으로 사용할 수 있고, 각 정점의 인접 정점을 빠르게 순회할 수 있다.