쿠리 프로 시험 유용 그래프 사용법

1. 배열 이용하는 방법 2. 리스트 이용하는 방법 각각 맵에 저장하고 검색하는 방법을 나타내고 있음 아래 코드는 리스트 이용하는 방법 연결된 노드 정보를 single linked list 배열에 저장한느 방식 parent 정보가 없는 Tree 생각 초기화시 myalloc 사용하는 heap_cnt 와 Single linked list 저장되는 table[]을 초기화 주면 됨 가중치가 있는 그래프의 경우 node 구조체에 value를 추가하고, n->value에 가중치를 저장하면 됨

#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; }