정점 추가
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 4번째.
정점(vertex)은 그래프의 단일 지점입니다. 정점을 추가한다는 것은 vertices 맵에 해당 키를 빈 이웃 리스트와 함께 등록하는 것을 의미합니다. 즉, 존재는 하지만 아직 연결은 없는 상태입니다.
키가 이미 맵에 있다면 아무것도 하지 않습니다. 누군가 addVertex를 두 번 호출했다고 해서 정점의 기존 이웃들을 지워버리고 싶지는 않기 때문입니다. 이러한 멱등성(idempotent) 있는 동작 덕분에 나중에 addEdge에서 이 메서드를 안전하게 호출할 수 있습니다.
이제 작성해 봅시다.
챌린지
쉬움Graph 클래스에 addVertex 메서드를 추가하세요.
이 메서드는 정수형 key를 인자로 받으며 다음을 수행합니다:
- 만약
key가vertices에 존재하지 않는다면, 빈 이웃 리스트와 함께 추가합니다. - 만약
key가 이미vertices에 존재한다면, 아무것도 하지 않습니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
static int _cmp_int(const void* a, const void* b) {
int ai = *(const int*)a, bi = *(const int*)b;
return (ai > bi) - (ai < bi);
}
int main() {
Graph g;
Graph_init(&g);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "verticesEmpty") == 0) { printf("%s\n", g.vertexCount == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Graph_indexOf(&g, atoi(arg)) != -1 ? "true" : "false"); }
if (strcmp(cmd, "addVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Graph_addVertex(&g, atoi(arg)); }
}
return 0;
}