조 병 규 Software Quality Lab. 한 국 교 통 대 학 교

Presentation on theme: "조 병 규 Software Quality Lab. 한 국 교 통 대 학 교"— Presentation transcript:

1 조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
NonLinear Structure 조 병 규 Software Quality Lab. 한 국 교 통 대 학 교

2 graph 비선형 자료 구조를 표현한 것 점(vertex)들과 이들을 연결하는 선(edge)들의 집합
일반적으로 점과 선에 고유한 명칭을 부여함 G = {V(G), E(G)} SQ LAB.

3 Graph example a 1 b 2 c 3 4 6 d 5 e f G = {{a, b, c, d, e, f}, {1, 2, 3 , 4, 5, 6}} SQ LAB.

4 용어 정리 그래프의 차수(order of graph) 그래프를 구성하는 점(vertex)의 수
    그래프의 복잡함은 반드시 그래프의 차수에 관계되는 것은 아니나, 일반적으로 차수가 높으면 높을수록 그래프가 복잡해진다. 선의 종류 무방향선(undirected edge)        방향이 없는 선분으로 시작점과 종착점 관계를 두지않고,       (vertex_m, vertex_n) 또는 (vertex_n, vertex_m)으로 표현       ⓜ────────ⓝ    (m,n) 또는 (n,m) 방향선(directed edge)       선의 방향이 있는 것으로 반드시 (시작점, 종착점)으로 표현한다.        ⓜ───────〉ⓝ    (m,n) SQ LAB.

5 용어 정리 점의 인접(adjacent) (vertex_m, vertex_n)인 경우
vertex_m과 vertex_n는 서로 인접 (adjacent)되었다고  함 루프(loop)    자기 자신의 점에 연결된 선, 즉 (vertex_n, vretex_n) 패스(path)    임의의 점에서 다른 점까지 연결된 일련의 선의 집합 P(시작점, 종착점)으로 표현 패스 길이(path length)    임의의 패스를 이루는 선분의 개수이다. 단순 패스(simple path)    패스 내에 동일한 선분이 중복되지 않는 패스이다. 싸이클(cycle)    시작점과 종착점이 같고, 동일한 선분이 두 번 이상 존재하지 않는 패스 SQ LAB.

6 그래프의 종류 방향 그래프와 무방향 그래프 단순 그래프와 다중 그래프 연결 그래프와 비연결 그래프 가중 그래프와 비가중 그래프
완전 그래프 SQ LAB.

7 방향 그래프와 무방향 그래프 방향 그래프(directed graph, di-graph)
  그래프를 구성하는 모든 선분이 방향 선분 (directed edge)으로 구성된 그래프 무방향 그래프(undirected graph)    그래프를 구성하는 모든 선분이 무방향 선분 (undirected edge)로 구성된 그래프 SQ LAB.

8 (예) 방향 그래프와 무방향 그래프 방향 그래프 a b c d e f 무방향 그래프 a b c d e f SQ LAB.

9 단순 그래프와 다중 그래프 단순 그래프(simple graph) 루프(loop)가 없고,
두 점을 연결하는 선분이 하나로만 구성 다중 그래프(multi-graph)    단순 그래프가 아닌 것 SQ LAB.

10 (예) 단순 그래프와 다중 그래프 단순 그래프 a b c d e f 다중 그래프 a b c d e f SQ LAB.

11 연결 그래프와 비연결 그래프 연결 그래프(connected graph) 그래프를 구성하는 점들에 대하여
   그래프를 구성하는 점들에 대하여 모든 임의의 두 점 사이에 패스가 존재하는 그래프 비연결 그래프(disconnected graph) 그래프를 구성하는 점들에 대하여 패스가 존재하지 않는 것도 있는 그래프 SQ LAB.

12 (예) 연결 그래프와 비연결 그래프 연결 그래프 a b c d e f 비연결 그래프 a b c d e f SQ LAB.

