간선 삭제
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 8번째.
간선을 제거하는 것은 간선을 추가하는 것의 반대 작업입니다. 연결이 양방향으로 저장되므로 양쪽 모두를 취소해야 합니다. u의 이웃 목록에서 v를 제거하고, v의 이웃 목록에서 u를 제거하세요.
예외 상황에 주의하세요. 만약 u나 v가 그래프에 전혀 존재하지 않거나 간선이 추가된 적이 없다면, 메서드는 아무런 동작도 하지 않아야 합니다. 우리는 정점이 아니라 간선을 제거하는 것입니다. 정점 자체는 (남아 있는 다른 간선들과 함께) 그래프에 그대로 유지됩니다.
챌린지
쉬움Graph 클래스에 removeEdge 메서드를 추가하세요.
이 메서드는 두 개의 정수 u와 v를 인자로 받아 그 사이의 간선을 제거합니다:
- 만약
u가vertices에 있다면, 해당 이웃 리스트에서v를 제거합니다. - 만약
v가vertices에 있다면, 해당 이웃 리스트에서u를 제거합니다. - 정점이나 간선이 존재하지 않는 경우, 아무 작업도 수행하지 않습니다. 정점 자체는 그래프에 그대로 유지됩니다.
직접 해보기
#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)); }
if (strcmp(cmd, "addEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_addEdge(&g, atoi(a1), atoi(a2)); }
if (strcmp(cmd, "degree") == 0) {
char* arg = strtok(NULL, " \t");
if (arg) {
int k = atoi(arg);
int ki = Graph_indexOf(&g, k);
printf("%d\n", ki == -1 ? 0 : g.vertices[ki].n);
}
}
if (strcmp(cmd, "hasEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) printf("%s\n", Graph_hasEdge(&g, atoi(a1), atoi(a2)) ? "true" : "false"); }
if (strcmp(cmd, "neighbors") == 0) {
char* arg = strtok(NULL, " \t");
if (arg) {
int buf[MAX_NEIGHBORS];
int n = Graph_getNeighbors(&g, atoi(arg), buf);
qsort(buf, n, sizeof(int), _cmp_int);
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", buf[i]);
}
printf("\n");
}
}
if (strcmp(cmd, "removeEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_removeEdge(&g, atoi(a1), atoi(a2)); }
}
return 0;
}