728x90
728x170
인접 행렬을 이용하여 그래프 구현하기
서론
인접 행렬(Adjacent Matrix)을 이용하여 그래프(Graph)를 구현해보자.
코드
#include <iostream>
#include <vector>
enum class city : int {
MOSCOW,
LONDON,
SEOUL,
SEATTLE,
DUBAI,
SYDNEY
};
std::ostream& operator<<(std::ostream& os, const city c) {
switch (c) {
case city::LONDON:
os << "런던";
return os;
case city::MOSCOW:
os << "모스크바";
return os;
case city::SEOUL:
os << "서울";
return os;
case city::SEATTLE:
os << "시애틀";
return os;
case city::DUBAI:
os << "두바이";
return os;
case city::SYDNEY:
os << "시드니";
return os;
default:
return os;
}
}
struct graph {
std::vector<std::vector<int>> data;
graph(int n) {
data.reserve(n);
std::vector<int> row(n);
std::fill(row.begin(), row.end(), -1);
for (int i = 0; i < n; i++) {
data.push_back(row);
}
}
void addEdge(const city c1, const city c2, int dis) {
std::cout << "에지 추가: " << c1 << "-" << c2 << "=" << dis << std::endl;
auto n1 = static_cast<int>(c1);
auto n2 = static_cast<int>(c2);
data[n1][n2] = dis;
data[n2][n1] = dis;
}
void removeEdge(const city c1, const city c2) {
std::cout << "에지 삭제: " << c1 << "-" << c2 << std::endl;
auto n1 = static_cast<int>(c1);
auto n2 = static_cast<int>(c2);
data[n1][n2] = -1;
data[n2][n1] = -1;
}
};
int main() {
graph g(6);
g.addEdge(city::LONDON, city::MOSCOW, 2500);
g.addEdge(city::LONDON, city::SEOUL, 9000);
g.addEdge(city::LONDON, city::DUBAI, 5500);
g.addEdge(city::SEOUL, city::MOSCOW, 6600);
g.addEdge(city::SEOUL, city::SEATTLE, 8000);
g.addEdge(city::SEOUL, city::DUBAI, 7000);
g.addEdge(city::SEOUL, city::SYDNEY, 8000);
g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
g.addEdge(city::DUBAI, city::SYDNEY, 1200);
g.addEdge(city::SEATTLE, city::LONDON, 8000);
g.removeEdge(city::SEATTLE, city::LONDON);
return 0;
}
결과 확인
에지 추가: 런던-모스크바=2500
에지 추가: 런던-서울=9000
에지 추가: 런던-두바이=5500
에지 추가: 서울-모스크바=6600
에지 추가: 서울-시애틀=8000
에지 추가: 서울-두바이=7000
에지 추가: 서울-시드니=8000
에지 추가: 시애틀-모스크바=8400
에지 추가: 시애틀-시드니=12000
에지 추가: 두바이-시드니=1200
에지 추가: 시애틀-런던=8000
에지 삭제: 시애틀-런던
728x90
그리드형(광고전용)
'Computer Science > Data Structure' 카테고리의 다른 글
[C++] 블룸 필터(Bloom Filter) (0) | 2021.05.28 |
---|---|
[C++] 뻐꾸기 해싱(Cuckoo Hashing) (0) | 2021.05.22 |
[C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현 (0) | 2021.05.20 |
[C++] 인접 리스트를 이용하여 그래프 구현하기 (0) | 2021.05.19 |
[C++] 이진 탐색 트리(Binary Search Tree) (0) | 2021.05.16 |
[C++] 트리 순회(Tree Traversal) (0) | 2021.05.15 |
[C] 탐색(Search) (0) | 2017.06.21 |
[C] 해싱(Hashing) (0) | 2017.06.20 |