자료구조-그래프 (종류, 용어, 구현 방법)

그래프

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조

그래프 G는 객체를 나타내는 정점(V)와 객체를 연결하는 간선(E)의 집합이다

G=(V,E)

 

종류

무방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프

(Vi, Vj)로 표현한다

V정점은 ABCD

E간선은 AB, AD, BC, BD ,CD 방향이 없음

 

방향 그래프

=다이그래프

간선에 방향이 있는 그래프

Vi->Vj를 <Vi, Vj>로 표현한다

<A, B>는 A->B

<B, C>는 B->C

 

완전 그래프

각 정점에서 다른 모든 정점이 연결된, 최대로 많은 간선 수를 가진 그래프

 

정점이 n개인 무방향 그래프에서 최대 간선 수: n(n-1)/2개

정점이 n개인 방향 그래프에서 최대 간선 수: n(n-1)개

 

G5의 간선 수:

정점의 개수는 4개고 무방향 그래프이므로 완전 그래프가 되려면 4(4-1)/2=6개 간선 필요

 

G6의 간선 수:

정점의 개수는 4개고 방향 그래프이므로 완전 그래프가 되려면 4(4-1)=12개 간선 필요

 

부분 그래프

원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프

그래프 G와 부분 그래프 G' 관계

G1이라는 그래프의 부분 그래프 G1'의 예시

 

가중치 그래프

=네트워크

정점을 연결하는 간선에 가중치를 할당한 그래프

 

용어

인접: 두 정점을 연결하는 간선이 있을 때 서로 인접하다고 한다

부속: 인접한 두 정점 사이의 간선은 두 정점에 부속되었다고 한다

-G1그래프에서 A와 B, D는 인접해있고, 정점 A에 부속되어 있는 간선은 (A,B)와 (A,D)

 

차수: 정점에 부속되어 있는 간선의 수

-G1그래프에서 A의 차수는 2, B의 차수는 3

-G3그래프에서 B의 진입차수는 1, 진출차수는 2

 

경로: 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것

-G1그래프에서 A부터 C까지의 경로는 A-B-C와 A-D-C, A-D-B-C경로가 있다

경로 길이: 경로를 구성하는 간선의 수

 

단순 경로: 모두 다른 정점으로 구성된 경로

-그래프 G1에서 A부터 C까지의 경로 A-B-C는 단순 경로

-경로 A-B-D-A-B-C는 단순 경로가 아님

 

사이클: 단순 경로 중에서 경로의 시작 정점과 끝 정점이 같은 경로

-G1에서 단순경로 A-B-C-D-A는 사이클

 

DAG: 방향 그래프이면서 사이클이 없는 그래프

 

연결 그래프: 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프

-한 마디로 혼자 동떨어진 정점이 없는 그래프

-정점과 정점 사이에 경로가 있으면 연결 되었다고 한다

-단절 그래프: 연결되지 않은 정점이 있는 그래프

 

그래프의 추상 자료형

1. 공백 그래프 생성

2. 그래프 g가 정점이 없는 공백 그래프인지 검사

3. 삽입 연산

4. 정점 삭제 연산

5. 간선 삭제 연산

6. 정점v에 인접한 모든 정점 반환 연산

 

그래프 구현

순차 자료구조를 이용한 그래프 구현: 인접 행렬

-행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법

 

-그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다

n개의 정점을 가진 그래프-n x n정방행렬

행렬의 행번호, 열번호-그래프의 정점

행렬 값-두 정점이 연결되었으면 1, 아니면 0

 

-무방향 그래프의 인접 행렬

행i의 합=열i의 합=정점 i의 차수

 

-방향 그래프의 인접 행렬

행i의 합=정점 i의 진출차수

열i의 합=정점 i의 진입차수

 

배열 그래프 구현

30x30배열을 만들어서 4x4만 쓰고 있음

 

연결 자료구조를 이용한 그래프 구현: 인접 행렬

-각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트

-각 정점의 차수만큼 노드를 연결한다(인접 정점에 대해서 오름차순으로 연결)

-인접 리스트의 각 노드

정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성

정점에 대한 인접 리스트의 헤드포인터는 정점 개수만큼 필요

그래프는 정점의 집합이므로 각 정점에 대한 헤드 포인터를 그룹으로 묶어서 포인터 배열로 구성함

 

n개의 정점과 e개의 간선을 가진 무방향 그래프의 인접 리스트

해드 노드 배열의 크기: n

연결하는 노드의 수: 2e

각 정점 헤드에 연결된 노드의 수: 정점의 차수

 

n개의 정점과 e개의 간선을 가진 방향 그래프의 인접 리스트

해드 노드 배열의 크기: n

연결하는 노드의 수: e

각 정점 헤드에 연결된 노드의 수: 정점의 진출 차수

 

 

연결리스트 중에서 확인할 부분

이런 상태에서 A노드(인덱스 0)를 추가하려면 코드가 어떻게 되나

간단한 예시로 노드가 아래처럼 구성되어 있다고 할 때

typedef struct Ver{
 int index;
 struct Ver* link;
} Vertex;

A노드를 추가하려면

1. 새로운 노드 생성

2. 노드의 인덱스 값 넣기

3. 기존 리스트에 연결

Vertex new;
new.index = 0; //인덱스는 0이다
new.link = adjList[1].link; //1번째의 링크는 C노드(인덱스2)를 가리키고 있었다 A노드가 그걸 가짐
adjList[1].link = new; //1번째 링크는 이제 A노드로

원래 C에 연결되어 있던 [1]번 링크값을 A노드의 link가 가짐으로 C뒤에 A번이 연결

[1]번 링크값은 A로 연결하면 그 사이로 들어가짐

 

이렇게 NULL값을 갖는 D(3번 인덱스)를 추가한다고 해도 위랑 똑같음

Vertex new;
new.index = 0; //인덱스는 3이다
new.link = adjList[2].link; //2번째의 링크는 NULL을 가리키고 있었다 이제는 D가 그 값을 가짐
adjList[2].link = new; //2번째 링크는 이제 D노드로