728x90 그래프3 [자료구조] Graph 개인적으로 나는 그래프가 어렵다. 자료구조를 배운 이래, 가장 진입하기 힘들었던 자료구조다. 물론 아직도 잘 모른다. 더욱이 이를 활용한 문제 풀이는 아직 먼 산이다... 그러므로 그래프에 대해 공부해본다. 자바로 한다. 그래프는 정점을 간선으로 연결한 것 그 이상도 이하도 아니다. 가장 단순한 모델은 무방향 그래프. 그래프의 정의는 이렇다. 정의 | 그래프는 정점의 집합과 그 집합의 정점 쌍을 연결하는 간선의 모음이다. 그래서 어디서 이용할까? 지도, 컴퓨터 네트워크, 소셜 네트워크 등등... 어떤 항목들을 연결하는 것이 핵심이다. 연결은 어떤 관계를 의미한다. 즉, 특정 항목들의 연결 상태, 경로 추적 등등에서 이용된다. 용어 정점, V | 쉽게 생각하면 꼭짓점이다. 간선, E | 쉽게 생각하면 선분.. 2022. 1. 31. [자료구조] Graph 정의 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다. 노드는 보통 vertex로 v, 간선은 보통 edge로 e를 많이 사용합니다. 특징 방향 그래프와 무방향 그래프 모두 존재합니다. 사이클 가능, 자체 간선도 가능, 순환 그래프, 비순환 그래프 모두 존재합니다. 딱히 루트 노드의 개념은 없습니다. 물론 부모-자식 개념도 희미합니다. 순회는 DFS,BFS를 사용합니다. 그래프는 네트워크 모델입니다. 인접 리스트 혹은 인접 행렬로 구현합니다. 2021. 10. 27. [자료구조] Undirected Graph - 2차원 배열 Undirected Graph - 2차원 배열 그래프라 하면 꼭지점(vertex)와 간선(edge)가 존재합니다. 가중치가 있을 수도 있고, 또는 방향성이 존재할 수도 있습니다. 하지만 그 둘다 없는 방향성도 가중치도 없는 그래프를 2차원 배열로 만들어보고자 합니다. 만약 그래프가 이렇다면, 마치 직사각형 같다고 생각해봅시다. 여기서 꼭지점은 1, 2, 3, 4 이고 간선은 1-2, 2-4, 3-4, 1-3입니다. 결국 꼭지점의 갯수는 4개이고 간선의 갯수도 4개입니다. 이걸 코드로 표현한다면 아래와 같습니다. public static void main(String[] args){ Scanner sc = new Scanner(System.in); int vertex = 4; // 꼭지점 int edge .. 2021. 10. 27. 이전 1 다음 728x90
