자료구조 스터디 5주차

5-1) 그래프

노드와 엣지의 집합

 

유니온 파인드	그래프의 사이클이 생성되는지 판별하는 알고리즘
위상 정렬	사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청
다익스트라	시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘. 단 음수 간선은 있으면 안됨  =>최단거리 알고리즘
벨만-포드	다익스트라 알고리즘인데 음수 간선이 가능함.  음수 사이클이 존재하는가=>최단거리 알고리즘
플로이드-워셜	벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음) =>최단거리 알고리즘
최소 신장 트리	mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없음. 따라서 유니온 파인드를 이용함.

 

 

5-2)그래프의 표현

 

1)엣지리스트

엣지를 중심으로 그래프 표현. 가중치가 없는 그래프는 배열의 행 두개로 표현 가능.

 

방향이 없는 경우는 시작점을 설정하지 않아도 된다. 방향이 있는 경우는 시작점 필수

가중치가 있는 경우

 

가중치 행 추가.3개의 행으로 표현 가능

 

2)인접행렬

 

가중치가 없는 경우

 

가중치가 있는 경우는 해당 배열 값에 가중치를 삽입하면 된다.

 

노드와 관련되어있는 엣지를 탐색하려면 n번 접근해야하므로 노드에 비해 엣지가 적을 경우 공간 효율성이 떨어짐.

노드의 개수에 따라 사용 여부를 판단해야함.

빈공간도 탐색해야한다는 단점.

 

3)인접리스트

제일 많이 사용된다. 배열로 선언.

가중치가 없는 그래프의 경우

리스트와 배열의 차이는 가변적이라는 점.

배열은 인덱스로 접근 가능함.

가중치가 있는 그래프의 경우

가중치가 있는 경우 배열에 자료형을 클래스로 사용. 노드 객체를 리스트에 삽입.

구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어남.

빈공간이 없어 추가 메모리가 불필요하고 시간복잡도 측면에서 좋음.

 

5-3)유니온 파인드

여러 노드가 있을 때 특정 2개 노드를 연결해 1개의 깁합으로 묶는 유니온 연산(union)과 노드가 같은 집합에 속해있는지를 확인하는 파인드 연산(find)으로 형성되어 있는 알고리즘.

 

알고리즘 실행 전 초기화 

 1 과 4를 하나의 집합으로 만든다== 그래프에서 1과 4를 연결한다.

인덱스가 작은 노드를 대표 노드로 하고 그 값을 큰 노드 value에 삽입.

[union (1,4)(6,5)예시]

대표노드끼리 연결해준다. 처음에는 연결선이 없으므로 모두가 대표노드임.

union(4,6)은 4의 대표노드인 1과 6의 대표노드인 5를 연결해주는 것과 같음.

즉 인덱스 5번의 value값에 1 삽입.

 

 

find 연산:

1. 대상 노드 배열에 index값과 value값이 동일한지 확인.

2. 동일하지 않으면 vlaue값이 가리키는 index위치로 이동.(동일하면 대표노드)

3. index값과value값이 같을 때 까지.즉 대표노드를 찾을 때 까지 반복.

 

5-4) 위상정렬

 

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘.

정답이 여러개일 수 있음. 사이클이 없어야 함.

 

진입차수: 해당 노드를 가리키는 엣지의 수.

 

1. 먼저 진입 차수 배열을 선언해준다.

 

(모든 상황에서 그래프 데이터를 자료구조 형태로 바꾸어주는게 기본 시작.)

 

2. 진입차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드의 진입 차수를 1 뺀다.

 

위상정렬의 핵심은 진입차수.