개념

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

그래프를 구현하는 방법중 하나이다. 연결리스트를 이용한다.

Python

def input_adjlist(filename):
    with open(filename, 'r') as file:
        node, edge = map(int, file.readline().split())
        adj = [[] for _ in range(node)]
        for line in file:
            a, b = map(int, line.split())
            adj[a].append(b)
            adj[b].append(a)
        return adj
    print("FILE NOT FOUND")
    exit()

graph = input_adjlist("graph_sample.txt")
print("graph = ")

for i in range(len(graph)):
    print("\\t{} -> {}".format(i, graph[i]))

graph =
        0 -> [3]
        1 -> [2, 3]
        2 -> [1]
        3 -> [1, 0]
        4 -> [5]
        5 -> [4]
        6 -> []

C

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

typedef struct _node {
    int key;
    int weight;
    struct _node* next;
} node;

node** input_adjlist(char* filename, int* vertex, int* edge) {
    FILE* fp = fopen(filename, "rt");
    if (!fp) {
        printf(" -- FILE NOT FOUND --\\n");
        return NULL;
    }
    fscanf(fp, "%d %d", vertex, edge);
    int i, a, b;
    node** adj = (node**)calloc(*vertex, sizeof(node*));

    node *t, *k;
    for (i = 0; i < *edge; i++) {
        fscanf(fp, "%d %d", &a, &b);

        // undirected graph라고 가정
        t = malloc(sizeof(node));
        t->key = b;
        t->next = adj[a];
        adj[a] = t;

        k = malloc(sizeof(node));
        k->key = a;
        k->next = adj[b];
        adj[b] = k;
				// ------------------------
    }
    return adj;
}

int main() {
    int i, vertex, edge;
    node* t;
    node** graph = input_adjlist("graph_sample.txt", &vertex, &edge);

    // Print Graph
    printf(" Graph = \\n");
    for (i = 0; i < vertex; i++) {
        printf(" (%d) ", i);
        t = graph[i];
        while (t) {
            printf("-> (%d) ", t->key);
            t = t->next;
        }
        printf("\\n");
    }

    return 0;
}

Graph = 
 (0) -> (3)
 (1) -> (3) -> (2)
 (2) -> (1)
 (3) -> (0) -> (1)
 (4) -> (5)
 (5) -> (4)
 (6)

C++

Python에서 append를 사용한것 처럼 C++에서는 vector의 push_back을 사용하면 된다.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int>* input_adjlist(string filename, int& vertex, int& edge) {
    ifstream fp(filename);
    if (fp.fail()) {
        cerr << " -- FILE NOT FOUND -- \\n";
        exit(-1);
    }
    fp >> vertex >> edge;
    vector<int>* adj = new vector<int>[vertex];
    int a, b;
    while (!fp.eof()) {
        fp >> a >> b;
        // undirected 일때
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    return adj;
}

int main() {
    string filename = "graph_sample.txt";
    int vertex, edge;
    vector<int>* graph = input_adjlist(filename, vertex, edge);
    vector<int>::iterator it;
    cout << "graph = \\n";
    for (int i = 0; i < vertex; i++) {
        cout << "\\t " << i;
        for (it = graph[i].begin(); it != graph[i].end(); it++) {
            cout << " -> " << *it;
        }
        cout << '\\n';
    }
}

graph = 
         0 -> 3
         1 -> 2 -> 3
         2 -> 1
         3 -> 1 -> 0
         4 -> 5
         5 -> 4
         6

Back_to_top