13 가중 그래프와 비가중 그래프 가중 그래프(weighted graph, network) 선분에 임의의 값을 가진 그래프
   선분에 임의의 값을 가진 그래프 비가중 그래프(unweight graph)    선분에 값이 부여되지 않은 그래프 SQ LAB.

14 (예) 가중 그래프와 비가중그래프 a b c d e f a b c d e f 가중 그래프 비가중 그래프 10 10 10 10
SQ LAB.

15 완전 그래프(complete graph)
그래프를 구성하는 모든 점들이 서로 인접된 그래프 점의 수가 n개인 완전 그래프에서의 선분의 수 = n(n-1)/2 SQ LAB.

16 (예) 완전 그래프 a b c d vetex 수 = 4             edge 수 = 4(4-1)/2=6 SQ LAB.

17 그래프의 표현 인접 행렬(Adjacency Matrx) 선분 리스트(Edge List)
인접 리스트(Adjacency List) SQ LAB.

18 인접 행렬로의 표현 - 정점의 수가 n일 경우 n x n의 2차원 배열을 확보하여,
두 정점 사이의 접속 관계를 설정된 기호로 표시 - 정점의 수 : n 배열  A = n x n 1 : (u, v) 존재 A(u, v) 0 : (u, v) 존재 안함 SQ LAB.

19 (예) 인접 행렬로의 표현 a b c d e f a b c d e f a b c d e f 방향 그래프 무방향 그래프 8 4
u v a b c d e f 1 d e f a b c u v a b c d e f 1 무방향 그래프 d e f 8 4 a b c 가중 그래프 u v a b c d e f 8 2 4 1 5 3 6 5 2 1 3 6 d e f SQ LAB.

20 선분 리스트 (Edge List)로의 표현 각 선분의 두 정점을 (시작점, 종착점, 가중치1,가중치2,∙ ∙ ∙,가중치n)
로 표현 SQ LAB.

21 (예) 선분 리스트로의 표현 : 방향 그래프 a b c d e f 방향 그래프 [방법 1] [방법 2] 시작자료 선분자료
시작점 종착점 포인터 a b 1 d 3 2 c e 4 5 f 7 6 / 8 SQ LAB.

22 (예) 선분 리스트로의 표현 : 가중 그래프 a b c d e f 8 4 가중 그래프 5 2 1 3 6 [방법 1]
[방법 2] 시작자료 선분자료 시작점 종착점 가중치 포인터 a b 8 1 d 2 3 c 4 e 5 f 6 7 / SQ LAB.

23 인접 리스트 (Adjacency List )로의 표현
각 정점에 인접된 정점(들)의 집합을 각 각의 링크드 리스트로 표현 노드구조(1) 종착점 링크 노드구조(2) 가중치(들) SQ LAB.

24 (예) 인접 리스트로의 표현 : 방향 그래프 a b c d e f 방향 그래프 시작점 링크 (100) (120) a b d \
(200) c (300) e (400) (420) f (500) SQ LAB.

25 (예) 인접 리스트로의 표현 : 무방향 그래프 a b c d e f 무방향 그래프 시작점 링크 (100) (120) a b d
\ (200) (220) (240) (260) c e f (300) (400) (420) (500) (520) (540) (600) (620) SQ LAB.

26 (예) 인접 리스트로의 표현 : 가중 그래프 a b c d e f 8 4 가중 그래프 5 2 1 3 6 시작점 링크 (100)
(120) a b 8 d 2 \ (200) c 4 (300) e 3 (400) (420) 1 f 6 (500) 5 SQ LAB.

27 그래프의 순회 (Breadth First traverse) 깊이 우선 순회 (Depth First traverse)
넓이 우선 순회넓이 우선 순회 (Breadth First traverse) SQ LAB.

28 깊이 우선 순회 ① 시작할 노드(start vertex) 결정(첫 번째 방문 노드) ② 방문 ③ 방문 장소에 수록
④ 방문한(또는 방문된) 노드와 인접된 노드들 중에서 하나 선택 ⑤ 선택된 노드가 이미 방문되었으면 다른 인접 노드 선택(반복) ⑥ 선택된 노드 방문 ⑦ 방문 장소에 수록 ⑧ GoTo④ 방문된 노드를 수록할 장소가 확보되어 있어야 하며, 미처리 인접 노드는 스택(Stack)에 저장함 SQ LAB.

