v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

(1)

12. 그래프와 관련 알고리즘 (보충설명)

2015-1 Programming Language

2015년 5월 26일

교수 김 영 탁

영남대학교 공과대학 정보통신공학과

(Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr)

(2)

Advanced Networking Tech. Lab.

미로 (Maze) 찾기

Graph representation for Maze

 vertex: cross point

 edge: distance between the cross points

0 1 2

0

1

2

v0 (start)

v1 v2

v3 v4 v5

v6 v7 v8

(end)

(3)

Yeungnam University (yuANTL) Programming Language

Prof. Young-Tak Kim ch12 - 3

(4)

0 1 2

0

1

2

v0 (start)

v1 v2

v3 v4 v5

v6 v7 v8

(end)

0 1 2

0

1

2

v0 (start)

v1 v2

v3 v4 v5

v6 v7 v8

(end)

3 4

(5)

5 x 5 미로 (Maze) 찾기

Find the shortest path from v0 (start) to v20 (end)

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

0 1 2 3 4

0

1

2

3

4

v0

v24 (start)

(end)

v4

v20

v1 v2 v3

v5 v6 v7 v8 v9

v10 v11 v12 v13 v14

v15 v16 v17 v18 v19

v21 v22 v23

(6)

5x5 미로 (Maze) 찾기

 Depth First Search example

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

0 1 2 3 4

0

1

2

3

4

v0

v24 (start)

(end)

v4

v20

v1 v2 v3

v5 v6 v7 v8 v9

v10 v11 v12 v13 v14

v15 v16 v17 v18 v19

v21 v22 v23

Tracking

Back Tracking

(7)

5x5 미로 (Maze) 찾기

 Breadth First Search example

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

0 1 2 3 4

0

1

2

3

4

v0

v24 (start)

(end)

v4

v20

v1 v2 v3

v5 v6 v7 v8 v9

v10 v11 v12 v13 v14

v15 v16 v17 v18 v19

v21 v22 v23

Tracking

(8)

미로 (Maze) 찾기 결과

 Sample routes to target (v0  v20)

0 1 2 3 4

0

1

2

3

4

v0

v24 (start)

(end) v4

v20

v1 v2 v3

v5 v6 v7 v8 v9

v10 v11 v12 v13 v14

v15 v16 v17 v18 v19

v21 v22 v23

Path by obtained by Depth First Search Path by obtained by Breadth First Search

(9)

IP Packet Router의 Forwarding Table 작성

 Input network topology (USA)

0

1

2

5

7

8 6

9

12 13

14

19 18

17

16

10

15 11

3 820

1144

828 Seattle

San Francisco

Salt Lake City

Los Angels

Denver

Phoenix

Houston Dallas

Minneapolis

Chicago

St. Louis

Memphis

New Orleans

Atlanta

Miami Washington

D.C.

Detroit

New York Boston

745

380 688

381

816

1067

920

861

780 521

409

297

286

845

285

454 246

352 393

394

473

861

661 632 534

640 834

211 237

4 Rapid city

611 657

389

(10)

 Depth First Search example

 Find a path from Seattle to Miami

0

1

2

5

7

8 6

9

12 13

14

19 18

17

16

10

15 11

3 820

1144

828 Seattle

San Francisco

Salt Lake City

Los Angels

Denver

Phoenix

Houston Dallas

Minneapolis

Chicago

St. Louis

Memphis

New Orleans

Atlanta

Miami Washington

D.C.

Detroit

New York Boston

745

380 688

381

816

1067

920

861

780 521

409

297

286

845

285

454 246

352 393

394

473

861

661 632 534

640 834

211 237

4 Rapid city

611 657

389

Tracking

Back Tracking

(11)

 Breadth First Search example

 Find the shortest path from Seattle to Miami

0

1

2

5

7

8 6

9

12 13

14

19 18

17

16

10

15 11

3 820

1144

828 Seattle

San Francisco

Salt Lake City

Los Angels

Denver

Phoenix

Houston Dallas

Minneapolis

Chicago

St. Louis

Memphis

New Orleans

Atlanta

Miami Washington

D.C.

Detroit

New York Boston

745

380 688

381

816

1067

920

861

780 521

409

297

286

845

285

454 246

352 393

394

473

861

661 632 534

640 834

211 237

4 Rapid city

611 657

389

(12)

Path by obtained by Depth First Search Path by obtained by

Breadth First Search

 Comparison of results

(13)

그래프의 C 프로그램

/* Graph.h (1) */

#ifndef GRAPH_H

#define GRAPH_H

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <limits>

#define MAX_NAME_LENGTH 10

