그래프의 종류와 인접, 행렬 리스트

그래프

그래프 G = (V,E) 이다.

 V : 정점의 집합을 의미하고 E : 간선의 집합을 의미한다. 

2차원 배열을 이용하여 인접 행렬이나 연결 리스트 형태의 인접 리스트로 표현이 가능하다. 여러 가지 종류로 나뉘기도 하는데

크게 무방향 그래프 , 방향 그래프로 나뉜다. 변이 방향성을 띠지 않는 그래프를 무뱡향 , 방향성을 띠는 그래프를 방향 그래프라고 함.

방향 그래프는 보통 그림 보면 화살표 있음. 

그래프의 종류

인접 - 간선 v,w 가 e(g)에 속한 간선 > 점점 v와 정점 w는 인접

부속 - v,w가 인접해 있을 떄, 간선v, w : 정점,v, w에 부속된 것

단순 경로 - 경로상에 있는 정점들 중에서 첫 번째 정점과 마지막 정점을 제외한 모든 정점들이 서로 다를때

사이클 - 첫 번째 정점과 마지막 정점이 같은 단순 경로.

차수 - 임의의 정점에 부속된 간선들의 수 (자식들 )

진입 차수 - 방향 그래프 g에서 임의의 정점v가 머리가 되는 간선들의 개수 (내가 받는 방향 )

진출 차수 - 방향 그래프 g에서 임의의 정점 v가 꼬리가 되는 간선의 개수 (내가 가는 방향 )

연결 그래프 - 그래프 g에서 그래프의 속한 모든 정점이 연결되어 있어서 vi, vj의 모든 쌍에 대하여 경로가 존재하는 그래프.

단절 그래프 - 연결 그래프가 아닌 그래프

인접 행렬 

정점 집합 V(G)={v1,v2,...,Vn) 인 그래프 G=(V(G),E(g))의 인접 행렬은 그래프를 구성하는 각 정점들 각의 인접 여부를 N * N 의

2차원 배열로 표현한 것이다. 인접 행렬은 쉬움. 두 꼭짓점을 연결한 선이 변인데 이것이 연결되어 있으면 1 아니면 0 이다.

그림은 그릴 줄 몰라서 패스한다. 그리고 문제점이 있는데 인접 행렬로는 n(n-1)개의 edge를 표현할 수 있다. 그러나 실제로

그래프 내의 edge 수는 이보다 훨씬 적기 때문에 대부분의 행렬 원소는 0의 값을 가진다. 따라서 완전 그래프철럼 edge가 많은

경우를 제외하고는 상당량의 기억장소가 낭비 되는 문제점이 있다. 이걸 해결하기 위해 인접 리스트 사용함.

Admatrix(int n, int m, int a[][]){
    int u, v, i, j;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            a[i][j]=0;
    for(i=1;<=m;i++){
        scanf("%d%d",&u,&v);
        a[u][v]=1;
        a[u][v]=1;
    }
}

인접 리스트

연결 리스트를 사용해서 그래프의 구조를 표현하는 건데 각 정점에 인접한 정점들을 각각 한 노드에 보관해서 1개의 연결 리스트

를 구성하여 각 리스트에 대한 포인터를 1차원 배열로 저장한 구조다. 표현법은 다음과 같다.

1. 그래프 포인터를 사용해서 인접 리스트로 표현. 임의의 정점 u를 중심으로 하여 정점u에 인접한 정점들은 1개의 연결 리스트

로 표현됨. 

2. G는 n개의 연결 리스트로 표현.

3. G의 간선들이 비용을 가지는 경우 연결 리스트상의 각 노드에 비용을 저장할 영역을 할당하면 됨. 이때 각 연결 리스트의 첫

번째 노드를 지시하는 포인터 배열이 추가로 필요.

장단점

장점 : 인접 리스트는 연결된 vertex들만 리스트로 관리하기 때문에 인접 행렬을 사용하능 경우처럼 비연결 vertex를 표현

하기 위해 기억장소를 낭비 안함.

단점 : 하나의 연결을 표시하기 위해 vertex 정보뿐 아니라 링크 정보까지 사용하므로 edge의 수가 상대적으로 많은 경우

인접 행렬을 사용할 때보다 기억장소의 낭비가 심해짐.

     그래프                                       인접 리스트                                          인접 행렬

역인접 리스트

방향 그래프에서 각 정점에 대한 그 정점으로 돌아오는 연결선과 인접한 정점들로 구성된 것을 역인접 리스트라 함.

이건 임의의 정점의 내차를 쉽게 알 수있음.

인접 다중 리스트

무방향 그래프의 인접 리스트 표현에서 각 연결선Vi,Vj는 2개로 나타내야 하는데. 즉Vi와 Vj는 리스트가 각각 표현되어야 해서

기억장소의 활용면에서 비효율적이다. 인접 다중 리스트는 인접 리스트에서 두 번 표현되는 연결선에 대해 1개의 노드에

저장하여 연결 리스트를 구성해 인접 리스트의 비효율적인 기억장소 활용 문제를 해결한 구조이다.

다중 인접 리스트