그래프탐색 (Graph Search) 그래프의가장기본적인연산 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 많은문제들이단순히그래프의노드를탐색하는것으로해결 ( 예 ) 도로망에서특정도시에서다른도시로갈수있는지여부 ( 예 ) 전자회로에서특정단자와다른단자가서로연결되어있는지여부 ch12-44
깊이우선탐색 (DFS) 깊이우선탐색 (DFS: depth-first search) 한방향으로갈수있을때까지가다가더이상갈수없게되면가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색진행 되돌아가기위해서는스택필요 ( 순환함수호출로묵시적인스택이용가능 ) ch12-45
DFS 알고리즘 depth_first_search(v) v를방문되었다고표시 ; for all u (v에인접한정점 ) do if (u가아직방문되지않았으면 ) then depth_first_search(u) ch12-46
DFS 알고리즘 ch12-47
DFS 프로그램 // 인접행렬로표현된그래프에대한깊이우선탐색 void dfs_mat(graphtype *g, int v) int w; visited[v] = TRUE; // 정점 v의방문표시 printf("%d ", v); // 방문한정점출력 for(w=0; w<g->n; w++) // 인접정점탐색 if( g->adj_mat[v][w] &&!visited[w] ) dfs_mat(g, w); // 정점 w에서 DFS 새로시작 // 인접리스트로표현된그래프에대한깊이우선탐색 void dfs_list(graphtype *g, int v) GraphNode *w; visited[v] = TRUE; // 정점 v 의방문표시 printf("%d ", v); // 방문한정점출력 for(w=g->adj_list[v]; w; w=w->link) // 인접정점탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); // 정점 w->vertex 에서 DFS 새로시작 ch12-48
너비우선탐색 (BFS) 너비우선탐색 (BFS: breadth-first search) 시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 큐를사용하여구현됨 너비우선탐색알고리즘 breadth_first_search(v) v를방문되었다고표시 ; 큐Q에정점v를삽입 ; while (not is_empty(q)) do 큐 Q에서정점 w를삭제 ; for all u (w에인접한정점 ) do if (u가아직방문되지않았으면 ) then u를큐 Q에삽입 ; u를방문되었다고표시 ; ch12-49
ch12-50
ch12-51
DFS 와 BFS 의 C 프로그램구현 /* Graph.h (5) */ typedef struct Graph Vertex **vrtxptrarr; // vertex array EdgeList *adjlstarr; // adjacency list array int num_vertices; int **ppdistmtrx; Graph(int num_nodes); Graph; typedef struct DepthFirstSearch Graph *pgrp; VertexStatus *pvrtxstatus; EdgeStatus **ppedgestatus; DepthFirstSearch(Graph *pgrp); DFS_DONE searchdone; // used in depth first search int *pleastcost; DepthFirstSearch; /* Graph.h (6) */ typedef struct BreathFirstSearch Graph *pgrp; VertexStatus *pvrtxstatus; int *pleastcost; int *pprev; BFS_PROCSS_STATUS* pbfs_proc_stat; BreathFirstSearch(Graph *pgrp); BreathFirstSearch; void bfstraversal(breathfirstsearch *pbfs, Vertex *pstart, Vertex *ptarget, VertexList *pvtl); void dfstraversal(depthfirstsearch *pdfs, Vertex *pv, Vertex *ptarget, VertexList *pvtl); ch12-52
/* Graph.cpp (13) */ DepthFirstSearch::DepthFirstSearch(Graph *pgraph) int num_nodes; pgrp = pgraph; num_nodes = pgrp->num_vertices; pvrtxstatus = (VertexStatus *)malloc(sizeof(vertexstatus)* num_nodes); for (int i = 0; i < num_nodes; i++) pvrtxstatus[i] = VRTX_NOT_VISITED; ppedgestatus = (EdgeStatus **)malloc(sizeof(edgestatus *)* num_nodes); for (int i = 0; i < num_nodes; i++) ppedgestatus[i] = (EdgeStatus *)malloc(sizeof(edgestatus)* num_nodes); for (int i = 0; i < num_nodes; i++) for (int j = 0; j < num_nodes; j++) ppedgestatus[i][j] = EDGE_UNEXPLORED; searchdone = NOT_DONE; // used in depth first search (dfs) traversal pleastcost = (int *)malloc(sizeof(int)* num_nodes); ch12-53
/* Graph.cpp (14) */ void dfstraversal(depthfirstsearch *pdfs, Vertex *pv, Vertex *ptarget, VertexList *pvtl) int num_nodes = pdfs->pgrp->num_vertices, num_selected = 0; Vertex *pv2; int **distmtrx = pdfs->pgrp->ppdistmtrx; int *pleastcost = pdfs->pleastcost; int start_id, target_id, cur_id, vrtx_id, v2_id; EdgeList *pel; EdgeListNode *peln; Edge *pe; vrtx_id = pv->id; target_id = ptarget->id; pdfs->pgrp->vrtxptrarr[vrtx_id]->vtxstatus = VRTX_VISITED; if (vrtx_id == target_id) printf("depth First Search is done!! n"); pdfs->searchdone = DONE; return; ch12-54
/* Graph.cpp (15) */ pel = &(pdfs->pgrp->adjlstarr[vrtx_id]); peln = pel->pfirst; for (int i = 0; (i < pel->num_edges) & (pdfs->searchdone!= DONE); i++) pe = peln->pe; if (pe->edgestatus == EDGE_UNEXPLORED) pe->edgestatus = EDGE_VISITED; pv2 = pe->pv2; v2_id = pv2->id; if (pv2->vtxstatus!= VRTX_VISITED) listpushback(pvtl, pv2); pdfs->ppedgestatus[vrtx_id][v2_id] = DISCOVERY; if (pdfs->searchdone!= DONE) dfstraversal(pdfs, pv2, ptarget, pvtl); if (pdfs->searchdone!= DONE) Vertex *plast_pushed = pvtl->plast->pv; listpopback(pvtl); else // V2 has been visited already pe->edgestatus = BACK; // end if peln = peln->pnext; // end for ch12-55
/* Graph.cpp (16) */ BreathFirstSearch::BreathFirstSearch(Graph *pgraph) pgrp = pgraph; int num_nodes = pgrp->num_vertices; pprev = (int *)malloc(sizeof(int)* num_nodes); pleastcost = (int *)malloc(sizeof(int)* num_nodes); pbfs_proc_stat = (BFS_PROCSS_STATUS*)malloc(sizeof(BFS_PROCSS_STATUS)* num_nodes); void bfstraversal(breathfirstsearch *pbfs, Vertex *pstart, Vertex *ptarget, VertexList *pvtl) int num_nodes = pbfs->pgrp->num_vertices, num_selected = 0; Vertex *pvrtx; int *pleastcost = pbfs->pleastcost; int **distmtrx = pbfs->pgrp->ppdistmtrx; int *pprev = pbfs->pprev; BFS_PROCSS_STATUS *pbfs_proc_stat = pbfs->pbfs_proc_stat; int start_vrtxid, target_vrtxid, cur_vrtxid, vrtxid; int round, minid, mincost; start_vrtxid = pstart->id; target_vrtxid = ptarget->id; /* initialize L(n) = w(start, n) */ for (int i = 0; i < num_nodes; i++) pleastcost[i] = distmtrx[start_vrtxid][i]; pprev[i] = start_vrtxid; pbfs_proc_stat[i] = NOT_SELECTED; pbfs_proc_stat[start_vrtxid] = SELECTED; num_selected = 1; ch12-56
/* Graph.cpp (17) */ round = 0; printf("breadth First Search... n"); printdist(pbfs->pgrp->num_vertices, pbfs->pleastcost, round); while (num_selected < num_nodes) round++; //printf("round (%2d) : ", round); // find cur_node with least cost minid = -1; mincost = PLUS_INF; for (int i = 0; i < num_nodes; i++) if ((pleastcost[i] < mincost) & (pbfs_proc_stat[i]!= SELECTED)) minid = i; mincost = pleastcost[i]; if (minid == -1) printf("error in FindShortestPath with bfstraversal() n"); printf(" ==> Target is not connected to the start!! n"); break; else ch12-57
/* Graph.cpp (17) */ pbfs_proc_stat[minid] = SELECTED; num_selected++; if (minid == target_vrtxid) // target reached printf(" ==> reached to the target node (%2d) at ", target_vrtxid); printf(" least cost = %d n", mincost); vrtxid = minid; do pvrtx = pbfs->pgrp->vrtxptrarr[vrtxid]; VertexListNode *pvln = (VertexListNode *)malloc(sizeof(vertexlistnode)); pvln->pv = pvrtx; pvln->pnext = pvln->pprev = NULL; if (pvtl->num_vertices == 0) pvtl->pfirst = pvtl->plast = pvln; pvtl->num_vertices++; else pvln->pnext = pvtl->pfirst; pvtl->pfirst->pprev = pvln; pvtl->pfirst = pvln; pvtl->num_vertices++; vrtxid = pprev[vrtxid]; while (vrtxid!= start_vrtxid); ch12-58
/* Graph.cpp (17) */ pvrtx = pbfs->pgrp->vrtxptrarr[vrtxid]; // push start node at the front of path VertexListNode *pvln = (VertexListNode *)malloc(sizeof(vertexlistnode)); pvln->pv = pvrtx; pvln->pnext = pvtl->pfirst; pvln->pprev = NULL; pvtl->pfirst = pvln; pvtl->num_vertices++; break; // end if (minid == target_vrtxid) // end if-else int pls, distmtrx_i; for (int i = 0; i < num_nodes; i++) pls = pleastcost[i]; distmtrx_i = distmtrx[minid][i]; if ((pbfs_proc_stat[i]!= SELECTED) & (pleastcost[i] > (pleastcost[minid] + distmtrx[minid][i]))) // update distances with relaxation pprev[i] = minid; pleastcost[i] = pleastcost[minid] + distmtrx[minid][i]; // printout the pleastcost[] for debugging printdist(pbfs->pgrp->num_vertices, pbfs->pleastcost, round); // end while free(pleastcost); free(pprev); ch12-59
/* main.cpp (3) */ // Depth First Search printf(" ndepth First Search (DFS)... n"); VertexList vtl_1; initlist(&vtl_1); DepthFirstSearch dfs(&grph); listpushback(&vtl_1, pstart); dfstraversal(&dfs, pstart, ptarget, &vtl_1); printf("dfs::path from start (%2d) to target (%2d): n ", pstart->id, ptarget->id); printlist(&vtl_1); // Breadth First Search printf(" nbreadth First Search (BFS)... n"); VertexList vtl_2; initlist(&vtl_2); BreathFirstSearch bfs(&grph); bfstraversal(&bfs, pstart, ptarget, &vtl_2); printf("shortestpath::path from start (%2d) to target (%2d): n ", pstart->id, ptarget->id); printlist(&vtl_2); ch12-60
미로 (Maze) 찾기 Graph representation for Maze vertex: cross point edge: distance between the cross points 0 1 2 0 1 v0 v1 v2 (start) v3 v4 v5 v6 v7 v8 2 (end) ch12-61
ch12-62
0 1 2 0 1 v0 v1 v2 (start) v3 v4 v5 v6 v7 v8 2 (end) 0 1 0 1 2 v0 v1 v2 (start) v3 v4 v5 3 2 v6 v7 v8 (end) 3 4 4 ch12-63
5 x 5 미로 (Maze) 찾기 Find the shortest path from v0 (start) to v20 (end) 0 1 2 3 4 0 1 2 3 v0 v1 v2 v3 v4 (start) v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 4 v20 (end) v21 v22 v23 ch12-64 v24
5x5 미로 (Maze) 찾기 Depth First Search example 0 1 2 3 4 0 v0 (start) v1 v2 v3 v4 Tracking Back Tracking 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 4 v20 (end) v21 v22 v23 v24 ch12-65
5x5 미로 (Maze) 찾기 Breadth First Search example 0 1 2 3 4 0 v0 (start) v1 v2 v3 v4 Tracking 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 4 v20 (end) v21 v22 v23 v24 ch12-66
미로 (Maze) 찾기결과 Sample routes to target (v0 v20) 0 1 2 3 4 0 1 2 v0 v1 v2 v3 v4 (start) v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 Path by obtained by Depth First Search Path by obtained by Breadth First Search 3 v15 v16 v17 v18 v19 4 v20 v21 v22 v23 v24 (end) ch12-67
IP Packet Router 의 Forwarding Table 작성 Input network topology (USA) Seattle 0 1144 820 San Francisco 1 380 2 Los Angels 745 688 828 Salt Lake City 381 6 Phoenix 3 521 816 657 Rapid city 4 389 Denver 5 1067 920 780 611 861 Dallas 8 246 Minneapolis 9 Houston 7 Memphis 454 ch12-68 409 St. Louis 352 12 Chicago 297 11 393 10 13 285 394 473 New Orleans Detroit 286 845 14 861 534 16 632 834 Atlanta 17 Washington D.C. 661 640 15 Miami Boston 19 211 18 New York 237
Depth First Search example Find a path from Seattle to Miami Seattle Tracking Back Tracking 0 1144 820 San Francisco 1 380 2 Los Angels 745 688 828 Salt Lake City 381 6 Phoenix 3 521 816 657 Rapid city 4 389 Denver 5 1067 920 780 611 861 Dallas 8 246 Minneapolis 9 Houston 7 Memphis 454 ch12-69 409 St. Louis 352 12 Chicago 297 11 393 10 13 285 394 473 New Orleans Detroit 286 845 14 861 534 16 632 834 Atlanta 17 Washington D.C. 661 640 15 Miami Boston 19 211 18 New York 237
Breadth First Search example Find the shortest path from Seattle to Miami Seattle 0 1144 820 San Francisco 1 380 2 Los Angels 745 688 828 Salt Lake City 381 6 Phoenix 3 521 816 657 Rapid city 4 389 Denver 5 1067 920 780 611 861 Dallas 8 246 Minneapolis 9 Houston 7 Memphis 454 ch12-70 409 St. Louis 352 12 Chicago 297 11 393 10 13 285 394 473 New Orleans Detroit 286 845 14 861 534 16 632 834 Atlanta 17 Washington D.C. 661 640 15 Miami Boston 19 211 18 New York 237
경로찾기 Path (0 15) produced by Depth First Search (DFS) Path by obtained by Depth First Search Path by obtained by Breadth First Search ch12-71
Homework 12 12.1 미로찾기 (1) 다음과같은미로에서임의의시작점 ( 예 : v0) 에서임의의종단점 ( 예 : v24) 까지의경로를찾기위한 Graph 프로그램을작성하고, printgraph() 함수를사용하여, 그래프정보를출력하라. (2) 시작점 (v0) 에서종단점 (v24) 까지의경로를 DFS (Depth First Search) 알고리즘으로찾는프로그램을작성하고, 결과경로를출력하라. (3) 시작점 (v0) 에서종단점 (v24) 까지의경로를 BFS (Breadth First Search) 알고리즘으로찾는프로그램을작성하고, 결과경로를출력하라. 0 1 2 3 4 0 v0 (start) v1 v2 v3 v4 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 v20 v21 v22 v23 v24 4 (end) ch12-72
12.2 Forwarding Table 구성 (1) 다음과같은네트워크에서 Graph BFS 탐색알고리즘을실행할수있도록 Graph 프로그램을작성하라. (2) 이 Graph 프로그램에서임의의노드로부터다른모든노드로최소비용경로를통하여갈수있는경로들을 BFS 알고리즘을찾는프로그램을작성하라. (3) 임의의지정된노드로부터, 다른모든노드로의최소비용경로를산출한후, 해당목적지로전달되어야하는패킷의 next hop을나타내는 forwarding table을출력하는프로그램을작성하라. ch12-73