8.2. 그래프 구현 코딩

문제1) 그래프 표현

[ 문제 1 ] (인접리스트 구현) 그림 1의 무방향 가중그래프를 인접리스트로 표현하고, 다음 명령어에 따라 그래프 정보를 출력하거나 그래프를 수정하는 프로그램을 작성하시오.

대화식 프로그램에 주어지는 명령어는 a, m, q 세 가지며 각 명령에 대해 다음과 같이 수행해야 한다.

a <node number> : <node number>를 가지는 node와 인접한 node와 그 노드까지의 간선 가중치를 모두 인쇄. 단, node number의 오름차순으로 인쇄하되, space 외의 구분자 없이 노드번호 가중치 노드번호 가중치 ... 형식으로 인쇄한다. 그래프에 정점 a가 존재하지 않으면 아무 것도 하지 않고 –1을 출력한다.

m a b w : 간선 (a, b)의 가중치를 w로 변경한다. 그러한 간선이 존재하지 않을 때는 가중치 w인 새로운 간선 (a, b)를 생성한다. w = 0이면 간선 (a, b)를 삭제한다. 그래프에 정점 a 혹은 b가 존재하지 않으면 아무 것도 하지 않고 –1을 출력한다.

q : 프로그램 종료

무방향 가중 그래프(인접리스트)

위 그림같은 무방향 가중 그래프를 구현할 것이다.

가장 먼저 기본적인 기능을 구현하기 위해, 가중치 없는 그래프를 구현해 볼 것이다.

노드 구조체

//노드 생성(간선 노드)
typedef struct Node{
	int vertex;
	struct Node* next;
}node;

간선을 나타내는 노드를 먼저 구현했다.

vertex: 해당 노드에서 도착하는 인접정점의 번호를 나타낸다.

• 위 그래프에선 1-2로 방향이 없지만, 구현은 1→2, 2→1로 구현할 것이다.

next: 다음 간선 노드를 가리킨다.

그래프 구조체

//그래프 생성
typedef struct graph{
	int V;	//vertex의 개수
	node** adj;
}graph;

그래프 자체를 나타내는 구조체

V: 그래프에 들어오는 정점의 개수를 나타낸다.

• 이후 그래프를 만들 때, 그래프의 정점 리스트를 동적할당 해줄 때 사용한다.

adj: 정점 리스트이다. 위에선 1~7까지 모든 정점을 배열에 넣어두는 방식으로 가리킨다.

즉, 구현 방식은

정점 배열이 있고, 정점 배열의 인덱스는 곧 정점 배열의 이름이다.

정점 배열의 한 노드가 간선 노드들을 가리키고, 간선 노드의 next와 vertex가 인접 정점들의 배열 인덱스를 가리킨다.

그래프 생성: graph* createGraph(int V)

//그래프 생성 함수
graph* createGraph(int V){
	graph* newGraph = (graph*)malloc(sizeof(graph));
	newGraph->V = V;
	newGraph->adj = (node**)malloc(sizeof(node*)* V+1);
	for(int i = 0; i<= V; i++){
		newGraph->adj[i] = NULL;
	}
	return newGraph;
}

1. 그래프 동적 할당
2. 그래프 크기 V 할당
3. adj(정점 배열) 동적 할당 (위 그래프에 의하면 1부터 시작하는 인덱스 > 간단하게 구현하기 위해 +1 해줌)
4. 반복문으로 각 배열 노드 초기화

노드 생성: void addEdge(graph* g, int u, int v)

void addEdge(graph* g, int u, int v){
	node* nodeV = createNode(v);
	node* nodeU = createNode(u);
	if(g->adj[u] == NULL){
		g->adj[u] = nodeV;
	}
	else{
		node *now = g->adj[u];
		node *prev = NULL;
		while(now != NULL && now->vertex < v){
			prev = now;
			now = now->next;
		}
		prev->next = nodeV;
		nodeV->next = now;
		if(g->adj[u] == now){
			g->adj[u] = nodeV;
		}
	}
	if(u == v){
		return;
	}
	if(g->adj[v] == NULL){
		g->adj[v] = nodeU;
	}
	else{
		node *now = g->adj[v];
		node *prev = NULL;
		while(now != NULL && now->vertex < u){
			prev = now;
			now = now->next;
		}
		prev->next = nodeU;
		nodeU->next = now;
		if(g->adj[v] == now){
			g->adj[v] = nodeU;
		}
	}
}

1. 노드 생성: 무방향이므로 한번에 두 번의 간선 생성(진출 진입)
2. 노드 삽입 위치 찾기: 들어가야할 노드를 log(n)의 시간복잡도로 찾는다. (구현 방식에 따라 우선순위 큐등으로 구현 가능)
3. 이후 삽입하는 방식으로 구현

main

int main(){
	graph* graph = createGraph(7);

	addEdge(graph, 1,2);
	addEdge(graph, 1,3);
	addEdge(graph, 1,4);
	addEdge(graph, 1,6);
	addEdge(graph, 2,3);
	addEdge(graph, 3,5);
	addEdge(graph, 5,5);
	addEdge(graph, 5,6);

	int n;
	scanf("%d", &n);
	node* now = graph->adj[n];
	while(now != NULL){
		printf(" %d", now->vertex);
		now = now->next;
		//인접노드 출력
	}	
	return 0;
}
// 1
//  2 3 4 6

위와 같이 삽입 후, 출력하면 결과가 위와 같이 나온다.

• 인접 정점이 vertex크기 순으로 정렬됨.

가중치 추가

가중치는 간단하게 입력 값에 가중치도 입력하게 만들고, 해당 가중치를 node에 넣어주는 방식으로 구현한다.

//노드 생성(간선 노드)
typedef struct Node{
	int vertex;
	struct Node* next;
	int weight;   //가중치 추가
}node;

node* createNode(int n,int w){
	node* newNode = (node*)malloc(sizeof(node));
	newNode->next = NULL;
	newNode->vertex = n;
	newNode->weight = w;   //가중치 업데이트
	return newNode;
}