#define PLUS_INF INT_MAX/2

enum VertexStatus {UNEXPLORED, VRTX_NOT_VISITED, VRTX_VISITED, VRTX_NOT_SELECTED, VRTX_SELECTED};

enum EdgeStatus {EDGE_UNEXPLORED, DISCOVERY, BACK, CROSS, EDGE_NOT_FOUND, EDGE_VISITED};

enum BFS_PROCSS_STATUS {NOT_SELECTED, SELECTED};

enum DFS_DONE {NOT_DONE, DONE};

(14)

/* Graph.h (2) */

typedef struct Vertex {

int ID;

char vname[MAX_NAME_LENGTH];

VertexStatus vtxStatus;

Vertex(int id, char name[]);

} Vertex;

typedef struct VertexListNode {

Vertex *pV;

VertexListNode *pNext;

VertexListNode *pPrev;

} VertexListNode;

typedef struct VertexList {

VertexListNode *pFirst;

VertexListNode *pLast;

int num_vertices;

} VertexList;

/* Graph.h (3) */

typedef struct Edge {

Vertex *pV1;

Vertex *pV2;

int dist;

EdgeStatus edgeStatus;

Edge(Vertex *pV1, Vertex *pV2, int dist);

} Edge;

typedef struct EdgeListNode {

Edge *pE;

EdgeListNode *pNext;

EdgeListNode *pPrev;

} EdgeListNode;

typedef struct EdgeList {

EdgeListNode *pFirst;

EdgeListNode *pLast;

int num_edges;

} EdgeList;

(15)

/* Graph.h (4) */

typedef struct Graph {

Vertex **vrtxPtrArr; // vertex array

EdgeList *adjLstArr; // adjacency list array int num_vertices;

int **ppDistMtrx;

Graph(int num_nodes);

} Graph;

void insertVertex(Graph *pGrp, Vertex *pVtrx);

void insertEdge(Graph *pGrp, Edge *pEdge);

void incidentEdges(Graph *pGrp, Vertex *pVrtx, EdgeList *pEdges);

void printVrtx(Vertex *pV);

void printEdge(Edge *pE);

void printEdges(EdgeList el);

void printGraph(Graph *pGrp);

void printList(VertexList *pVTL);

void printListReverse(VertexList *pVTL);

void initList(VertexList *pVTL);

void printDistMtrx(int **distMtrx, int num_nodes);

void printDist(int num_nodes, int *dist, int round);

void listPushBack(VertexList *pVTL, Vertex *pV);

void listPopBack(VertexList *pVTL);

void listPushBack(EdgeList *pEL, Edge *pE);

void listInsertInOrder(EdgeList *pEL, Edge *pE);

#endif

(16)

/* Graph.cpp (1) */

#include <stdio.h>

#include "Graph.h"

Vertex::Vertex(int id, char name[]) {

strcpy(vname, name);

ID = id;

vtxStatus =UNEXPLORED;

}

Edge::Edge(Vertex p1, Vertex p2, int d) {

pV1 = p1;

pV2 = p2;

dist = d;

edgeStatus = EDGE_UNEXPLORED;

}

(17)

/* Graph.cpp (2) */

Graph::Graph(int num_nodes) {

num_vertices = num_nodes;

vrtxPtrArr = (Vertex **)malloc(sizeof(Vertex *) * num_vertices); // vertex array for (int i = 0; i < num_vertices; i++)

{

vrtxPtrArr[i] = NULL;

}

adjLstArr = (EdgeList *)malloc(sizeof(EdgeList)* num_vertices); // adjacency list array for (int i = 0; i < num_vertices; i++)

{

adjLstArr[i].pFirst = adjLstArr[i].pLast = NULL;

adjLstArr[i].num_edges = 0;

}

/* prepare distance matrix */

ppDistMtrx = (int **)malloc(sizeof(int *)* num_vertices);

for (int i = 0; i < num_vertices; i++) {

ppDistMtrx[i] = (int *)malloc(sizeof(int)* num_vertices);

}

for (int i = 0; i < num_vertices; i++) for (int j = 0; j < num_vertices; j++) if (i == j)

ppDistMtrx[i][j] = 0;

else

ppDistMtrx[i][j] = PLUS_INF;

}

(18)

/* Graph.cpp (3) */

void insertVertex(Graph *pGrp, Vertex *pVtrx) {

int vid = pVtrx->ID;

if (vid < 0 || vid >= pGrp->num_vertices) {

printf("Error in vertex ID (%D) which is outof range (%d) !!₩n", vid, pGrp->num_vertices);

exit;

}

if (pGrp->vrtxPtrArr[vid] == NULL) pGrp->vrtxPtrArr[vid] = pVtrx;

}

