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

 

그래프 (Graph)

그래프는 정점(Vertex)과 간선(Edge)로 이루어진 자료구조로, 정점간의 연결관계를 나타냅니다.

• 정점(Vertex) : 데이터를 표현하는데 사용한다.
• 간선(Edge) : 두 정점을 연결하며, 관계를 나타낸다.

 

특징 및 종류

• 네트워크 모델
• 2개 이상의 경로가 가능하다.
• 부모-자식 관계 / 루트 노드 개념이 없다
• 순환 / 비순환  그래프
  • 순환(Cycle) : 동일한 정점에서 시작하여 다시 그 정점으로 돌아오는 경로. 순환이 있는 그래프
  • 비순환(Acyclic) : 그래프 내에 순환이 없는 그래프
• 방향 / 무방향 그래프
  • 방향 그래프 (Directed Graph) : 간선이 방향성을 가지고 있는 그래프
  • 무방향 그래프 (Undirected Graph) : 간선간의 방향이 없는 그래프로 서로 모두 이용 가능한 상태
• 가중치 그래프
  
  • 가중치 (Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
• 연결 / 비연결 그래프
  • 연결 (Connected Graph) : 무방향 그래프에 있는 모든 정점에 대해서 경로가 존재하는 그래프
  • 비연결 (DisConnected Graph) : 무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 경우
• 완전 그래프
  • 완전(Complete Graph) : 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

 

 

행렬 / 리스트 표현 방식 - https://howtolivelikehuman.tistory.com/75

인접 리스트 

• 각 정점마다 연결된 정점들을 리스트로 저장하는 방식
• 메모리 사용량 O(V + E)이며, 인접 행렬보다 메모리 사용이 효율적이다.
• 그래프 내의 적은 숫자의 간선을 가지는 그래프(희소 그래프)인 경우에 사용하기 적합하다.
• 인접 노드를 빠르게 알 수 있지만, 연결 여부확인은 모든 노드를 탐색해야한다.

 

enum Vertex { A, B, C, D, E, F };

class Graph
{
private:
	int vertices;								             
	std::vector<std::vector<Vertex>> adjList;
public:
	void addEdge(Vertex u, Vertex v)
	{
		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}
};

int main() {
	graph.addEdge(A, B);
	graph.addEdge(B, C);
	graph.addEdge(B, D);
	graph.addEdge(C, E);
	graph.addEdge(D, F);
}

 

 

인접 행렬

• 정점간의 연결 여부를 2D 행렬(2차원 배열)로 표현하는 방식
• 메모리 사용량은 O(V^2)이며, 인접 리스트보다 상대적으로 메모리를 더 많이 사용한다.
• 노드간의 연결 정보를 바로 알 수 있으며, 구현이 쉽다 (탐색 속도 O(1))
• 간선의 연결 여부는 빠르게 알 수 있지만, 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 순회해야한다.
• 간선이 많이 존재하는 그래프(밀집 그래프) 형태에 사용하기 적합하다.

class arrGraph
{
private:
	int vertices;
	std::vector<std::vector<int>> adjMatrix;

public:
	void addEdge(int u, int v)
	{
		adjMatrix[u][v] = 1;
		adjMatrix[v][u] = 1;
	}
};

int main() {
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(1, 3);
	graph.addEdge(2, 4);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
  
	return 0;
}