[알고리즘 그림노트] 그래프-1 용어정리&그래프의 코드 표현법

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

용어 정리

1. G=(V,E)

그래프 G는 다음과 같은 요소로 이루어진 집합이다.

a.정점(vertex or node)들의 집합 V와 

b.간선(edge or line)들의 집합 E로 이루어졌다. 

여담 

트리는 그래프의 특수한 형태다.

그래프의 집합

그래프의 부분집합은 그래프이다

물론 그 그래프는 떨어져 나온 원본 그래프의 일부분다.

2. 인접(Adjacent)

두 정점을 연결한 간선이 있을때.

3. 루프(loop)

두 정점이 같은 정점인 간선

4. 경로(path)

특정 정점에서 다른 정점을 이동할때 거치는 

정점과 간선을 쭉 그린것.

5. 회로(Circuit) = Cycle

경로의 시작점과 끝점이 같은길

6. 길이(lenght)

경로 또는 순환을 구성하는 정점 개수

7. 차수(degree)

한 정접과 인접하는 간선개수

8. 이분그래프

그래프를 두 부분으로 분활 했을떄 

두 분할 사이를 련결하는 간선이 존재하는 그래프

9. 이분그래프 &완전 이분그래프

그래프 내의 정점 집합을 분활

분활로 이루어진 다른 정점 집합 사이에 간선이 존재 하면 이분그래프

이분 매칭

{a,c} {c,d,e}로 분활 하고

두가지 영역으로 나누가 분활된 두 영역을 이어붙이는것

10. 오일러 경로

그래프의 모든 간선들을 꼭 한번씩 지나는 경로 

한붓그리기?

11. 오일러 회로 

한번 돌아와야함

12. 해밀턴 경로

그래프의 모든 정점들을 꼭 한번씩 지나는 경로

13. 트리(tree) 

비순환적이며, 비방향성 그래프 q 뿌리 있는 트리(rooted tree) - 

한 정점이 뿌리로 지정된 트리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그래프의 분류_1 -> 정점의 방향성

정점(vertex)의 edge 방향 유무구분

방향 그래프 

정점간에 순서가 존재하는 그래프

진입 차수 In-degree 

진출 차수 Out-degree

무방향 그래프

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그래프의 분류_2 -> 정점의 차수

정점(vertex)의 degree 에 따른 분류

완전그래프

정점(vertex)의 degree = 그래프내부의 정점(vertex) 수 -1

즉, 모든 vertex가 edge 로 연결된 그래프

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그래프를 코드로 표현하는 방법

1.이차원 배열 (인접 행렬) int V[n][n];

>"모든 정보를 저장"

>정점(vertex) 개수(V)의 제곱에 해당하는 공간을 차지합니다.

V + E의 개수만큼 작성

>정점(vertex) 개수가 작으면 이차원 배열 이 효율적일 수 있습니다.

>장단점

- 장점: 

직관적이며 쉽게 구현 가능

- 단점: 

불필요한 정보의 저장이 많으며, 

그래프의 크기가 커지면 메모리 초과가 발생할 수 있음

2.연결 리스트 (인접 리스트) Node(연결리스트 구조체) node[n];

>"갈 수 있는 곳만 저장"

>장단점

- 장점: 

필요한 정보만 저장하여 메모리 절약 가능

- 단점: 

인접행렬에 비해 다소 어려움

>구현

리스트(List)나 벡터(Vector)등의 자료구조를 이용

정점(vertex) 개수가 크면 연결 리스트를 사용하는 게 효율적일 수 있습니다.