[자료구조] 그래프 (Graph)

그래프 (Graph) 란?

• 그래프는 정점(vertex)과 간선(edge)로 이루어진 자료구조

• 트리 (Tree) 와 무슨 차이가 있냐고 생각할 수 있는데,
  그래프에 경우에는 트리와 다르게 정점마다 간선이 없을 수도 있고 부모 자식개념이 존재하지 않는 등 차이점이 존재한다.
• 지하철 노선도 등의 최단경로를 찾거나 sns에서는 공통된 친구를 찾는 등에 활용된다.

장단점

장점

• 복잡한 관계를 모델링할 수 있음 (소셜 네트워크, 경로 탐색 등)
• 다양한 알고리즘을 통해 최단 경로, 연결성 등을 찾을 수 있음.

단점

• 구현과 연산이 복잡하고 메모리 사용이 큼.
• 순환이 발생할 경우 처리가 어려울 수 있음.

구현

<vector>를 사용한 구현

#include <iostream>
#include <vector>

class Graph
{
private:
	int V;
	std::vector<std::vector<int> > adjMatrix;
public:
	Graph(const int& n) {
		this->V = n;
		adjMatrix.resize(V, std::vector<int>(V, 0));
	}
	~Graph() {};

	void addEdge(int u, int v) {
		adjMatrix[u][v] = 1; // 단방향
	}

	void printGraph() {
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				std::cout << adjMatrix[i][j] << " ";
			}
			std::cout << std::endl;
		}
	}
};

int main() {
    Graph g(5);  // 5개의 정점을 가진 그래프 생성
    g.addEdge(0, 1);  // 0 -> 1
    g.addEdge(1, 2);  // 1 -> 2
    g.addEdge(2, 3);  // 2 -> 3
    g.addEdge(3, 4);  // 3 -> 4

    g.printGraph();
    return 0;
}

• 그래프 (graph) 에 경우에는 종류에 따라 방향 그래프 (Directed Graph), 비방향 그래프 (Undirected Graph) 등 다양하게 존재한다.
• 다익스트라 알고리즘 등 노드 사이의 가장 짧은 경로를 찾는경우에도 활용된다.

참고자료

https://80000coding.oopy.io/125156cf-79bb-48da-82ae-1f2ee7896bb8

https://www.geeksforgeeks.org/applications-of-graph-data-structure/