[ C로 구현하는 ] 그래프

그래프란?

정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G=(V, E) 이다.

 

그래프의 표현 방법

인접 행렬

다음과 같은 그래프를 행렬로 표현해보자

	0	1	2	3	4
0	0	1	0	0	1
1	1	0	1	1	1
2	0	1	0	1	0
3	0	1	1	0	1
4	1	1	0	1	0

이렇게 표현이 가능하다.

당연한 얘기지만 무방향성 그래프 (위와 같이 양방향 그래프)는 대각선을 기준으로 대칭을 이루고,

방향성 그래프는 대각선을 기준으로 오른쪽에 나타난다.

 

인접 리스트

정점	인접 정점
0	1, 4
1	0, 2, 3, 4
2	1, 3
3	1, 2, 4
4	0, 1, 3

이를 링크드 리스트로 구현할 수 있을 것처럼 보인다.

 

장단점

인접 행렬

- 정점 간의 인접 여부 확인 빠름

- 정점의 크기 X N^2만큼 커짐 (메모리 낭비)

 

인접 리스트

- 정점 간의 인접 여부 확인을 위해 순차 탐색 필수 (오래걸림)

- 메모리양을 줄일 수 있음

 

구현

typedef struct tagVertex {
	VElementType Data;
	int Visited;
	int Index;

	struct tagVertex* next;
	struct tagEdge* AdjacencyList;

}Vertex;

typedef struct tagEdge {
	int Weight;
	struct tagEdge* Next;
	Vertex* From;
	Vertex* Target;
}Edge;

typedef struct tegGraph {
	Vertex* Vertices;
	int VertexCount;
}Graph;

그래프 -> 정점(Vertex) 리스트 -> 간선(Edge) 리스트

 

삽입

void AddVertex(Graph* G, Vertex* V) {
	Vertex* vList = G->Vertices;

	if (vList == NULL)
		G->Vertices = V;
	else {
		while (vList->next != NULL)
			vList = vList->next;

		vList->next = V;
	}

	V->Index = G->VertexCount++;
}

그래프 객체의 정점 리스트를 순차탐색하여 끝 부분에 새로운 정점을 추가한다.

 

void AddEdge(Vertex* V, Edge* E) {
	if (V->AdjacencyList == NULL) {
		V->AdjacencyList = E;
	}
	else {
		Edge* AdjacencyList = V->AdjacencyList;
		//printf("v: %c\n", V->Data);
		while (AdjacencyList->Next != NULL) {
			//printf("%c\n", AdjacencyList->From->Data);
			AdjacencyList = AdjacencyList->Next;
		}
			
		AdjacencyList->Next = E;
	}
}

해당 정점의 간선 리스트를 가져오고, 순차탐색을 하여 끝에 추가한다.

 

https://github.com/mete0rfish/ThisIsDataStructure-Algorithm/tree/main/Chap09%20Graph