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

그래프(Graph)

---

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조입니다. 이게 무슨 말인지 솔직히 감이 잘 안오실겁니다. 그럼 그림으로 한 번 이해해볼까요?

그래프(Graph)

여기서 보시다 싶이 그래프는 2개의 구성요소로 존재합니다. 

• 정점(Vertex/Node):  그래프의 개별 요소를 나타냅니다.
  e.g. 사람, 도시, 컴퓨터 등이 될 수 있습니다. 
• 간선(Edge/Arc): 두 정점을 연결하는 선을 의미합니다. 
  이 간선은 정점 간의 관계나 연결성을 나타냅니다. 

그래프의 종류

1. 방향성과 무방향성
   • 무방향 그래프(Undirected Graph):
     간선에 방향성이 없어, 두 정점 간의 연결이 쌍방향입니다.
   • 방향 그래프(Directed Graph)
     간선에 방향성이 있어, 한 정점에서 다른 정점으로의 일방적인 연결을 나타냅니다. 
2. 가중치 유무
   • 가중치 그래프(Weghted Graph):
     각 간선에 비용, 거리, 시간 등 가중치가 부여됩니다. 
   • 비가중치 그래프(Unweighted Graph):
     간선에 별도의 가중치가 부여되고 않고 단순한 연결만 표현됩니다.
3. 단순성과 다중 간선
   • 단순 그래프(Simple Graph):
     자기 자신으로 간선(루프)이 없으며, 두 정점 사이에 한 개의 간선만 존재합니다. 
   • 다중 그래프(Multigraph):
     두 정점 사이에 여러 개의 간선이 존재할 수 있습니다. 
4. 순환성 여부
   
   • 순환 그래프(Cyclic Graph):
     사이클(순환)이 존재하는 그래프. 즉, 어떤 정점에서 시작해 여러 정점을 거쳐 다시 그 정점으로 돌아오는 경로가 있습니다. 
   • 비순환 그래프(Acylic Graph):
     사이클이 없는 그래프 → 방향 비순환 그래프(DAG, Directed Acyclic Graph):
     방향성이 있으면서 사이클이 없는 그래프
5. 특수한 구조의 그래프
   • 트리(Tree):
     사이클이 없고, 모든 정점이 연결된 그래프 → 이진 트리(Binary Tree), 균형 트리(Balanced Tree) 등 다양한 변형 존재
   • 포레스트(Forest):
     서로 연결된 트리들의 집합

방향 그래프(Directed Graph)

무방향 그래프(Undirected Graph)

 

그래프(Graph) VS 트리(Tree)

구분	그래프(Graph)	트리(Tree)
정의	노드와 그 노드를 연결하는 간선으로 구성된 일반적인 자료구조로, 다양한 형태의 연결 관계를 표현합니다.	계층적 구조를 가지며, 노드와 노드를 연결하는 간선으로 구성된 비순환 유향 그래프입니다.
방향성	방향성(Directed)과 무방향성(Undirected) 모두 가능합니다.	일반적으로 방향성(Directed)을 가집니다.
사이클 존재 여부	순환(Cyclic) 및 비순환(Acyclic) 구조 모두 가능합니다.	사이클(Cycle)이 존재하지 않는 비순환(Acyclic) 구조입니다.
루트 노드	루트 노드의 개념이 없으며, 임의의 노드간에 여러 경로가 존재할 수 있습니다.	하나의 루트 노드(Root Node)가 존재하며, 모든 노드는 루트에서 시작되는 유일한 경로를 가집나다.
부모-자식 관계	부모-자식 관계의 개념이 없습니다.	명확한 부모와 자식(Child) 관계가 있습니다.
간선의 수	간선의 수는 제한이 없으며, 노드 수와 관계없이 다양할 수 있습니다.	N개의 노드를 가진 트리는 항상 N-1개의 간선을 가집니다.
경로의 유일성	두 노드 간에 여러 경로가 존재할 수 있습니다.	두 노드 간의 경로가 유일합니다.
모델 구조	네트워크(Network) 모델을 표현합니다.	계층척(Hierarchical) 모델을 표현합니다.
순회 방법	너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등의 순회 방법이 사용됩니다.	전위(Pre-order), 중위(In-order), 후위(Post-order) 순회 방법이 있습니다.
실생활 예시	도로망, 소셜 네트워크, 전기 회로 등	조직도, 파일 시스템, 가계도 등

 

 

이산 수학에서 쓰는 그래프를 알고 싶다? -> https://blog.naver.com/kjh91207/223683567033

[이산수학] 8. 그래프