29 (예) 깊이 우선 순회 a b c d e f 방문 노드 Stack Push/Pop 상태 a b c e f d
시작 노드 d e f 방문 노드 Stack Push/Pop 상태 a b c e f d 인접노드 수 2 : push(a) 인접노드 수 3 : push(b) 인접노드 수 0 : pop(b) 인접노드 수 3 : push(e) f의 인접 노드 : pop(e) 모두 방문됨 d의 인접 노드 : pop(a) a의 인접 노드 : pop(/) b, a e, a / SQ LAB.

30 넓이 우선 순회 ① 시작할 노드 결정 또는 방문된 노드 중에서 하나 선택 ② 방문 ③ 방문 장소에 수록
④ 방문한 노드와 인접된 노드들 중 하나 선택  ⑤ 선택된 노드가 이미 방문되었으면 다른 노드 선택(반복) ⑥ 선택된 노드 방문 ⑦ 방문 장소에 수록 ⑧ 한 노드에 대한 인접 노드를 모두 방문했으면 GoTo①    아니면 GoTo④ 방문된 노드를 수록할 장소가 확보되어 있어야 하고, 방문된 인접 노드는 큐(Queue)에 저장한다. SQ LAB.

31 (예) 넓이 우선 순회 a b c d e f 방문 노드 Queue 동 작 상태 a b d c e f
시작 노드 d e f 방문 노드 Queue 동  작 상태 a b d c e f 선택 노드 b             Insert(b) 선택 노드 d             Insert(d) a의 인접 노드 모두 방문 delete(b) 선택 노드 c             Insert(c) 선택 노드 e              Insert(e) 선택 노드 f             Insert(f) b의 인접 노드 모두 방문 delete(d) d의 인접 노드 모두 방문 delete(c) c의 인접 노드 없슴      delete(e) e의 인접 노드 모두 방문 delete(f) f의 인접 노드 모두 방문 d,b c,d e,c,d f,e,c,d f,e,c f,e / SQ LAB.

32 트리(tree) SQ LAB.

33 뿌리를 가진 트리(Rooted Tree) ① 뿌리 노드(root node)가 존재하며
Root Node : in-degree = 0 ② 뿌리 노드를 제외한 n개의 노드들은 서로 분리된 집합 T1,T2,...,Tn으로 분할되며,      T1,T2,...,Tn도 각각 하나의 트리로 구성되며, 이들을 부트리(subtree)라 함. - 트리의 일반적 정의를 모두 수용하며 추가적으로 뿌리(근:root : indegree = 0)라는 특별한 노드(node)를 가지고 있으며, 트리를 구성하는 각 선분에 방향이 존재하며, 인접된 두 노드의 관계가 상하관계로 구성되어 계층적 구조(hierarchical structure)로 형성 - 뿌리를 가진 트리는 뿌리 노드로부터 시작하여 구성된 나무의 모양으로 표현 이때, 일반적으로 선분의 방향 표시는 생략 SQ LAB.

34 (예) 뿌리를 가진 트리 SQ LAB.

35 용어 정리 SQ LAB.

36 용어 정리 SQ LAB.

37 용어 정리 SQ LAB.

38 트리 종류 SQ LAB.

39 트리 종류 SQ LAB.

40 트리 종류 SQ LAB.

41 트리 순회 SQ LAB.

42 (예) 트리 순회 SQ LAB.

43 이진 트리(Binary Tree) SQ LAB.

44 이진 트리 종류 SQ LAB.

45 (예) 이진트리 종류 SQ LAB.

46 이진 트리 순회 SQ LAB.

47 (예) 이진트리 순회 SQ LAB.

48 이진 트리의 구현 SQ LAB.