void insertEdge(Graph *pGrp, Edge *pEdge) {

Vertex *v1, *v2;

int v1_id, v2_id;

if (pEdge->pV1 == NULL) {

printf("Error:: edge has null vertex !!₩n");

exit;

} else {

v1_id = pEdge->pV1->ID;

}

(19)

/* Graph.cpp (4) */

if (pEdge->pV2 == NULL) {

printf("Error:: edge has null vertex !!₩n");

exit;

} else {

v2_id = pEdge->pV2->ID;

}

if (pGrp->vrtxPtrArr[v1_id] == NULL)

pGrp->vrtxPtrArr[v1_id] = pEdge->pV1;

if (pGrp->vrtxPtrArr[v2_id] == NULL)

pGrp->vrtxPtrArr[v2_id] = pEdge->pV2;

//listPushBack(&pGrp->adjLstArr[v1_id], pEdge);

listInsertInOrder(&pGrp->adjLstArr[v1_id], pEdge);

// update distMtrx

pGrp->ppDistMtrx[v1_id][v2_id] = pEdge->dist;

}

void printVrtx(Vertex *pV) {

printf("Vertex(%2d, %3s) : ", pV->ID, pV->vname);

}

(20)

/* Graph.cpp (5) */

void printEdge(Edge *pE) {

if (pE->dist != PLUS_INF)

printf("Edge (%2d -> %2d, %2d)", pE->pV1->ID, pE->pV2->ID, pE->dist);

else

printf("Edge (%2d -> %2d, oo)", pE->pV1->ID, pE->pV2->ID);

}

void printEdges(EdgeList el) {

EdgeListNode *pELN = el.pFirst;

int numOutgoingEdges = el.num_edges;

for (int i = 0; i < numOutgoingEdges; i++) {

printEdge(pELN->pE);

if (i < (numOutgoingEdges - 1)) printf(", ");

pELN = pELN->pNext;

} }

(21)

/* Graph.cpp (6) */

void printDist(int num_nodes, int *dist, int round) {

if (round == 0) // print heading at the beginning {

printf("Distances from the start node at each round: ₩n");

printf(" |");

for (int i = 0; i < num_nodes; i++) {

printf("%5d", i);

}

printf("₩n");

printf("---+");

printf("---", i);

}

printf("₩n");

}

printf("round[%2d] |", round);

if (dist[i] == PLUS_INF) printf(" +oo");

else

printf("%5d", dist[i]);

}

printf("₩n");

}

(22)

/* Graph.cpp (7) */

void printDistMtrx(int **distMtrx, int num_nodes) {

int dist;

printf("Distance Matrix:₩n");

printf(" |");

for (int i = 0; i < num_nodes; i++) printf("%5d", i);

printf("₩n");

printf("----+");

for (int i = 0; i < num_nodes; i++) printf("---");

printf("₩n");

printf("%2d |", i);

for (int j = 0; j < num_nodes; j++) {

dist = distMtrx[i][j];

if (dist == PLUS_INF) printf(" +oo");

else

printf("%5d", dist);

}

printf("₩n");

}

printf("₩n");

}

(23)

/* Graph.cpp (8) */

void printDistMtrx(Graph *pGrp) {

int num_nodes = pGrp->num_vertices;

int **distMtrx = pGrp->ppDistMtrx;

printDistMtrx(distMtrx, num_nodes);

}

void printGraph(Graph *pGrp) {

int num_vrtx = pGrp->num_vertices;

printf("₩nGraph of %d vertices:₩n", num_vrtx);

for (int i = 0; i < num_vrtx; i++) {

printVrtx(pGrp->vrtxPtrArr[i]);

printEdges(pGrp->adjLstArr[i]);

printf("₩n");

}

printDistMtrx(pGrp);

}

(24)

/* Graph.cpp (9) */

void initList(VertexList *pVTL) {

pVTL->pFirst = pVTL->pLast = NULL;

pVTL->num_vertices = 0;

}

void listPushBack(VertexList *pVTL, Vertex *pV) {

VertexListNode *pVLN = (VertexListNode *)malloc(sizeof(VertexListNode));

pVLN->pV = pV;

pVLN->pNext = pVLN->pPrev = NULL;

printf("listPushBack:: vertex (%2d)₩n", pV->ID);

if (pVTL->num_vertices == 0) {

pVTL->pFirst = pVTL->pLast = pVLN;

} else {

pVLN->pPrev = pVTL->pLast;

pVTL->pLast->pNext = pVLN;

pVTL->pLast = pVLN;

}

pVTL->num_vertices++;

}

