[알고리즘] 그래프(Graph) 구현

그래프의 구현

 

1. 인접 행렬을 이용한 구현 : O(V * V)
2. 인접 리스트를 이용한 구현 : O(V+E)

* 적은 간선을 가질 경우(Sparse Graph) 인접 리스트가 더 효율적이다.

 

#include <iostream>
#include <vector>
#include <tuple>
#define SIZE 500

using namespace std;

int main() {
	int vertexN, edgeN; // 정점의 갯수, 간선의 갯수
	cin >> vertexN >> edgeN;
	vector<tuple<int, int, int>> edge(edgeN);

	// 간선의 정보를 저장
	for (int i = 0; i < edgeN; i++) {
		int a, b, w; // a -> b 가중치 : w
		scanf("%d %d %d", &a, &b, &w);
		edge.push_back(make_tuple(a, b, w));
	}

	// 행렬
	int graphMatrix[SIZE + 1][SIZE + 1];
	for (auto i : edge) {
		int v1 = get<0>(i); // a
		int v2 = get<1>(i); // b
		int w = get<2>(i); // w

		// 양방향 기록. 단방향의 경우 한 줄만 작성
		graphMatrix[v1][v2] = w;
		graphMatrix[v2][v1] = w;
	}

	// 리스트
	vector<pair<int, int>> graphList[SIZE + 1];
	for (auto i : edge) {
		int v1 = get<0>(i); // a
		int v2 = get<1>(i); // b
		int w = get<2>(i); // w

		// 양방향 기록. 단방향의 경우 한 줄만 작성
		graphList[v1].push_back(make_pair(v2, w));
		graphList[v2].push_back(make_pair(v1, w));
	}
}

 

참고 블로그 : https://coderkoo.tistory.com/11