알고리즘[Graph]

그래프 소개 

그래프는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조이다.

 

-정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말한다.

-간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍(u, v)로 표현함.

 

그래프는 정점들의 집합 V와 간선들의 집합E를 사용하여 (V, E)로 나타냅니다.

- G =(V, E)

V = {1, 2, 3, 4, 5}

E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)}

 

그래프 용어

-방향성(유향) 간선(Directed edge)

1. 방향을 가진 정점의 쌍(u,v)으로 화살표로 표현하고 단방향을 가리킵니다.

2. 첫번째 정점u는 출발점을 의미하고 두 번째 정점v는 도착점을 의미합니다.

3. 방향성 간선을 가진 그래프를 방향성 그래프(Directed Graph)라고 합니다.

 

-무방향성(무향)간선(Undirected edge)

1. 방향이 없는 정점의 쌍(u,v)으로 직선으로 표현한다.

2.무방향성 간선(u,v)와(v,u)는 같다 (양방향을가리킴)(화살표?시작과 끝이없으니깐)

3.무방향성 간서을 가진 그래프를 무방향성 그래프(Undirected Graph)라고 합니다.

 

-참고로 이해하면 좋은 용어

단순경로 : 반복되는 노드가 없는 경로(같은 간선을 지나가지 않는 경로)

진입 차수 : 방향 그래프에서 외부 노드에서 들어오는 간선의수

진출 차수 : 방향 그래프에서 한 노드에서 외부 노드로 향하는 간선의 수

경로 길이 : 경로를 구하기 위해 사용된 간선의 수

 

 

인접 행렬 그래프

그래프의 노드를 2차원 Int형 배열로 만들어서

이동할 수 있으면 1, 없으면 0으로 표기한다.

 

방향성 그래프 A의 엣지가 B와D를 가르치기 때문에 1 로 표현(반대는없다)

무방향 그래프 같은경우는 화살표 방향이 없으므로 양쪽다 1를 표현 해 줄수있다.

 

인접 행렬 그래프의 장.단점

장점

1. 직관적이며 쉽게 구현 가능하다.

2. 2차원 배열 안에 모든 노드들의 간선 정보를 담기 때문에,

    두 노드에 대한 연결 정보를 조회할 때O(1)이면 가능하다.

단점

1. 모든 노드에 대한 간선 정보를 대입해야하여, O(n2)의 시간 복잡도가 소요된다.

2. 무조건 2차원 배열이 필요하기 때문에 메모리 공간이 낭비 된다.

 

그래프와 트리의 차이