[C언어 무방향 비가중치 그래프 알고리즘] 무방향 비가중치 그래프와 인접 행렬

💡 이번에는 무방향 비가중치 그래프를 구현 하는 법을 배워보았다.

문제

💡 무방향 비가중치 그래프를 구현하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int a[1001][1001];
int n, m;

int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        scanf("%d %d", &x, &y);

        // 서로 연결시킴
        a[x][y] = 1;
        a[y][x] = 1;
    }

    for (int i = 1; i <= n ; i++) {
        for (int j = 1 ; j <= n ; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\\n");
    }

    return 0;
}

설명

그래프란?

그래프란 사물을 정점(Vertex)와 간선(Edge)으로 나타내기 위한 도구이다.

1. 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
2. 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

무방향 비가중치 그래프와 인접 행렬이란?

• 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
• 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다.
• 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력 할 수 있다.
• 인접 행렬은 모든 연결 여부를 저장하여 𝑂(𝑉제곱)의 공간을 요구하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 𝑂(1)의 시간을 요구한다.

main 함수

int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        scanf("%d %d", &x, &y);

        // 서로 연결시킴
        a[x][y] = 1;
        a[y][x] = 1;
    }

    for (int i = 1; i <= n ; i++) {
        for (int j = 1 ; j <= n ; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\\n");
    }

    return 0;
}

• scanf("%d %d", &n, &m); 는 &n 노드의 개수, &m 간선의 개수이다.
• 아래의 코드가 왜 서로를 연결시키는지 모르겠지만 서로를 연결시킨다고 한다.
• a[x][y] = 1; a[y][x] = 1;
• 결과 값은 아래와 같다
• // 아래 값 입력 5 3 1 2 3 4 4 5 // 결과 값 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0

---

마치며..

역시나 백프로 이해는 되지 않으나 코드가 간결한 덕분에 어느정도 이해는 할 수 있었다.

이해 못한 부분은 나중에 또 찾아봐야지..