49 quiz : 이진 트리의 구현 다음과 같은 자료를 처리할 수 있는 이진 트리를 - Linked list와 배열로 구현하시오.
번호 성명 SQ LAB.

50 이진 트리의 구현 (linked list) /*001*/ // BinaryTreeTraverse00
/*002*/ // complete or full binary tree creation and traverse /*003*/ // traverse : preOder, inOrder, postOrder /*004*/ /*005*/ #include <iostream> /*006*/ /*007*/ using namespace std; /*008*/ /*009*/ const int Max = 101; /*010*/ const int nil = 0; /*011*/ /*012*/ struct nodeType { /*013*/ nodeType *left_link; /*014*/ char *number; /*015*/ char *name; /*016*/ nodeType *right_link; /*017*/ }; /*018*/ SQ LAB.

51 /*019*/ class btree_class /*020*/ { /*021*/ private:
/*020*/ { /*021*/ private: /*022*/ nodeType *root; /*023*/ nodeType *parent; /*024*/ nodeType *current; /*025*/ public: /*026*/ btree_class() /*027*/ { /*028*/ root = new nodeType; /*029*/ root->left_link = root->right_link = nil; /*030*/ }; /*031*/ int btree_set(); /*032*/ void btree_preorder(); /*033*/ void preOrder(nodeType* root); /*034*/ void btree_inorder(); /*035*/ void inOrder(nodeType* root); /*036*/ void btree_postorder(); /*037*/ void postOrder(nodeType* root); /*038*/ }; /*039*/ SQ LAB.

52 /*040*/ int btree_class::btree_set() /*041*/ {
/*041*/ { /*042*/ FILE *input_file; /*043*/ char *buffer; /*044*/ int i; /*045*/ nodeType *parent; /*046*/ nodeType *new_node; /*047*/ nodeType *queue[Max]; /*048*/ int rear=0,front=0; /*049*/ char left_or_right; /*050*/ /*051*/ input_file = fopen("btree.dat","r"); /*052*/ if(input_file == NULL) /*053*/ { /*054*/ cout << " btree.dat not opened"; /*055*/ return 0; /*056*/ }; /*057*/ buffer = new char[18]; /*058*/ fgets(buffer,18,input_file); SQ LAB.

53 /*059*/ if(feof(input_file)) /*060*/ {
/*060*/ { /*061*/ cout << "Have no node in the 'btree.dat'"; /*062*/ root = nil; /*063*/ return 9; /*064*/ }; /*065*/ root->number = new char[5]; /*066*/ for(i=0;i<4;i++) root->number[i] = buffer[i]; /*067*/ root->number[i] = '\0'; /*068*/ root->name = new char[13]; /*069*/ for(i=0;buffer[i+4]!='\n';i++) root->name[i] = buffer[i+4]; /*070*/ root->name[i] = '\0'; /*071*/ rear = front = 1; /*072*/ queue[rear] = root; /*073*/ SQ LAB.

54 /*074*/ buffer = new char[18]; /*075*/ fgets(buffer,18,input_file);
/*076*/ left_or_right = 'l'; /*077*/ while(!feof(input_file)) /*078*/ { /*079*/ new_node = new nodeType; /*080*/ new_node->left_link = new_node->right_link = nil; /*081*/ new_node->number = new char[5]; /*082*/ for(i=0;i<4;i++) new_node->number[i] = buffer[i]; /*083*/ new_node->number[i] = '\0'; /*084*/ new_node->name = new char[13]; /*085*/ for(i=0;buffer[i+4]!='\n';i++) new_node->name[i] = buffer[i+4]; /*086*/ new_node->name[i] = '\0'; /*087*/ SQ LAB.

55 /*088*/ if(left_or_right == 'l') /*089*/ {
/*089*/ { /*090*/ parent = queue[front]; /*091*/ front = front + 1; /*092*/ parent->left_link = new_node; /*093*/ left_or_right = 'r'; /*094*/ } /*095*/ else /*096*/ { /*097*/ parent->right_link = new_node; /*098*/ left_or_right = 'l'; /*099*/ }; /*100*/ rear = rear + 1; /*101*/ queue[rear] = new_node; /*102*/ /*103*/ buffer = new char[18]; /*104*/ fgets(buffer,18,input_file); /*105*/ }; /*106*/ return 1; /*107*/ }; /*108*/ SQ LAB.

56 /*109*/ void btree_class::btree_preorder() /*110*/ {
/*110*/ { /*111*/ system("cls"); /*112*/ cout << "\n ==== pre order traverse ====\n"; /*113*/ /*114*/ preOrder(root); /*115*/ /*116*/ cout << "\n\n Type <Enter> : "; /*117*/ cin.get(); /*118*/ }; /*119*/ /*120*/ void btree_class::preOrder(nodeType* root) /*121*/ { /*122*/ if(root!=nil) /*123*/ { /*124*/ cout << "\n number : " << root->number /*125*/ << " name : " << root->name; /*126*/ /*127*/ preOrder(root->left_link); /*128*/ preOrder(root->right_link); /*129*/ } /*130*/ } /*131*/ SQ LAB.

57 /*132*/ void btree_class::btree_inorder() /*133*/ {
/*133*/ { /*134*/ system("cls"); /*135*/ cout << "\n\n ===== in order traverse =====\n"; /*136*/ /*137*/ inOrder(root); /*138*/ /*139*/ cout << "\n\n Type <Enter> : "; /*140*/ cin.get(); /*141*/ }; /*142*/ /*143*/ void btree_class::inOrder(nodeType* root) /*144*/ { /*145*/ if(root!=nil) /*146*/ { /*147*/ inOrder(root->left_link); /*148*/ /*149*/ cout << "\n number : " << root->number /*150*/ << " name : " << root->name; /*151*/ /*152*/ inOrder(root->right_link); /*153*/ } /*154*/ } /*155*/ SQ LAB.

58 /*159*/ cout << "\n\n === post order traverse ===\n"; /*160*/
/*157*/ { /*158*/ system("cls"); /*159*/ cout << "\n\n === post order traverse ===\n"; /*160*/ /*161*/ postOrder(root); /*162*/ }; /*163*/ /*164*/ void btree_class::postOrder(nodeType* root) /*165*/ { /*166*/ if(root!=nil) /*167*/ { /*168*/ postOrder(root->left_link); /*169*/ postOrder(root->right_link); /*170*/ /*171*/ cout << "\n number : " << root->number /*172*/ << " name : " << root->name; /*173*/ } /*174*/ } /*175*/ SQ LAB.

59 /*178*/ btree_class object; /*179*/ /*180*/ if(object.btree_set()==1)
/*176*/ void main() /*177*/ { /*178*/ btree_class object; /*179*/ /*180*/ if(object.btree_set()==1) /*181*/ { /*182*/ object.btree_preorder(); /*183*/ object.btree_inorder(); /*184*/ object.btree_postorder(); /*185*/ } /*186*/ /*187*/ cout << "\n\n\n Good Type <Enter> : "; /*188*/ cin.get(); /*189*/ } } SQ LAB.

60 이진 트리의 구현 (array) /*001*/ // BinaryTreeArray02
/*002*/ // complete or full binary tree creation and inorder traverse /*003*/ /*004*/ #include <iostream> /*005*/ /*006*/ using namespace std; /*007*/ /*008*/ const int Max = 101; /*009*/ /*010*/ struct nodeType { /*011*/ char *number; /*012*/ char *name; /*013*/ }; /*014*/ SQ LAB.

61 /*015*/ class binaryTreeClass /*016*/ { /*017*/ private:
/*016*/ { /*017*/ private: /*018*/ nodeType numberNname[Max]; /*019*/ int arrayMax; /*020*/ public: /*021*/ int binaryTreeSetting(); /*022*/ void binaryTreeInorder(); /*023*/ }; /*024*/ SQ LAB.

62 /*025*/ int binaryTreeClass::binaryTreeSetting() /*026*/ {
/*026*/ { /*027*/ FILE *inputFile; /*028*/ char *buffer; /*029*/ int i; /*030*/ /*031*/ inputFile = fopen("btree.dat","r"); /*032*/ if(inputFile == NULL) /*033*/ { /*034*/ cout << " btree.dat not opened"; /*035*/ return 0; /*036*/ }; /*037*/ buffer = new char[18]; /*038*/ fgets(buffer,18,inputFile); /*039*/ if(feof(inputFile)) /*040*/ { /*041*/ cout << "Have no node in the 'btree.dat'"; /*042*/ return 9; /*043*/ }; SQ LAB.

63 /*044*/ numberNname[1].number = new char[5];
/*045*/ for(i=0;i<4;i++) /*046*/ numberNname[1].number[i] = buffer[i]; /*047*/ numberNname[1].number[i] = '\0'; /*048*/ numberNname[1].name = new char[13]; /*049*/ for(i=0;buffer[i+4]!='\n';i++) /*050*/ numberNname[1].name[i] = buffer[i+4]; /*051*/ numberNname[1].name[i] = '\0'; /*052*/ SQ LAB.

64 /*053*/ buffer = new char[18]; /*054*/ fgets(buffer,18,inputFile);
/*055*/ arrayMax = 1; /*056*/ while(!feof(inputFile)) /*057*/ { /*058*/ arrayMax = arrayMax + 1; /*059*/ if(arrayMax > Max) /*060*/ { /*061*/ cout << "overflow error : " << arrayMax; /*062*/ return 8; /*063*/ } /*064*/ numberNname[arrayMax].number = new char[5]; /*065*/ for(i=0;i<4;i++) /*066*/ numberNname[arrayMax].number[i] = buffer[i]; /*067*/ numberNname[arrayMax].number[i] = '\0'; /*068*/ numberNname[arrayMax].name = new char[13]; /*069*/ for(i=0;buffer[i+4]!='\n';i++) /*070*/ numberNname[arrayMax].name[i] = buffer[i+4]; /*071*/ numberNname[arrayMax].name[i] = '\0'; /*072*/ /*073*/ buffer = new char[18]; /*074*/ fgets(buffer,18,inputFile); /*075*/ }; SQ LAB.

65 /*076*/ return 1; /*077*/ }; /*078*/ SQ LAB.

66 /*079*/ void binaryTreeClass::binaryTreeInorder() /*080*/ {
/*080*/ { /*081*/ int current; /*082*/ int stack[Max]; /*083*/ int top; /*084*/ /*085*/ top = 0; /*086*/ current = 1; /*087*/ while(top >= 0) /*088*/ { /*089*/ while(current <= arrayMax) /*090*/ { /*091*/ top = top + 1; /*092*/ stack[top] = current; /*093*/ current = current * 2; /*094*/ }; /*095*/ if(top < 1) break; /*096*/ current = stack[top]; /*097*/ top = top - 1; /*098*/ cout << "\n number : " << numberNname[current].number /*099*/ << " name : " << numberNname[current].name; /*100*/ current = current * 2 + 1; /*101*/ }; /*102*/ }; /*103*/ SQ LAB.

67 /*106*/ binaryTreeClass object; /*107*/
/*104*/ void main() /*105*/ { /*106*/ binaryTreeClass object; /*107*/ /*108*/ if(object.binaryTreeSetting()==1) /*109*/ object.binaryTreeInorder(); /*110*/ /*111*/ cout << "\n\n Good Type <Enter> : "; /*112*/ cin.get(); /*113*/ } SQ LAB.

68 이진 탐색 트리 SQ LAB.

69 이진 탐색 트리 SQ LAB.

70 quiz : 이진 탐색 트리의 구현 다음과 같은 자료를 처리할 수 있는 이진 탐색 트리를 - Linked list와 배열로
구현하시오. 자료 번호 성명 SQ LAB.

71 균형 이진 탐색 트리 SQ LAB.

72 (예) 균형 이진 탐색 트리 SQ LAB.

73 (예) 불균형 이진 탐색 트리 SQ LAB.