[C++ Data Structure] 그래프(Graph)
그래프Permalink
그래프(Graph)는 노드(정점, Node, Vertex)와 간선(Edge)으로 구성된 비선형 자료구조입니다.
여러 개의 개체 간의 관계를 표현하는 데 사용됩니다.
네트워크, 경로 찾기, 소셜 네트워크 분석 등에 활용됩니다.
그래프를 탐색하는 대표적인 알고리즘은 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다.
그래프 종류Permalink
방향 그래프(Directed Graph / Digraph)Permalink
방향 그래프는 간선에 방향이 존재하는 그래프입니다.
무방향 그래프(Undirected Graph)Permalink
무방향 그래프는 간선에 방향이 없는 그래프입니다.
가중 그래프(Weighted Graph)Permalink
가중 그래프는 각 간선에 가중치(비용, 거리, 시간 등)가 부여된 그래프입니다.
비가중 그래프(Unweighted Graph)Permalink
비가중 그래프는 각 간선에 가중치가 없는 그래프입니다.
사이클 있는 그래프(Cyclic Graph) / 사이클 없는 그래프(Acyclic Graph)Permalink
사이클 있는 그래프는 노드를 순환하며 다시 방문할 수 있는 그래프 이며, 사이클 없는 그래프는 순환이 없는 그래프입니다.
표현 방법Permalink
인접 행렬(Adjacency Matrix)Permalink
인접 행렬는 2차원 배열(행렬)을 사용하여 그래프를 저장하는 방식입니다.
노드 수가 V개라면, V x V 크기의 행렬을 사용합니다.
A B C D
----------------
A | 0 1 0 1
B | 1 0 1 1
C | 0 1 0 1
D | 1 1 1 0
- 장점
- 간선이 존재하는지 여부를 O(1) 시간으로 빠르게 확인 가능합니다.
- 배열만으로 구현하기 때문에 구현이 단순합니다.
- 가중치 그래프에 쉽게 확장 가능합니다.
- 단점
- 메모리 사용량이 O(V2)로 메모리 사용량이 많아 희소 그래프(Sparse Graph)에는 비효율적입니다.
- V는 정점 개수입니다.
- 연결된 노드를 찾는 데 O(V) 시간복잡도를 가집니다.
- 메모리 사용량이 O(V2)로 메모리 사용량이 많아 희소 그래프(Sparse Graph)에는 비효율적입니다.
구현 예시
#include <iostream>
#include <vector>
class Graph
{
private:
std::vector<std::vector<int>> adjMatrix; // 인접 행렬
int vertices; // 정점 개수
public:
Graph(int v) : vertices(v), adjMatrix(v, std::vector<int>(v, 0)) {}
// 간선 추가 (비가중치 그래프)
void addEdge(int u, int v)
{
adjMatrix[u][v] = 1; // 방향 그래프
adjMatrix[v][u] = 1; // 무방향 그래프(방향 그래프를 구현하려면 해당 줄 제거)
}
// 간선 추가 (가중치 그래프)
void addEdge(int u, int v, int weight)
{
adjMatrix[u][v] = weight; // 방향 그래프
adjMatrix[v][u] = weight; // 무방향 그래프(방향 그래프를 구현하려면 해당 줄 제거)
}
// 그래프 출력
void printGraph()
{
for (int i = 0; i < vertices; i++)
{
for (int j = 0; j < vertices; j++)
{
std::cout << adjMatrix[i][j] << " ";
}
std::cout << std::endl;
}
}
};
int main() {
Graph g(5); // 5개의 정점을 가진 그래프 생성
// 간선 추가
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 인접 행렬 출력
g.printGraph();
}
인접 리스트(Adjacency List)Permalink
인접 리스트는 각 노드에 연결된 다른 노드들을 리스트(List) 형태로 저장하는 방식입니다.
- 장점
- 메모리 사용량이 O(V+E)로 효율적이므로, 희소 그래프(Sparse Graph)에 효율적입니다.
- 단점
- 특정 노드가 연결되어 있는지 확인하는 데 O(V)의 시간 복잡도를 가집니다.
구현 예시
#include <iostream>
#include <vector>
using namespace std;
class Graph
{
private:
vector<vector<int>> adjList; // 인접 리스트
int V; // 정점 개수
public:
Graph(int vertices)
{
V = vertices;
adjList.resize(V); // 정점 개수만큼 리스트 크기 설정
}
// 간선 추가 (비가중치 그래프)
void addEdge(int u, int v)
{
adjList[u].push_back(v); // 방향 그래프
adjList[v].push_back(u); // 무방향 그래프(방향 그래프를 구현하려면 해당 줄 제거)
}
// 간선 추가 (가중치 그래프)
void addEdge(int u, int v, int weight)
{
adjList[u][v] = weight; // 방향 그래프
adjList[v][u] = weight; // 무방향 그래프(방향 그래프를 구현하려면 해당 줄 제거)
}
// 인접 리스트 출력
void printGraph()
{
for (int i = 0; i < V; i++)
{
cout << i << ": ";
for (int neighbor : adjList[i])
{
cout << neighbor << " ";
}
cout << endl;
}
}
};
int main()
{
Graph g(5); // 정점 5개인 그래프 생성
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
}
댓글남기기