그래프는 Vertex 구조체만 쓰기엔 아쉽다

A. 그래프를 Vertex 구조체로만 만들지 않는 이유

1. 그래프를 Vertex로 그려보자

그래프를 구현할 때 트리와 같이 노드를 나타내는 Vertex 구조체를 사용할 수 있음

 

a. 구현할 이미지

이 이미지를 구현할 예정

 

b. Vertex로 생성한 그래프

기본모습

 

트리랑 비슷하게 Vertex로 정점을 만들고

정점에서 다른 간선들에 대한 정보를 들고 있는 모습으로 생성

 

c. 간선 정보를 물어본다면

연결관계를 물어본다면 위와같은 모습이 될것

 

 

👉 그래프는 간선간의 데이터가 중요하기 때문에 위와 같이 관리한다면 더 많은 자원이 필요하게 됨

 

d. 간선 위주의 데이터 형식

그래프의 경우, 각 노드가 자신과 연결된 다른 노드들의 정보를 가지고

이들 간의 관계는 그래프 자료구조에 따라 다르게 표현하기 때문에

 

🌟 그래프를 구현할 때는 보통 Vertex 구조체를 사용하여 각 노드의 데이터를 표현하고

인접 리스트나 인접 행렬 등의 형태로 저장됨

 

e. 즉, 사용하지 않는다는 결론

1) 유연성과 다양성 

 

그래프는 트리와는 달리 순환 구조를 가질 수 있음.

따라서 그래프의 노드는 더 다양한 형태를 가질 수 있어야 함

! Vertex 구조체로 고정된 형태의 노드를 사용하는 것은 이러한 다양성을 제한함

 

그래프는 여러 가지 속성을 가질 수 있으며, 이러한 속성은 Vertex에만 국한되지 않을 수 있음

예를 들어, 간선의 가중치, 방향성 등도 고려되어야 함

 

2) 간선 중심 구조

 

그래프 자료구조에서는 보통 간선을 중심으로 구성.

각 노드는 간선들의 집합에 속하며, 간선들은 서로 다른 노드들을 연결

따라서, 간선을 중심으로 데이터 구조를 설계하는 것이 더 자연스럽고 효율적

 

3) 메모리 관리와 성능

 

대부분의 그래프 알고리즘은 간선들을 중심으로 작동

따라서, 노드를 구조체로 표현하는 것보다는 간선들을 관리하는 것이 메모리를 더 효율적으로 사용

특히 대규모 그래프에서는 간선 중심의 구조가 더 나은 성능을 제공

 

 

 

---

출처 :  https://chat.openai.com/ ,

https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버