(25)

/* Graph.cpp (10) */

void listPushBack(EdgeList *pEL, Edge *pE) {

EdgeListNode *pELN = (EdgeListNode *)malloc(sizeof(EdgeListNode));

pELN->pE = pE;

pELN->pNext = pELN->pPrev = NULL;

//printf("listPushBack:: edge (%2d -> %2d)₩n", pE->pV1->ID, pE->pV2->ID);

if (pEL->num_edges == 0) {

pEL->pFirst = pEL->pLast = pELN;

} else {

pELN->pPrev = pEL->pLast;

pEL->pLast->pNext = pELN;

pEL->pLast = pELN;

}

pEL->num_edges++;

}

(26)

void listInsertInOrder(EdgeList *pEL, Edge *pE)

{ EdgeListNode *pNew = (EdgeListNode *)malloc(sizeof(EdgeListNode));

EdgeListNode *pLN;

pNew->pE = pE;

pNew->pNext = pNew->pPrev = NULL;

//printf("listPushBack:: edge (%2d -> %2d)₩n", pE->pV1->ID, pE->pV2->ID);

if (pEL->num_edges == 0)

{ pEL->pFirst = pEL->pLast = pNew;

pEL->num_edges++;

} else {

for (pLN = pEL->pFirst; pLN != NULL;) { if (pNew->pE->dist < pLN->pE->dist)

{ pNew->pNext = pLN;

pNew->pPrev = pLN->pPrev;

if (pLN == pEL->pFirst) { pEL->pFirst = pNew;

pNew->pPrev = NULL;

pLN->pPrev = pNew;

} else { // pLN != pEL->pFirst if (pLN->pPrev != NULL)

pLN->pPrev->pNext = pNew;

pLN->pPrev = pNew;

}pEL->num_edges++;

break;

}

(27)

else if ((pLN == pEL->pLast) && (pNew->pE->dist >= pLN->pE->dist)) { pNew->pPrev = pLN;

pLN->pNext = pNew;

pEL->pLast = pNew;

pNew->pNext = NULL;

pEL->num_edges++;

break;

}else {

if (pLN != pEL->pLast) pLN = pLN->pNext;

elsebreak;

} // end if-else } // end for

} // end if }

(28)

void listPopBack(VertexList *pVTL) { if (pVTL->num_vertices == 0)

{ printf("Exception:: popBack() while VertexList is empty !!₩n");

return;

}else {

VertexListNode *pVLN = pVTL->pLast;

printf("listPopBack:: vertex (%2d)", pVLN->pV->ID);

pVTL->pLast = pVTL->pLast->pPrev;

printf(" -> vertex (%2d)₩n", pVTL->pLast->pV->ID);

free(pVLN);

}pVTL->num_vertices--;

}

(29)

/* Graph Topology of 5 x 5 Maze*/

#ifndef GRAPHTOP_MAZE_5x5

#define GRAPHTOP_MAZE_5x5

#include "Graph.h"

#define NUM_NODES 25

#define NUM_EDGES 50

Vertex v[NUM_NODES] = // 20 nodes

{ Vertex( 0, "v0" ), Vertex( 1, "v1" ), Vertex( 2, "v2" ), Vertex( 3, "v3" ), Vertex( 4, "v4" ), Vertex( 5, "v5" ), Vertex( 6, "v6" ), Vertex( 7, "v7" ), Vertex( 8, "v8" ), Vertex( 9, "v9" ), Vertex( 10, "v10" ), Vertex( 11, "v11" ), Vertex( 12, "v12"), Vertex( 13, "v13"), Vertex( 14, "v14" ), Vertex( 15, "v15" ), Vertex( 16, "v16" ), Vertex( 17, "v17"), Vertex( 18, "v18"), Vertex( 19, "v19" ), Vertex( 20, "v20" ), Vertex( 21, "v21" ), Vertex( 22, "v22"), Vertex( 23, "v23"), Vertex( 24, "v24" ) };

Edge edges[NUM_EDGES] = // 50 edges {

Edge(&v[0], &v[1], 0), Edge(&v[1], &v[0], 0), Edge(&v[1], &v[2], 0), Edge(&v[2], &v[1], 0), Edge(&v[0], &v[5], 0), Edge(&v[5], &v[0], 0), Edge(&v[1], &v[6], 0), Edge(&v[6], &v[1], 0), Edge(&v[3], &v[8], 0), Edge(&v[8], &v[3], 0), Edge(&v[4], &v[9], 0), Edge(&v[9], &v[4], 0), Edge(&v[6], &v[7], 0), Edge(&v[7], &v[6], 0), Edge(&v[7], &v[8], 0), Edge(&v[8], &v[7], 0), Edge(&v[6], &v[11], 0), Edge(&v[11], &v[6], 0), Edge(&v[8], &v[13], 0), Edge(&v[13], &v[8], 0), Edge(&v[9], &v[14], 0), Edge(&v[14], &v[9], 0), Edge(&v[10], &v[11], 0), Edge(&v[11], &v[10], 0), Edge(&v[13], &v[14], 0), Edge(&v[14], &v[13], 0), Edge(&v[10], &v[15], 0), Edge(&v[15], &v[10], 0), Edge(&v[12], &v[17], 0), Edge(&v[17], &v[12], 0), Edge(&v[14], &v[19], 0), Edge(&v[19], &v[14], 0), Edge(&v[15], &v[16], 0), Edge(&v[16], &v[15], 0), Edge(&v[17], &v[18], 0), Edge(&v[18], &v[17], 0), Edge(&v[18], &v[19], 0), Edge(&v[19], &v[18], 0), Edge(&v[15], &v[20], 0), Edge(&v[20], &v[15], 0), Edge(&v[16], &v[21], 0), Edge(&v[21], &v[16], 0), Edge(&v[17], &v[22], 0), Edge(&v[22], &v[17], 0), Edge(&v[18], &v[23], 0), Edge(&v[23], &v[18], 0), Edge(&v[21], &v[22], 0), Edge(&v[22], &v[21], 0), Edge(&v[23], &v[24], 0), Edge(&v[24], &v[23], 0)

};

#endif

(30)

/* main.cpp (1) */

#include <stdio.h>

#include "Graph.h"

#define TEST_TOPOLOGY 2 void main()

{

Vertex *pStart, *pTarget;

#if (TEST_TOPOLOGY == 1)

#include "Graph_Simple_2x3.h"

pStart = &v[0];

pTarget = &v[5];

#elif (TEST_TOPOLOGY == 2)

#include "GraphTop_Maze_5x5.h"

pStart = &v[0];

pTarget = &v[20];

#include "GraphTopology_16Nodes_50Edges.h"

pStart = &v[0];

pTarget = &v[15];

#include "GraphTopology_USA.h"

pStart = &v[0];

pTarget = &v[15];

#endif

/* main.cpp (2) */

Graph grph(NUM_NODES);

for (int i = 0; i < NUM_NODES; i++) {

insertVertex(&grph, &v[i]);

}

for (int e = 0; e < NUM_EDGES; e++) {

insertEdge(&grph, &edges[e]);

}

printGraph(&grph);

}

(31)

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);

