Im4u 봄방학캠프 DAY 5; Elementary Graph Theory 구종만 jongman@gmail.com
그래프 (Graphs) 가장중요한 (?) 자료형인그래프의소개 그래프문제의큰두가지벽 모델링 : 현실세계의개념을그래프로나타낸다 알고리즘: 그래프로나타낸문제를해결한다 대개의문제에서는한가지벽만있다 모델링 : 문제를풀면서공부 알고리즘 : 비교적배우기쉽다 (^^)
자주등장하는주제들 셀수없이많지만.. 그래프의탐색 그래프의구조파악 컴포넌트들로분해 한붓그리기 (Eulerian Paths) 그래프를대상으로하는최적화문제들 최소신장트리 (MST) 최단거리문제 (Shortest Paths) 네트워크유량 (Network Flow)
오늘할이야기 ( 오늘은알고리즘에집중해보죠 ) 그래프의소개, 명시적 / 암시적그래프 그래프의구현 깊이우선탐색및너비우선탐색 Dijkstra 의최단거리알고리즘 한붓그리기 현실세계의문제를그래프로바꾸기 네트워크유량 ( 안할지도..) 다음주
그래프 6 4 2 0 계열 1 계열 2 1 2 3 4 우리가여기서다루고싶은것은?
그래프 6 4 2 0 계열 1 계열 2 1 2 3 4 네함수의그래프 (graph of a function) 아니죠그래프맞습니다 ~
느슨한정의 객체들과그들의연결관계를표현하는자료구조 기차역들과그들을연결하는기차선로 라우터들과그들을연결하는네트워크 논문들과그들의상호참조관계 사람들과그들사이의친분관계 소년탐정김전일 : 누가누구를죽였는가? 현실세계의문제를해결하기위한수학적인모델 모델 : 현실세계의근사치, 우리머릿속에서둥둥떠다닙니다
엄격한정의 정점 (vertex) 들의집합과그들의연결관계인간선 (edge) 들의집합으로구성되는자료구조 GV (, E 다른정보는포함하지않는다 아래의세그래프는모두같은그래프 )
그래프는어디서튀어나오는가 명시적그래프 (Explicit Graph) 문제에대놓고주어지는그래프 라우터와그들을잇는네트워크선 여러남녀들과그들의짝사랑관계 암시적그래프 (Implicit Graph) 15-Puzzle 브라운운동트래킹하기 이것들은다음주에 ( 사실이게진짜재밌는부분 )
그래프의종류들 표현하려는문제에따라그래프의간선들은다른속성을가질수있다 방향그래프 (directed graph) 가중치그래프 (weighted graph) 네트워크 (network)
그래프구현하기 The OOP Way class Vertex { public: void connectto(const const Vertex& other, int weight); bool isconnectedto(const const Vertex& other); VertexIterator getadjacent() const; }; class Edge { public: Vertex* getfirst(); Vertex* getsecond(); int getweight(); };
사실대개는 각정점에 0 부터 V-1 까지의번호를부여 배열을통해간단하게구현하게된다 정점이문자열이라도다음과같이변환가능 int getvertexno(const string& name) { static map<string string,int int> m; } if(m.count(name) > 0) return m[name]; int ret = m.size(); return m[name] = ret;
가장간단한방법 인접행렬 (adjacency matrix) VxV 크기의배열에간선정보를담는다 int V; bool graph[max_v][max_v]; // 간선 (u,v) 가 있으면 graph[u][v] == true bool directed[max_v][max_v]; // graph[u][v]!= graph[v][u] 일 수도 있음 int weighted[max_v][max_v]; // graph[u][v] 는 (u,v) 의 가중치, 없으면 -1 0 1 2 3 4 0 0 1 0 0 1 1 0 0 0 0 0 2 1 0 0 1 0 3 0 0 1 0 1 4 1 0 0 0 0
가장간단한방법 2 인접리스트 (adjacency list) V 개의연결리스트를만들어간선정보를담는다 int V; std::list<int int> graph[max_v]; std::list<pair<int int,int int> > weighed[max_v];
Matrix vs. List 인접행렬 두정점이주어졌을때간선의정보를 O(1) 에얻을수있다 인접한모든정점을효 율적으로찾을수없다 메모리사용량이많다 O(V*V) 밀집그래프 (dense graph) 에적합 인접리스트 두정점이주어졌을때연결리스트를처음부터읽어가야한다 인접한모든정점을효 율적으로찾을수있다 메모리사용량이적다 O(E) 희소그래프 (sparse graph) 에적합
희소그래프 vs. 밀집그래프 백문이불여일견
그래프의탐색 (search) YAM (Yet Another Misnamed) 역시또다른잘못지어진이름중하나 ( 라고주장中 ) 탐색보다관광에가까움 특정한순서에따라순서대로 발견 하는전략 가장유명한두개의방법이있음 깊이우선탐색 너비우선탐색 이들은많은그래프알고리즘의골격을형성함
깊이우선탐색 인접한정점중아직방문하지않은것을하나골라서그간선을따라간다 더따라갈간선이없으면마지막에따라온간선으로돌아간다 계속반복 간선의종류에주목
깊이우선탐색의구현 int V; std::vector<int int> graph[max_v]; bool visited[max_v]; void dfs(int here) { visited[here] = true; for(int i = 0; i< graph[here].size(); ++i) { int there = graph[here][i]; if(!visited[there]) dfs(there); } } for(int i = 0; i < V; ++i) visited[i] = false; for(int i = 0; i < V; ++i) if(!visited[i]) dfs(i); 대개재귀호출로구현 모든정점에서시작하는것에유의 : 왜?
위상정렬 DAG (Directed Acyclic Graph) 를재배열 모든간선이왼쪽에서오른쪽으로가도록
위상정렬 by DFS 앞절의코드에서 dfs() 함수가종료할때마다해당정점을목록의맨앞에추가한다 이것만으로도위상정렬완료! 증명?
위상정렬 by DFS 앞절의코드에서 dfs() 함수가종료할때마다해당정점을목록의맨앞에추가한다 이것만으로도위상정렬완료! 증명 by 귀류법 : 반대로가는간선 (u,v) 가있다고하자. 어느쪽이먼저 dfs() 함수가종료했을까?
깊이우선탐색신장트리 back edge cross edge tree edge forward edge 깊이우선탐색에사용된간선 (tree edge) 만남긴트리
간선의구분 DFS as a coloring process enum COLOR { WHITE, GRAY, BLACK }; int V; std::vector<int int> graph[max_v]; COLOR color[max_v]; int rank[here], time = 0; void dfs(int here) { color[here] = GRAY; rank[here] = time++; for(int i = 0; i < graph[here].size(); ++i) { int there = graph[here][i]; if(color[there] == WHITE) dfs(there); if(color[there] == GRAY) ; if(color[there] == BLACK) ; } color[here] = BLACK; } for(int i = 0; i < V; ++i) color[i] = WHITE; for(int i = 0; i < V; ++i) if(color[i] == WHITE) dfs(i);
간선의구분 Tree Edge (u,v) Forward Edge (u,v) Back Edge (u,v) Cross Edge (u,v)
간선의구분 Tree Edge (u,v) Color[there] == WHITE Forward Edge (u,v) color[there] == BLACK, rank[there] > rank[here] Back Edge (u,v) color[there] == GRAY Cross Edge (u,v) Color[there] == BLACK, rank[there] < rank[here]
사이클찾기 주어진그래프에사이클이존재하는가?
사이클찾기 그래프에서사이클의존재여부는 Back Edge 의존재여부와동치 사이클( u 1, u 2, L, u n 1, u n, u 1) 에서, WLOG, u 1 가제일먼저발견되었다고하자 dfs( u ) 은 u 1 n 이발견되기전까지끝나지않는다 간선 ( u n,u 1 ) 을발견했을때, u1 의색깔은?
절단점찾기 해당정점과인접간선을없애면그래프가두개이상으로찢어지는정점들 (cut vertex) 이문제에서는연결된무방향그래프를가정
절단점찾기 by DFS DFS 를하면서, dfs(u) 가종료할때 u 가절단점인지아닌지의여부를판정할수있다 연결된정점들의 rank, color,
현재정점이절단점일까? 자신이 DFS 신장트리의루트인가 / 아닌가로나뉨 루트인경우 : 비교적판단하기쉽다 한개의간선만따라가서탐색해도모든정점을만날수있어야함
루트가아닌경우 Forward edge 를만났다면? 글쎄다 Cross edge 를만났다면? Tree edge 를만났다면? 글쎄다 Back edge 를만났다면?
루트가아닌경우 Forward edge 를만났다면? 글쎄다 Cross edge 를만났다면? Cross edge 는없다 Tree edge 를만났다면? 글쎄다 Back edge 를만났다면? h 는사이클위에있다 ( 절단점 X)
Forward 와 Tree 이정점이절단점이아니라면 p 와 d 는 (h 빼고 ) 어떻게든연결되어있어야한다 이것을어떻게찾을까? dfs(u) = DFS 신장트리에서 u 와그후손들에대해, 직접연결된정점중최소의 rank 를반환
내가절단점이아니라면 모든내후손들은내선조 (rank 가나보다작은 ) 들로가는간선을갖고있어야한다 만약 (f,p3) 이없다면 h 는절단점일수밖에없다
따라서.. int time = 0; std::vector<int int> graph[max_v]; int rank[max_v]; // rank[i] == -1 이면 아직 방문 안 했음 int low[max_v]; // low[u] = u 를 루트로 하는 서브트리에서 연결된 가장 작은 rank bool iscutvertex[max_v]; int dfs(int here) { rank[here] = low[here] = time++; iscutvertex[here] = false; for(int i = 0; i < graph[here].size(); ++i) { int there = graph[here][i]; if(rank[there] == -1) // there 는 here 의후손 low[here] = min(low[here], dfs(there)); else // forward edge 혹은 back edge low[here] = min(low[here], rank[there]); if(low[there] >= rank[here]) iscutvertex[here] = true; } } dfs(0); 유일한예외 : iscutvertex[0]
OneWayStreets 양방향간선을한방향으로고정해서사이클이없도록하고싶다 : 가능할까? 찍어봅시다! TCO 08 R2 250
OneWayStreets 주어진그래프에이미방향있는간선으로구성된사이클이있다면, 당연히불가능하다 만약그런사이클이없다면가능할까? TCO 08 R2 250
OneWayStreets 가능하다! 구성적증명 방향간선만남긴그래프 G 를얻는다 G 를위상정렬한다 모든무방향간선을왼쪽에서오른쪽으로가도록방향을고정한다
너비우선탐색 시작점에서의최단거리순서대로방문해나간다
Formally Explained 방문할정점들의목록 q 를유지한다 q 는반드시 FIFO (First-In-First-Out) 큐여야한다 q 에서정점을꺼내방문하고 인접정점중에아직발견하지못한정점을찾아q 에추가 더 q 에정점이남지않을때까지반복한다
BFS 의구현 int time = 0, V; std::vector<int int> graph[max_v]; bool seen[max_v]; void bfs(int start) { for(int i = 0; i < V; ++i) seen[i] = false; std::queue<int int> q; q.push(start); seen[start] = true; while(!q.empty()) { int here = q.front(); q.pop(); for(int i = 0; i < graph[here].size(); ++i) { int there = graph[here][i]; if(!seen[there]) { q.push(there); seen[there] = true; } } } } std::queue 를사용하는것이간편하다 이세미나에서배우는모든알고리즘중가장유용 --;;
어떻게가까운순서대로방문할수있지? 모든정점들을최단거리별로분류한다고하자 V = S S L 0 1 S x 맨처음방문하는정점은 { start } = S Si 를모두방문하고나면큐에는S i+ 1 만들었다. 왜냐면 u S i 를방문중에 v 를큐에추가했다면, v S i+1 일테니까요 이것은귀류법으로증명가능 0
최단거리를기록하는너비우선탐색 int time = 0, V; std::vector<int int> graph[max_v]; int dist[max_v]; void bfs(int start) { for(int i = 0; i < V; ++i) dist[i] = -1; std::queue<int int> q; q.push(start); dist[start] = 0; while(!q.empty()) { int here = q.front(); q.pop(); for(int i = 0; i < graph[here].size(); ++i) { int there = graph[here][i]; if(dist[there] == -1) { q.push(there); dist[there] = dist[here] + 1; } } } } dist[x] = start ~ x 의최단거리
SortingGame 길이 n (<= 8) 인정수수열에대해, 임의의부분구간을골라이것을뒤집을수있다. 이때, 주어진수열을정렬하기위해이뒤집기를최소몇번이나해야하는가? SRM397 Div1 250
SortingGame 8! = 40320 개의가능한상태가있다 게임판의상태를정점으로, 뒤집는연산을간선으로하면무방향그래프를얻을수있다 BFS 로풀면되죠?
Avoiding Your Boss Boss 는 s 에서 t 까지항상최단거리로움직인다 2 개이상있으면, 모든경로에대해동일한확률 Boss 가 d 를지날확률은?
3-Tier Problem s 에서 t 까지최단거리를잰다 s 에서 t 로가는최단경로의개수를구한다 d 를지나는최단경로의개수를구한다 Graph & DP combined! 이번주의숙제입니다