5 Graph 사용법

지난 글과 관련성이 있습니다.

역시 본인에게 잘 맞는 분만 참고하시기 바랍니다.

같은 코드만 계속 알려드려서, Graph 관련 내용은 안쓸까 생각했는데요.

Graph 에 관련해서 질문하신 분이 아래에 계서서 한번 써 보겠습니다.

===============================================

이번에는 Graph 를 사용하는 방법입니다.

아래와 같은 그래프 데이터 구조로 나타내는 방법입니다.

(아래 데이터는 장홍준님의 이전글에서 차용해왔습니다. 감사합니다.)

1. 배열을 이용하는 방법

 

    int map[5][5] 를 선언하고

    - 1 에서 출발하는 간선은  2, 3, 4 가 있으므로 map[1][2], map[1][3], map[1][4] 을 1로 체크

    - 2 에서 출발하는 간선은  3, 4 가 있으므로  map[2][3], map[2][4] 에 1로 체크

    하는 경우 아래와 같은 배열이 만들어 집니다.

   

	0	1	2	3	4
0	0	0	0	0	0
1	0	0	1	1	1
2	0	0	0	1	1
3	0	0	0	0	0
4	0	0	0	0	0

 코드로 표현하면 아래와 같습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int node, edge, from, to;       cin >> node >> edge;           for(int h = 0; h<=node; h++)  //map 배열 초기화     for(int w = 0; w<=node; w++)       map[h][w] = 0;           for(int e = 0; e<edge; e++)   {         cin >> from >> to;     map[from][to] = 1;   //간선 연결정보를 map에 표시(가중치가 있는 경우 1대신 가중치로)   }

각 노드에서 연결된 노드을 찾으려면 배열을 검색하면 되므로 간편하게 사용할 수 있습니다.

1 2 3 4 5 6 7 8

//1번에 연결된 노드 검색.   cout << "Searching edge from 1 to  ";       for(int m = 0; m<=node; m++)   {     if(map[1][m] != 0)  cout << m << " , ";   }

* 간선의 가중치가 있으면, 1대신 가중치를 저장하면 됩니다.

* 방향성이 없는 graph 의 경우, map[from][to] = map[to][from] = 1 로 저장합니다.

* 크기가 큰 경우 메모리를 많이 사용하고, 초기화에 시간이 걸립니다.

2.  싱글 링크드 리스트를 이용하는 방법

연결된 노드 정보를 Single linked list 배열에 저장하는 방식입니다.

(parent 정보가 없는 Tree 라고 생각하시면 됩니다)

1번에 연결된 노드는 2, 3, 4 와   2번에 연결된 노드는 3,4  를 각각 Single linked list 로 표시합니다.

데이터를 모두 입력하고나면  single linked list의 배열은 아래와 같이 구성 됩니다.

0 :  null 1 :  3 -> 4 -> 2 -> null 2 :  4 -> 3 -> null 3 :  null 4 :  null

앞선 게시물에서 계속 사용했던 Single linked list 코드로 작성하면

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

node* n;       for(int e = 0; e < edge; e++)   {     cin >> from >> to;         n = myalloc();     n->v = to;    //연결된 노드를 저장         n->prev = table[from];    //from 의 Single linked list 에 저장     table[from] = n;       }

너무 같은 코드를 계속 우려먹고 있는거 같습니다. ^^.

각 노드에 연결된 노드를 검색할 때는  tabl[] 의 Single linked list 를 검색하시면 됩니다.

1번 노드에 연결된 노드를 찾는 경우, Table[1] 을 확인하면 됩니다.

1 2 3 4 5 6

//1번에 연결된 노드 검색.   cout << "Searching edge from 1 to  ";   for (node* iter = table[1]; iter != nullptr; iter = iter->prev)  // table[1] 의 Single linked list 에서 검색   {     cout << iter->v << " , ";   }

* 초기화시에는 myalloc에서 사용하는 heap_cnt 와 Single linked list 가 저장되는 table[] 을 초기화 주면 됩니다.

* 방향성이 없는 경우 table[from] 에 to를 저장하고, table[to]에 from을 저장하면 됩니다.

* 가중치가 있는  Graph의 경우 node 구조체에 (value)를 추가하고, n->value 에 가중치를 저장하면 됩니다.

* 노드가 자연수가 아닌경우에는 이전 Tree 게시물을 참조해서 자연수로 변경하시면 됩니다.

* 같은 포멧의 코드를 계속 사용해서

* 실수할 가능성을 줄여 줍니다.

* 코딩 속도를 빠르게 해 줍니다.

** 동일한 포멧을 사용하는 코드로는 마지막입니다만,

** Single linked list 특성상 다양한 활용이 가능할 것 같습니다.

** 많은 추천 부탁드려요

input.txt

4 5 2 3 1 2 1 4 1 3 2 4

main_array.txt

#include <iostream> using namespace std; int map[5][5]; int main(void) { freopen("input.txt", "r", stdin); int node, edge, from, to; cin >> node >> edge; for (int h = 0; h <= node; h++) //map 배열 초기화 for (int w = 0; w <= node; w++) map[h][w] = 0; for (int e = 0; e < edge; e++) { cin >> from >> to; map[from][to] = 1; //간선 연결정보를 map에 표시(가중치가 있는 경우 1대신 가중치로) } //모든 map 정보를 표시. cout << "Print all amp info " << endl; for (int h = 0; h <= node; h++) { for (int w = 0; w <= node; w++) cout << map[h][w] << " "; cout << endl; } cout << endl << endl; //1번에 연결된 노드 검색. cout << "Searching edge from 1 to "; for (int m = 0; m <= node; m++) { if (map[1][m] != 0) cout << m << " , "; } cout << endl; }

main_list

#include <iostream> using namespace std; struct node { int v; //연결된 노드 정보 //int value; //가중치가 있는 경우 사용. node *prev; } a[100]; int heap_cnt; node * myalloc(void) { return &a[heap_cnt++]; } node *table[10]; int main(void) { freopen("input.txt", "r", stdin); int no, edge, from, to; cin >> no >> edge; //초기화 heap_cnt = 0; for (int i = 0; i < no; i++) table[i] = nullptr; node *n; //간선 정보 입력 for (int e = 0; e < edge; e++) { cin >> from >> to; n = myalloc(); n->v = to; //연결된 노드를 저장 //n->value = input_value; // 가중치 저장. n->prev = table[from]; //from 의 Single linked list 에 저장 table[from] = n; } //모든 map 정보를 표시. cout << "Print all map info " << endl; for (int i = 0; i <= no; i++) { cout << "from " << i << " to "; for (node* iter = table[i]; iter != nullptr; iter = iter->prev) cout << iter->v << " "; cout << endl; } cout << endl << endl; //1번에 연결된 노드 검색. cout << "Searching edge from 1 to "; for (node* iter = table[1]; iter != nullptr; iter = iter->prev) // table[1] 의 Single linked list 에서 검색 { cout << iter->v << " , "; } cout << endl; }