Developer Cafe

연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된 그래프 G를 G=(V, E)로 정의한다. 그래프는 간선의 방향성 유무에 따라서 방향 그래프와 무방향 그래프가 있고, 연결정도에 따라서 연결 그래프와 단절 그래프, 완전 그래프가 있다. 그리고 가중치를 가진 간선으로 이루어진 가중치 그래프가 있다. 그래프를 구현하기 위해서 표현하는 방법은 순차 자료구조 방식을 이용하는 2차원 배열의 인접 행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다. 1. 인접 행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다. A B C D A 0 1 0 1 B ..

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 원 하나를 노드로 그 노드는 정점이라 부르고, 정점간 관계인 선은 간선이라 부른다. 또한 그래프는 트위터 팔로우 기능처럼 화살표로 표현된 것을 방향 그래프, 페이스북처럼 상호작용하는 그래프는 무방향 그래프라한다. 위 그림에서 앨리스는 밥과 직접 커넥션이 있으나 신시아와 직접 커넥션이 없다. 비직접적인 커넥션을 포함해 앨리스 전체 네트워크를 찾으려면 두가지 방법이 있다. 1. 너비 우선 탐색 2. 깊이 우선 탐색 여기선 너비 우선 탐색만 포스팅하고 깊이 우선 탐색은 차후 업데이트하거나 따로 비교포스팅하겠다. 너비 우선 탐색 1. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다 표시하고 큐에 추..