(32)

DepthFirstSearch::DepthFirstSearch(Graph *pGraph) {

int num_nodes;

pGrp = pGraph;

num_nodes = pGrp->num_vertices;

pVrtxStatus = (VertexStatus *)malloc(sizeof(VertexStatus)* num_nodes);

pVrtxStatus[i] = VRTX_NOT_VISITED;

}

ppEdgeStatus = (EdgeStatus **)malloc(sizeof(EdgeStatus *)* num_nodes);

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);

}

(33)

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;

}

(34)

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 }

(35)

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;

(36)

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;

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 {

(37)

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;

} else {

pVLN->pNext = pVTL->pFirst;

pVTL->pFirst->pPrev = pVLN;

pVTL->pFirst = pVLN;

}

vrtxID = pPrev[vrtxID];

} while (vrtxID != start_vrtxID);

(38)

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;

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);

}

(39)

/* 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);

}

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

12. 그래프와 관련 알고리즘 (보충설명)

2015-1 Programming Language

Graph representation for Maze

Find the shortest path from v0 (start) to v20 (end)

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

 Depth First Search example

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

Tracking

Back Tracking

 Breadth First Search example

v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): +

Tracking

 Sample routes to target (v0  v20)

 Input network topology (USA)

 Depth First Search example

 Find a path from Seattle to Miami

Tracking

Back Tracking

 Breadth First Search example

 Find the shortest path from Seattle to Miami

 Comparison of results

/* Graph.cpp (1) */

#include <stdio.h>

#include "Graph.h"

Vertex::Vertex(int id, char name[]) {

strcpy(vname, name);

ID = id;

vtxStatus =UNEXPLORED;

}

Edge::Edge(Vertex *p1, Vertex *p2, int d) {

pV1 = p1;

pV2 = p2;

dist = d;

edgeStatus = EDGE_UNEXPLORED;

}

Edge::Edge(Vertex p1, Vertex p2, int d) {