개념

그래프 (자료 구조) - 위키백과, 우리 모두의 백과사전

인접행렬 - 위키백과, 우리 모두의 백과사전

그래프 자료구조는 크게 리스트와 행렬로 구현할 수 있다. 이 페이지에서는 행렬 중 인접행렬(Adjacency Matrix)로 그래프를 구현하는 것에 대해 다룬다.

Python

직접 입력할 떄

import sys

I = sys.stdin.readline

node, edge = map(int, I().split())
adj = [[0 for _ in range(node)] for _ in range(node)]

for _ in range(edge):
    src, dest = map(int, I().split())
    adj[src][dest] = 1
    adj[dest][src] = 1

print(*adj, sep='\\n')

5 1
1 2
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

txt파일로 가져올 때

def input_adjmatrix(filename):
    with open(filename, "r") as file:
        node, edge = map(int, file.readline().split())
        adj = [[0 for _ in range(node)] for _ in range(node)]
        for line in file:
            a, b = map(int, line.split())
            adj[a][b] = 1
            adj[b][a] = 1
        return adj

graph = input_adjmatrix("Graph Theory\\Adj Matrix\\graph_sample.txt")
print("adjmatrix : ", *graph, sep='\\n')

adjmatrix : 
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

C

txt파일로 파일로 입력받기

#include <stdio.h>
#include <stdlib.h>

int** input_adjmatrix(char* filename, int* vertex, int* edge) {
    FILE* fp = fopen(filename, "rt");
    if (!fp) {
        printf("-- FILE NOT FOUND --\\n");
        return NULL;
    }
    int i, a, b;
    fscanf(fp, "%d %d", vertex, edge);
    int** adj = (int**)calloc(*vertex, sizeof(int*));
    for (i = 0; i < *vertex; i++) {
        adj[i] = (int*)calloc(*vertex, sizeof(int));
    }
    for (i = 0; i < *edge; i++) {
        fscanf(fp, "%d %d", &a, &b);
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    return adj;
}

int main() {
    int v, e;
    int** graph = input_adjmatrix("graph_sample.txt", &v, &e);
    if (!graph) return 0;
    int i, j;
    for (i = 0; i < v; i++) {
        for (j = 0; j < v; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\\n");
    }
    return 0;
}

C++

C++파일입출력을 복습한다는 느낌으로 작성하였다.

C++ 파일입출력 간단히 정리

#include <cstring>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int** input_adjmatrix(string filename, int& vertex, int& edge) {
    ifstream fin(filename);
    if (fin.fail()) {
        cerr << "FILE NOT FOUND\\n";
        return nullptr;
    }
    fin >> vertex >> edge;
    int** adj = new int*[vertex];
    for (int i = 0; i < vertex; i++) {
        adj[i] = new int[vertex];
        memset(adj[i], 0, vertex * sizeof(int));
    }
    int a, b;
    while (!fin.eof()) {
        fin >> a >> b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    fin.close();
    return adj;
}

int main() {
    int vertex, edge;
    int** graph = input_adjmatrix("graph_sample.txt", vertex, edge);

    for (int i = 0; i < vertex; i++) {
        for (int j = 0; j < vertex; j++) {
            cout << graph[i][j] << ' ';
        }
        cout << '\\n';
    }
}