안녕하세요,,, 죽지않고 돌아왔습니다.
꼴에 작년에 열심히 살았다고 번아웃 비슷하게 왔던거 같아요,,,
그래서 요새 매주 자료구조와 그 자료구에 관련된 문제를 1,2개 씩 풀고있는데 그걸 정리하면서 포스팅하면서 천천히 다시 글을 써보려고합니다,,,
자 그러면 오늘은 그래프에 대해서 한 번 얘기해보려고 합니다,,,
그래프(Graph)
노드와 노드를 연결하는 간선을 하나로 모아놓은 자료 구조
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다.
그래프 관련 용어
- 노드: 데이터가 저장됨
- 간선: 노드를 연결한 선
- 인접 정점: 간선에 의해 직접 연결된 노드
- 단순 경로: 반복되는 노드가 없는 경로 (같은 간선을 지나가지 않는 경로)
- 진입 차수: 방향 그래프에서 외부 노드에서 들어오는 간선의 수
- 진출 차수: 방향 그래프에서 한 노드에서 외부 노드로 향하는 간선의 수
- 경로 길이: 경로를 구하기 위해 사용된 간선의 수
그래프의 종류
- 방향 그래프
- 간선에 방향이 있는 그래프로, 간선 그래프 방향으로만 갈 수 있다
2. 무방향 그래프
- 간선에 방향이 없는 그래프로, 노드는 양방향으로 갈 수 있음
3. 가중치 그래프
- 노드를 이동할 때 드는 비용, 또는 가중치가 할당된 그래프
4. 완전 그래프
- 모든 노드가 간선으로 연결되어 있는 그래프
그래프의 표현 방법
1. 인접 행렬 그래프
방향 그래프
무방향 그래프
<대각선 기준으로 대칭>
