[C언어] 자료구조 - 그래프 -1

이어서 그래프에 대해서 배워볼건데... 그래프가 눈에 가장 잘띄는데

코딩은 가장 귀찮은 듯한 느낌이야. ㅠㅠㅠㅠㅠ

 

뭐 그래프는 뭐 요소들끼리 서로 연결되어 있는 관계를 나타내는 자료구조인데..

말도 쉽고, 눈도 쉽지만 ,, 손은 어려운 ㅋㅋㅋㅋㅋ

 

아무튼 최단경로찾는 그런 교통어플리케이션도 이러한 그래프를 이용하는 경우가 정말 많다.

지하철 노선도 처럼 ~~~도로 끝나는 것은 거의 다 그래프다. ㅋㅋㅋ

 

그래프의 역사를 올라가고 싶지만... 너무 길기에 바로 본론으로 들어가자

 

그래프의 정의를 보자

 

vertex 와 edge로 이루어지며 

다르게 불리기도 한다.

 

정점(vertices) 또는 노드(node)

•여러 가지 특성을 가질 수 있는 객체 의미

•V(G) : 그래프 G의 정점들의 집합

 

간선(edge) 또는 링크(link)

•정점들 간의 관계 의미

•E(G) : 그래프 G의 간선들의 집합

 

또한 그래프라는 그림은 연결관계를 그냥 표현해준 것이기 때문에 생긴 것은 달라보여도

연결관계를 살펴보면 같은 경우가 있다.

 

?? 다르게 생겼는데 같은그래프다. 이렇게 그림으로 판단하면,,, 큰 코 다치고 정확히 파악하기 위해서는 그림보단 표로 정리해서 보는게 확실하다. 매트릭스나 그런거

 

또한 용어도 정리해볼까??

1. 인접 정점(adjacent vertex)

–하나의 정점에서 간선에 의해 직접 연결된 정점

–G1에서 정점 0의 인접 정점

정점 1, 정점 2, 정점 3

 

그니까 인접정점을 알면 누구랑 연결되어있는지 알 수 있겠네?

그럼 인접정점들의 집합을 알면 그게 그래프네? 

매트릭스로 표현 가능하겠구나!!! 까지 오면 굿

2. 차수(degree)

–하나의 정점에 연결된 다른 정점의 수

–무방향 그래프에서는 이렇다.

•G1에서 정점 0의 차수: 3

•차수의 합은 간선 수의 2배

간선 하나에 2개 연결되어있잖아 ㅎㅎ

 

–방향 그래프에서는 이렇다. 

•진입차수, 진출차수

•모든 진입(진출) 차수의 합은 간선의 수

 

방향그래프란 것은 밑에 설명되어있을 것이다.

 

3. 그래프의 경로(path)

–무방향 그래프의 정점 s로부터 정점 e까지의 경로

•정점의 나열 s, v1, v2, ..., vk, e

•반드시 간선 (s, v1), (v1, v2), ... , (vk, e) 존재해야 함

 

–방향 그래프의 정점 s로부터 정점 e까지의 경로

•정점의 나열 s, v1, v2, ..., vk, e

•반드시 간선 <s, v1>, <v1, v2>, ... ,<vk, e> 존재해야 함

 

괄호가 다르게 생김,, (둥근놈은 방향성이 없어보이고 < 뾰족한놈은 방향성 있어보이네 ㅇㅋ?

 

4. 경로의 길이(length)

–경로를 구성하는데 사용된 간선의 수

그렇다. 최단경로란 간선의 수가 가장 적은 것을 말하는 것이겠지

 

5. 단순경로(simple path)

–경로 중에서 반복되는 간선이 없는 경로

•1, 0, 2, 3은 단순경로

•1, 0, 2, 0은 단순경로 아님

 

6.사이클(cycle)

–시작 정점과 종료 정점이 동일한 경로

•0, 1, 2, 0은 사이클

사이클이 중요한데... 왜 중요하냐면 나중에 나옴 싸이클 정의만 확실히 알아두자

 

 

 

7. 연결 그래프(connected graph)

–모든 정점쌍에 대한 경로 존재

–G2는 비연결 그래프임

그니까 간선이 연결되지 않는 노드가 하나라도 있으면 비연결 그래프다 이말이야

 

8. 트리(tree)

–그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프

트리는 정말로 앞에 배운 트리랑 같다. 걔네들은 싸이클 절대 없지 계층적구조인데 그치?

 

 

9. 완전그래프(complete graph)

–모든 정점이 연결되어 있는 그래프

–n개의 정점을 가진 무방향 완전그래프의 간선의 수

•n×(n-1)/2

–n=4, 간선의 수 = (4×3)/2 = 6

 

그래프의 종류도 다양하다

간선의 종류에 따라 구분되는데

 

1. 무방향그래프 (undirected graph)

 

•간선을 통해서 양방향으로 갈수 있음 // 정해져 있지 않잖아 ㅇㅇ

•(A, B)로 표현

•(A, B) = (B, A)

 

 

2. 방향그래프 (directed graph)

 

•간선을 통해서 한쪽 방향으로만 갈 수 있음

•일방통행 길

•<A, B> 로 표현

•<A, B> ≠ <B, A> // 교환법칙 성립 안되네 ㅋㅋㅋ 일방통행이니까 역주행 금지

 

3. 가중치 그래프(weighted graph)

 

–네트워크(network)라고도 함 // 그렇대 왜인지는 나도 몰라

–간선에 비용(cost)이나 가중치(weight)가 할당된 그래프 // 사실 최단경로 따지자면 이렇게따져야함 ㅋㅋㅋㅋ

거리가 짧은데 신호등 겁나 많아봐 오래걸리잖아, 근데 거리는 좀 길더라도 신호등 없으면 빨리가잖아? 그런거야

 

–가중치 그래프 예

•정점 : 각 도시를 의미

•간선 : 도시를 연결하는 도로 의미

•가중치 : 도로의 길이 

 

4. 부분그래프(subgraph)

–정점 집합 V(G)와 간선 집합 E(G)의

부분 집합으로 이루어진 그래프

 

전체를 간선을 기준으로 다 쪼갰다고나 할까?? ㅋㅋㅋ

 

–V(G1)= {0, 1, 2, 3},      E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}

–V(G2)= {0, 1, 2, 3},      E(G3)= {(0, 1), (0, 2))}

–V(G2)= {0, 1, 2},         E(G2)= {<0, 1>, <1, 0>, <1, 2>}

 

 

 

 

와 이것만 머리에 넣어도 터질듯 

머리는 이따가 터뜨리기로 하고 우선 여기까지만 하자