Graph

Input

4 5 //정점의 개수, 간선의 개수
2 3 //1번 간선의 정보, 2번 정점에서 3번 정점을 향하는 간선이 존재한다
1 2 //2번 간선의 정보, 1번 정점에서 2번 정점을 향하는 간선이 존재한다
1 4 
1 3
2 4

방법1

  • int map[5][5]를 선언하여 연결 정보 있을 시 map[from][to] 를 1로 체크하고 찾을땐 다 돌면서 찾는 방식
  • 메모리를 많이 사용하고 초기화에 시간이 걸림

방법2

  • single linked list 사용하는 방법
  • 1번 노드에 연결 된 2,3,4와 2번에 연결된 3,4를 각각 single linked list로 표시, 아래와 같은 연결 형태
0 : null
1 : 3 -> 4 -> 2 -> null
2 : 4-> 3-> null
3 : null
4 : null

Code

#include <iostream>
using namespace std;
#define MAXTABLE 1000
int idx = 0;

struct NODE {
    int value;
    NODE* prev;
}a[10000];

NODE* myalloc() {
    return &a[idx++];
}

NODE* table[MAXTABLE];

int main() {
    int T; cin >> T;
    for (int test_case = 0; test_case < T; ++test_case) {
        //init
        idx = 0;
        for (int i = 0; i < MAXTABLE; ++i)table[i] = nullptr;

        int N, L;//정점, 간선
        cin >> N >> L;

        //save graph
        for (int i = 0; i < L; ++i) {
            int from, to;
            cin >> from >> to;

            NODE* node = myalloc();
            node->value = to; //연결된 노드 저장
            node->prev = table[from];
            table[from] = node;

        }


        //search
        cout << "searching edge from 1 to " << endl;
        for (NODE* it = table[1]; it != NULL; it = it->prev) {
            cout << it->value << endl;
        }

    }
    return 0;
}
  • 연결리스트로 table[from]에 연결되는 정보(가령 table[1]에 연결된 3->4->2)는 노드1번에 연결된 애들이란 것이지, 3번다음 4번이 오고 4번에 2번이 연결되고 하는 것이 아니니 헷갈리지 말것.
  • 방향성이 없는 경우 table[from]=to, table[to]= from 도 저장하면 됨
  • 가중치가 있는 그래프의 경우 node 구조체에 weight를 추가하여 node->weight에 가중치 저장
  • 노드가 자연수가 아닌 경우 이전 Tree 게시물처럼 id값을 자연수로 변경
  • single linked list 특성 상 다양한 활용이 가능
Musicals, Travel, Photo, Coding