자료구조
-
자료구조...79일지 2021. 4. 21. 20:45
ArrayGraph 기능 메서드) 그래프에서 사용하는 기능 메서드를 구현한다. ArrayGraph.cpp /// /// 지정된 인덱스의 노드에 진입하는 차수를 반환한다. /// /// 노드의 인덱스 size_t ArrayGraph::GetDegreeIn(int index) { if (index = m_nodeCount) { return -1; } int count{ 0 }; for (int i = 0; i < m_nodeCount; i++) { count += m_graph[i][index]; } return count; } /// /// 지정된 인덱스의 노드에서 진출하는 차수를 반환한다. /// /// 노드의 인덱스 size_t ArrayGraph::GetDegreeOut(in..
-
자료구조...78일지 2021. 4. 20. 11:12
ArrayGraph 삭제 메서드) 노드와 에지를 삭제하는 메서드를 구현한다. ArrayGraph.cpp /// /// ArrayGraph에서 지정된 인덱스의 노드를 제거한다. /// /// 제거할 값 void ArrayGraph::RemoveNode(int index) { if (index = m_nodeCount) { return; } for (int i = index; i < m_nodeCount - 1; i++) { for (int j = 0; j < m_nodeCount; j++) { m_graph[i][j] = m_graph[i + 1][j]; } for (int j = 0; j < m_nodeCount; j++) { m_graph[j][i] = m_graph[j][i ..
-
자료구조...77일지 2021. 4. 19. 11:03
ArrayGraph 삽입 메서드) 노드와 에지를 삽입하는 함수를 구현한다. ArrayGraph.cpp /// /// ArrayGraph에 노드를 추가한다. /// void ArrayGraph::InsertNode() { if (m_nodeCount to 인 간선을 추가한다. /// /// 시작 노드 /// 끝 노드 void ArrayGraph::InsertEdge(int from, int to) { if (from = m_nodeCount || to = m_nodeCount) { return; } m_graph[from][to]++; } mai..
-
자료구조...76일지 2021. 4. 13. 08:23
ArrayGraph 기본 구조) 생성자, 소멸자, 테스트용 출력 메서드를 구현한다. ArrayGraph.h #pragma once #include class ArrayGraph { public: #pragma region 생성자 ArrayGraph(size_t nodeCapacity = 5); ~ArrayGraph(); #pragma endregion #pragma region 속성 size_t NodeCapacity() { return m_nodeCapacity; } size_t NodeCount() { return m_nodeCount; } #pragma endregion #pragma region 메서드 void InsertNode(); void InsertEdge(int from, int to);..
-
자료구조...75일지 2021. 4. 10. 11:15
그래프 구현/인접행렬) 각각의 노드와 간선을 행렬을 통해 표현하는 방법으로 다음과 같이 각각의 노드가 순서대로 존재하는 것으로 가정하고 노드의 간선을 값으로 표현하는 방법이다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayGraph() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 ArrayGraph(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성 속성 NodeCapacity 노드의 최대 개수 NodeCount 현재 노드의 개수 메서드 InsertNode() 가능할 경우 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 엣지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 후 모든 데이터 위치 조정 RemoveEdge(int, i..
-
그래프(Graph)프로그래밍 기초/자료구조 2021. 4. 8. 11:15
그래프 그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다. 그래프의 구성요소 노드(또는 정점) 데이터 저장 및 표현 간선 데이터 간의 관계 표현 그래프의 종류 그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다. 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프 그래프의 표현) 그래프는 방향성에 따라 다르게 표현된..
-
자료구조...74일지 2021. 4. 7. 15:04
그래프 관련 용어) 연결 그래프(Connected Graph) 서로 떨어진 노드가 없는 그래프 단절 그래프(Disconnected Graph) 연결 되지 않은 노드가 있는 그래프 차수(Degree) 노드에 부속된 간선의 수 경로(Path) 특정 노드에서 다른 노드로 갈 수 있는 길을 나열한 것 경로 길이(Path Length) 경로를 구성하는 간선의 수 단순 경로(Simple Path) 경로가 모두 다른 노드로 구성되는 가장 단순한 경로 사이클(Cycle) 단순 경로 중 시작 점과 끝 점이 같은 경로 더보기 참고문헌 이지영.(2013.07.30).C로 배우는 쉬운 자료구조
-
자료구조...73일지 2021. 4. 5. 22:06
그래프의 종류) 그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다. 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프 그래프의 표현) 그래프는 방향성에 따라 다르게 표현된다. 가령 정점 A, B가 존재하는 완전 그래프 G에 대해 다음과 같이 표현한다. 무방향 그래프 V(G) = { A, B } E(G) = { (A, B) }..