[강의노트] 무방향 그래프 구현 - 2

그래프 구현 - 2

이번 포스트에서는 실제로 그래프를 구현해보는 작업을 할 것이다.

 

인접리스트를 이용한 상세구현(연결리스트 사용)

 

아래의 그림은 인접리스트와 인접행렬의 상세구현 방법을 보여주고 있다.

 

내가 실제로 구현해볼 그래프의 모습은 아래와 같다. 위의 그림을 참고해서 아래의 그래프를 구현해볼 것이다.

 

그림을 토대로 먼저 구조체 틀을 짜보자

 

간선에 대한 구조체 struct edge

 

1. 시작 정점(시점)에 대한 포인터

2. 끝 정점(종점)에 대한 포인터

3. 가중치 정보 (또는 간선이 담고있는 정보, 그림에선 a 또는 b)

4. 다음 간선을 가리키는 포인터

typedef struct edge {        int weight; // 가중치 정보        struct edge *next ; //다음 간선을 가리키는 포인터        VERTEX* start; //시점에 대한 포인터        VERTEX* end;  //종점에 대한 포인터 }EDGE;

 

정점에 대한 구조체 struct vertex

 

1. 정점이 가지고 있는 데이터 ( 그림에선 u, v ,w )

2. 다음 정점을 가리키는 포인터

3. incidence list의 헤드노드를 가리키는 포인터

typedef struct vertex {        int data; //정점 데이터        struct vertex* next;        struct edge* incidenceList; //부착간선리스트의 헤드노드를 가리키는 포인터 }VERTEX;

 

그래프에 대한 구조체 struct graph

 

1. 정점의 헤드를 가리키는 포인터

2. 정점의 수

typedef struct graph {        int n; //정점의 수        VERTEX vertices; }GraphType;

 

1. 그래프 생성

 

이제 데이터타입을 정의했으니 그래프를 생성해보자.

메인에서 그래프를 생성해준 후 초기화 함수 init을 통해 그래프를 초기화해준다.

 

초기화되고 나면, 생성한 그래프 g의 정점의 개수는 0개이고 당연히 정점을 가리키는 노드는 NULL로 초기화 되어있다.

 

2. 그래프에 정점 추가 insert_vertex

 

위의 그래프의 정점은 총 6개로 1, 2, 3, 4, 5, 6이다 

이 정점들의 헤드는 GraphType 구조체의 vertices 라는 포인터가 가리키게 된다.

아래의 그림처럼 정점들은 연결리스트 형태로 관리해야한다.

즉 insert_vertex에서는 호출마다 연결리스트의 제일 뒤에 새로운 노드를 추가하는 형태로 구현하면 된다.

 

예시 ( g는 그래프)

insert_vertex(g,u)

insert_vertex(g,v)

insert_vertex(g,w)

결과

u -> v -> w

 

아래와 같이 호출해서 1,2,3,4,5,6 정점을 그래프에 추가한다.

insert_vertex에서는 정점을 생성하고 초기화한뒤 정점들의 연결리스트 제일 뒤에 붙여주면 된다.

이 작업은 연결리스트에 삽입하는 익숙한 과정이므로 어렵지 않다. 

3. 그래프에 간선 추가 insert_edge

각 정점을 잇는 간선을 추가할 차례이다. 간선이 가지는 정보를 다시 한번 상기해보자.

 

1. 시작 정점(시점)에 대한 포인터

2. 끝 정점(종점)에 대한 포인터

3. 가중치 정보 (또는 간선이 담고있는 정보, 그림에선 a 또는 b)

4. 다음 간선을 가리키는 포인터

즉 간선의 생성은 아래와 같이 4개 정보를 저장해준다.

start는 시점을 가리키고, end는 종점을 가리킨다.

 

정점을 추가했던 것 처럼, 간선들도 추가해주어야하는데 그림을 한번 다시 살펴보자.

간선 a를 삽입하는 과정이라 생각해보자. 간선 a의 시점은 u , 종점은 v이다.

그리고 간선 a의 시점 u의 부착간선리스트(incidence list)가 다시 간선 a를 가리키고 있다.

 

생성과정에서 시점,종점,가중치정보는 추가되었기때문에 간선 추가 과정에서 해야할일은

incidence list를 생성하는 일과 간선의 next link를 연결하는 일이 남았다.

 

각각을 분리해서 생각해보자.

먼저 incidence list를 생성하는 것을 고려해보자. 시점에 해당하는 정점 start의 부착간선 리스트를

Edge head를 선언해서 지정해준다. 즉 처음 선언이라면 head 노드는 비어있을 것이다.

위의 그림에서는 각 간선의 시점에 대한 incidence list의 헤드노드를 비워두었지만, 나는 비우지않고 바로 사용할 것이다.

 

여기까지의 내용을 실제 구현하고자 하는 예시에 적용해서 다시 이해해보자. (어려우므로 차근차근)

위의 그림에서 우리는 아직 정점만 추가했으므로, 간선이 없고 정점만 있는 상황이라 가정해보자.

여기서 처음으로 정점 1,2를 끝점으로 하고 가중치 1을 가지는 간선을 추가하려고 한다.

 

먼저 간선이 생성되는 과정은 다음과 같다.

새로 추가하고자 하는 간선 edge 생성 ( EDGE *edge = (EDGE*)malloc(sizeof(EDGE)) ) 1. edge의 시점 : 정점1 2. edge의 종점 : 장점2 3. edge의 weight : 1 4. edge의 next : NULL

이제 간선추가과정에서는 아까도 말했다싶이, incidence list를 생성하는 작업과 간선의 next link를 연결하는 작업 두가지를

진행해야한다.

incidence list 생성 ( EDGE *head = start ->incidencelist) 시점 start에 대한 incidence list의 헤드를 가리키는 포인터를 생성한다. 현재 간선이 처음 삽입되는 과정을 예시로 들었으므로 시점1에 대한 incidence list의 head는 비어있을 것이다. 따라서 head가 NULL 이라면 head는 새로 삽입한 간선을 가리키게 한다.

위의 과정을 코드로 나타낸 것이 아까 설명한 코드이다. 

그럼 그 다음으로 그림1에서 정점 1,3을 끝점으로하고 가중치 1인 간선이 추가된다면 어떻게 될까?

마찬가지로 간선의 정보를 담은 간선을 생성하고

새로 추가하고자 하는 간선 edge 생성 ( EDGE *edge = (EDGE*)malloc(sizeof(EDGE)) ) 1. edge의 시점 : 정점1 2. edge의 종점 : 장점3 3. edge의 weight : 3 4. edge의 next : NULL

 

incidence list를 생성하는 작업과 간선의 next link를 연결하는 작업 두가지를 진행해야한다.

incidence list 생성 ( EDGE *head = start ->incidencelist) 시점 start에 대한 incidence list의 헤드를 가리키는 포인터를 생성한다. 이미 시점1에 대한 부착간선이 있으므로 head는 간선(1,2) 를 가리키고 있을 것이다. 이때 간선을 어떻게 연결할지 선택을 해야하는데 이번 구현에서는 간선의 종점을 기준으로 오름차순으로 구현하겠다. 간선(1,3)의 종점은 3이고 , 이전에 삽입된 간선 (1,2)의 종점은 2이다. 따라서 이 경우는 부착간선 연결리스트의 제일 뒤에 넣으면 된다. 만약 위의 상황이 아니라 간선(1,2) , 간선(1,4)가 존재하는 상황에서 간선 (1,3)이 추가된다면 간선(1,3)는 간선(1,4) 앞에 넣으면 된다.

위의 작업을 코드로 나타내면 다음과 같다.

아래의 코드는 두번째 시행일 경우 while문에 들어가지않고 바로 빠져나오는 case를 위한 것이다.

 

이제 간선을 추가하는 메소드를 메인에서 호출해서 그래프에 간선을 추가해보자.

 

4. 그래프 출력하기

정점의 번호를 입력받고, 그 정점에 대한 인접 정점 리스트를 출력하는 함수이다.

인접 정점 번호와 가중치 순으로 출력한다.

void adjList(GraphType* g, int number) { //number 노드의 인접노드 data와 가중치출력 //출력은 오름차순으로 ->> (노드1 data, 가중치) , ... , (노드n data, 가중치) // 1. 먼저 그래프에 해당 number의 노드가 있는지 찾는다. // 2. 해당 노드의 인접리스트를 통해 인접노드와 가중치를 출력한다.       VERTEX* vertex = g->vertices; //정점 리스트의 헤드노드       EDGE* edge = NULL;       while (1) {       //다 돌아도 없으면 -1 출력             if (vertex == NULL) {                 printf("-1\n");                 return;             }             edge = vertex->incidenceList;             if (vertex->data == number) {             //출력하고자하는 노드를 찾았다면             //해당노드의 인접노드와 가중치정보 출력             //이미 오름차순으로 저장했으므로 차례대로 출력하면 됨             printf("[%d번 노드에 대한 인접정점 정보] ",number);             while (edge != NULL) {                   printf("노드: %d 가중치: %d\n", edge->end->data, edge->weight);//인접노드는 종점의 data                   edge = edge->next;             }             printf("\n");             return;       }       vertex = vertex->next;    }    printf("\n"); }

 

 

 

다음 포스트에서는 가중치를 수정하고 제거 하는 함수를 추가해보겠다.