(알고리즘 -3) 기본 자료구조 그래프

그래프

그래프는 도형으로 표현되는 비선형 자료구조로서, 연결할 객체를 나타내는 정점의 집합 V와 정점을 연결하는 간선의 집합 E로 구성되며 

G = (V, E)로 표시됩니다. 그래프는 전기회로 분석, 프로젝트 분석, 최단 경로 탐색등 여러 분야에 쓰입니다. 

 

위 그림을 보면 무방향 그래프와 방향 그래프가 있는걸 볼 수 있습니다. 이 둘의 차이는 정점 사이의 간선이 방향이 있냐 없냐 차이입니다. 

무방향 그래프를 보면 간선의 방향이 없고 방향그래프는 간선의 방향이 있는걸 볼 수 있습니다. 

 

그리고 무방향 그래프 G1과 무방향 그래프 G2를 보면 간선의 가중치가 있냐 없냐를 볼수가 있는데 가중치가 있는 그래프를 보고 가중 그래프 라고 합니다. 최단 경로를 예시로 들자면 가중치는 시간이나 가는 비용이 있습니다. G2는 트리도 됩니다.

트리는 그래프의 특수한 경우로 연결된 무사이클 무방향 그래프 입니다. 

 

 

 

그래프의 용어

인접,부수 : 두 정점 u v 사이에 간선이 있으면 정점 u와 v는 인접한다고 하며 해당 간선은 정점 u와 v에 부수되었다고 합니다.

 

부분 그래프  정점집합 g'이 정점집합 g의 부분집합이고 간선집합 g'이 간선집합 g의 부분집합일 경우 그래프 g'는 그래프 g의 부분 그래프라고 합니다. 

ex)

 

경로 :  그래프 G에서 정점 V1로 부터 정점 Vn까지의 경로로란 간선으로 연결된 중점의 순서리스트를 말하면 이때 경로에 존재하는 간선의 개수를 경로의 길이라고 합니다. 

 

차수 : 해당 정점에 부수된 간선의 수를 의미하며, 방향 그래프에서는 차수를 세분화하여 정점으로 들어오는 간서의 수를 진입 차수라고 하고 그 정점에서 나가는 간선의 수를 진출 차수 라고 합니다. 

 

단순 경로 : 한 경로상에서 처음과 마지막 정점을 제외한 모든 정점이 서로 다른 경로를 말합니다. 

 

사이클 : 처음과 마지막 정점이 같은 단순 경로를 말하며 특히 사이클이면서 경로의 길이가 1인 경로를 루프라고 합니다. 

 

연결 : 무방향 그래프 g에서 서로 다른 정점의 모든 쌍에 대해서 u에서 v까지의 경로가 있으면 그래프는 연결되었다고 합니다. 

방향 그래프의 경우에는 서로 다른 두 정점의 모든 쌍에 대해서 u에서 v로의 방향 경로와 v에서 u로의 방향 경로가 존재하면 그 방향 그래프는 강력 연결되었다고 합니다. 

 

그래프를 구현할때는 인접 행렬 또는 인접 리스트를 사용합니다. 

 

인접 행렬 A = (n x n)의 임의의 원소 A(i, j)는 다음과 같이 정의합니다. 여기서 n은 그래프 g의 정점의 개수를 의미합니다. 

 

  a(i j) = 1, 간선(i j)∈ E(G) 또는 <i,j> ∈ E(G)

             0, 간선이 존재하지 않는 경우 

 

가중 그래프의 경우에는 정점 i와 정점 j사이에 간선이 존재하는 경우 간선상에 존재하는 가중치를 A(i j)의 값으로 나타내고 간선이 없는 경우에는 무한대로 표현한다. A(i j)의 값은 0으로 정합니다. 

 

인접행렬 인접 리스트

 

한편 인접 리스트에서는 인접 행렬의 n개의 각 행들을 연결 리스트로 표현합니다. 즉 그래프 g의 각 정점에 대하여 한 개의 연결 리스트가 존재합니다. 각 노드에는 적어도 두 개의 필드, 즉 정점과 링크 필드가 있지만, 가중 그래프의 경우에는 각 노드에 가중치를 저장하기 위한 필드가 추가로 사용됩니다. 헤드 포인터 head [i]는 정점 i로부터 인접되어 있는 정점들을 나타내는 연결 리스트의 시작 주소를 갖습니다.