간선 확인
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 6번째.
그래프에 물어볼 수 있는 가장 간단한 질문은 "이 두 정점이 연결되어 있는가?"입니다. 우리의 인접 리스트를 사용하면, 그 답은 한 번의 맵 조회와 한 번의 리스트 스캔으로 얻을 수 있습니다. u의 이웃을 조회하고 v가 그 리스트에 있는지 확인하면 됩니다.
만약 u가 그래프에 존재하지도 않는다면 스캔할 리스트가 없으므로 false를 반환합니다. addEdge가 양방향으로 연결을 설정했기 때문에 한쪽만 확인하면 됩니다. 만약 v가 u의 이웃에 있다면, 구조상 u도 v의 이웃에 있게 됩니다.
이제 코드를 작성해 보세요.
챌린지
쉬움Graph 클래스에 hasEdge 메서드를 추가하세요.
이 메서드는 두 개의 정수 u와 v를 인자로 받으며, 두 정점 사이에 간선이 있으면 true를, 그렇지 않으면 false를 반환합니다.
만약 u가 vertices에 존재하지 않으면 false를 반환하세요. 그렇지 않으면 v가 u의 이웃 리스트(neighbor list)에 포함되어 있는지 여부를 반환하세요.
직접 해보기
#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"); }
}
return 0;
}