• 일상생활의 문제를 → 그래프 이론으로 적용해보자!
• 개념들간의 연결관계가 있는가? (논리적인 연결관계 포함)

1. 용어

1. 연결 그래프 : 임의의 두 정점 vi, vj에 대해서 경로 path(vi,vj)가 존재하는 그래프
2. 트리 그래프 : 순환을 갖지 않는 연결 그래프, 무향그래프
   • 정점 N개 , 간선 N-1개
   • 임의의 두 정점에 대해 경로가 정확히 1개 존재한다.
   • 하나 이상의 정점을 가지며, 임의의 간선을 제거한 그래프는 연결 그래프가 아니다.

2. 그래프 표현

1. 간선 리스트(Edge List)

: 간선 E개 만큼의 배열 생성

→ 한 노드에 연결된 모든 간선들을 탐색할 필요가 있을 때 유리

//간선 E개
Info[] edge = new Info[E];

class Info{
	int start;
	int end;
	int weight;
...
}

2. 인접 행렬(Adjacent Matrix)

: V * V 개만큼의 이차원 배열 생성

3. 인접 리스트(Adjacent List)

: 정점 V개 만큼의 리스트 생성, 연결리스트로 연결

→

ArrayList<Info>[] node = new ArrayList[V+1]; //정점 V개만큼 생성

for(int v=1;v<V;v++){ //ArrayList초기화
	node[v] = new ArrayList<>();
}

class Info{
	int end;
	int weight;
...
}