[알고리즘] Graph (그래프)

[알고리즘] Graph (그래프)

2021. 9. 20. 08:00ㆍ코딩 테스트 준비/알고리즘

728x90

안녕하세요? 주니하랑 입니다.

오늘은 알고리즘의 이진 탐색에 대해서 공부하는 시간인 것이에요.

코테를 유능한 개발자가 되기 위해 열심히 공부 해 보겠습니다!

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

📌 Graph (그래프) 란?

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 혹은 Node(노드)와 간선(Edge 혹은 Link, Branch)로 표현하기 위해 사용하는 것이에요.

📍Graph 관련 용어

👉 예제 :) 집에서 회사로 가는 경로 그래프로 표현

Node(노드) : 위치를 말한다. 정점(Vertext)라고도 하고, 위에 사진에서 집, 지하철, 회사, 버스의 동그라미가 Node이다.
Link(간선) : Node 간의 관계를 표시한 선으로 Node를 연결한 선이다. (Edge 또는 Branch라고도 한다.)
Adjacent Vertext(인접 정점) : Node와 Node 간의 간선으로 직접 연결된 정점(혹은 Node) 위의 그림에서 보았을 때, 집과 지하철 혹은 버스와 회사 등이 될 수 있다.
추가 참고 용어
- 정점의 차수 (Degree) : 무방향(위의 그림처럼 화살표가 그려지지 않은 간선들로 이뤄진 그래프)에서 하나의 Node에 인접한 Node의 수. 집을 기준으로 보면 지하철과 버스가 된다.
- 진입 차수 (In-Degree) : 방향 그래프(위의 그림처럼 화살표가 그려진 간선들로 이뤄진 그래프)에서 Node를 기준으로 외부에서 오는 간선의 수. 예를 들어 회사로 치면 회사 Node 입장에서 외부로 들어오는 간선은 2개(지하철, 버스)임으로 2개가 된다.
- 진출 차수 (Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수. 예를 들어 집을 기준으로 집은 버스와 지하철로 가는 화살표 간선이 두개이기 때문에 2개이다.
- 단순 경로 (Simple Path) : 처음 Node와 끝 Node를 제외하고, 중복된 Node가 없는 경로. 위의 그림에서 집에서 지하철을 타고, 회사를 갔다면 이는 중복되는 것이 없기 때문에 단순 경로이다. 하지만, 집에서 지하철을 타고, 회사로 와서 버스를 탔다가 다시 회사로 오면 회사가 두번 중복이 되어버리기 때문에 이 부분은 단순 경로가 아니다.
  만약 집에서 지하철을 타고, 회사를 갔다가 버스를 타고, 집에 다시 돌아오면 집이 두번 중복된 거 같이 보이나, 이는 중복이 아니고, 단순 경로 취급한다.
- 사이클 (Cycle) : 단순 경로의 시작 Node와 종료 Node가 동일한 경우 '단순 경로' 마지막에 든 예는 단순 경로도 되고, 사이클도 된다.

📍Graph (그래프) 종류

👉 무방향 그래프 (Undirected Graph)

간선의 방향이 없는 그래프
간선을 통해, Node는 양방향으로 갈 수 있다.
보통 Node A, B가 연결 되어 있을 때, (A, B) 또는 (B, A)로 표기한다.

👉 방향 그래프 (Directed Graph)

간선의 방향이 있는 그래프
보통 Node A, B가 A -> B로 가는 간선으로 연결 되어있을 때, <A, B>로 표기한다. (<B, A> 는 B -> A로 가는 간선이 있는 경우이기 때문에 <A, B>가 아니다.

👉 가중치 그래프 (Weighted Graph) 혹은 Network (네트워크)

간선에 비용 혹은 가중치가 할당(표기)된 그래프

맨 왼쪽에서 오른쪽을 가는데, 위에 부분에 경우 4, 5의 비용이 들어가는데 반해 아래쪽은 2, 1의 비용이 들어가는 것이에요.

결국 아래쪽으로 가는 것이 비용이 더 적게 드니 가깝다고 표현할 수 있겠지요!

👉 연결 그래프 (Connected Graph)와 비연결 그래프 (Disconnected Graph)

연결 그래프 (Connected Graph)
- 무방향 그래프에 있는 모든 Node에 대해 항상 경로가 존재하는 경우
비연결 그래프 (Disconnected Graph)
- 무방향 그래프에서 특정 Node에 대해 경로가 존재하지 않는 경우

👉 Cycle(사이클)과 비순환 그래프 (Acyclic Graph)

Cycle(사이클)
- 단순 경로의 시작 Node와 종료 Node가 동일한 경우
비순환 그래프(Acyclic Graph)
- Cycle이 없는 그래프

👉 Complete Graph (완전 그래프)

그래프의 모든 Node가 서로 연결되어 있는 그래프

📍Graph와 Tree 차이점

Tree는 Graph 중에 속한 특별한 종류라고 할 수 있는 것이에요!

	그래프	트리
정의	Node와 Node를 연결하는 간선으로 표현되는 자료 구조	그래프의 한 종류, 방향성이 있는 비순환 그래프
방향성	방향, 무방향 그래프 둘 다 존재	방향 그래프만 존재
사이클	사이클 가능, 순환 및 비순환 그래프 모두 존재	비순환 그래프로 사이클 없음
루트 노드	루트 노드 없음	루트 노드 있음
부모 / 자식 관계	부모 자식 개념이 없음	부모 자식 관계 있음

무방향, 방향, 가중치 그래프는 알고리즘에서 꽤 사용하기 때문에 눈 여겨 보는게 좋은 것이에요!

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글 그리고 방명록은 주니하랑에게 많은 힘이 됩니다