그래프
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
인접 리스트를 통한 그래프 구현프로그래밍 기초/자료구조 2021. 5. 3. 09:37
인접 리스트 통한 그래프 구현 그래프 구현/인접 리스트 인접 리스트는 각각의 노드를 하나의 포인터로 하여 특정 노드에서 이동 가능한 노드를 표현하는 방법으로 다음과 같이 표현된다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayListGraph() 비어있는는 인스턴스 생성 속성 NodeCount 현재 노드의 개수 메서드 InsertNode() 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 제거 Clear() 저장되어 있는 모든 데이터 삭제 GetDegreeIn(int) 노드의 진입 차수 반환 GetDegreeOut(i..
-
인접 행렬을 통한 그래프 구현프로그래밍 기초/자료구조 2021. 4. 22. 20:21
인접 행렬을 통한 그래프 구현 인접 행렬로 그래프를 표현하는 것은 다음과 같이 각각의 노드가 순서대로 존재하는 것으로 가정하여 표현하는 것이다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayGraph() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 ArrayGraph(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성 속성 NodeCapacity 노드의 최대 개수 NodeCount 현재 노드의 개수 메서드 InsertNode() 가능할 경우 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 후 모든 데이터 위치 조정 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 ..
-
그래프(Graph)프로그래밍 기초/자료구조 2021. 4. 8. 11:15
그래프 그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다. 그래프의 구성요소 노드(또는 정점) 데이터 저장 및 표현 간선 데이터 간의 관계 표현 그래프의 종류 그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다. 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프 그래프의 표현) 그래프는 방향성에 따라 다르게 표현된..