무방향 그래프(undirected graph) G의 인접 행렬(adja… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

무방향 그래프(undirected graph) G의 인접 행렬(adjacent matrix) 표현을 C 언어의 2차원 배열을 이용하여 다음과 같이 구현했다. 그래프 G의 정점(vertex)이 0, 1, 2, 3, 4, 5, 6의 숫자로 표현될 때, 무방향 그래프 G의 그림으로 옳은 것은?
int G[7][7]={
                { 0, 1, 1, 0, 0, 0, 0 },
                { 1, 0, 1, 1, 0, 0, 0 },
                { 1, 1, 0, 1, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 0 },
                { 0, 0, 1, 1, 1, 0, 1 },
                { 0, 0, 0, 0, 0, 1, 0 }
        };

[그림]

[그림]

[그림]

[그림]

올바른 그림은 간선 0-1, 0-2, 1-2, 1-3, 2-3, 2-5, 3-5, 4-5, 5-6의 9개로 이루어진 그래프이다.
무방향 그래프의 인접 행렬은 대칭이므로 상삼각 부분의 1만 읽으면 간선 목록이 된다. 특히 정점 4는 5와만, 정점 6도 5와만 연결되며 0과 3은 연결되지 않는다.
0과 3이 연결되고 2-4, 3-6 간선이 있는 그림: 행렬의 0행 3열과 2행 4열이 0이므로 틀리다.
2와 4가 연결되고 2-5 간선이 없는 그림: 2행 5열이 1, 2행 4열이 0이므로 틀리다.
0-3, 3-4 간선이 있고 1-2, 2-5 간선이 없는 그림: 행렬과 여러 칸이 어긋난다.