Download presentation
Presentation is loading. Please wait.
1
C언어 응용 제11주 실습 해보기 제9장 그래프1
2
실습 내용 예제 9-1 그래프의 인접행렬 표현 예제 9-2 그래프의 인접리스트 표현 예제 9-3 그래프의 깊이우선 탐색
예제 9-4 그래프의 너비우선 탐색
3
예제 9-1 실습하기 행렬을 이용한 그래프 구현 그래프를 구현한 소스파일과 헤더파일을 따로 작 성한다. 구현한 함수 목록
initializeGraph : 그래프를 초기화하는 함수 insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수
4
실습내용 우측 그림과 같은 4 개의 그래프를 인접 행렬로 구현한 후 인 접행렬을 출력한다. 해야할일
우측 그림과 같은 4 개의 그래프를 인접 행렬로 구현한 후 인 접행렬을 출력한다. 해야할일 인접행렬로 구현한 그 래프형 구조체 선언 그래프를 구성하기 위 한 함수들 구현 이를 테스트하는 main 함수 구현
5
소스 목록 및 내용 adjgraph.h : 그래프구현에 필요한 자료형과 함수 의 원형을 선언하는 헤더 파일
adjgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 ex0901.c : 그래프를 테스트하는 main 소스 파일
6
실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 adjgraph.h 파일 작성 adjgraph.c 파일 작성 ex0901.c 작성 빌드 및 실행 결과 확인
7
소스들 사이의 연관 관계 adjgraph.h ex0901.c 그래프 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다.
구현된 그래프를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. adjgraph.c 그래프 구현에 필요한 함수의 내용을 작성한다.
8
main 소스 코드 그래프를 만들고 인접행렬을 출력한다.
9
Eclipse 실행 D:\Lec_hwl\CApp\y2014
10
Eclipse 실행
11
Workspace 확인 D:\Lec_hwl\CApp\y2014
12
CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음
13
CDT Perspective 확인 C/C++ 선택
14
CDT Perspective 확인 C/C++ 로 되어 있음
15
이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다.
다음 슬라이드에 설명한 바대로 빈 프로젝트를 만 든다.
16
새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것
17
프로젝트 명 설정 Ch0901 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0901
18
프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용
19
생성된 빈 프로젝트 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다.
이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음
20
adjgraph.h 추가 및 작성 Header File 선택
21
adjgraph.h 추가 및 작성 Ch0901 프로젝트명 설정(자동설정) adjgraph.h 헤더 파일 명 설정
22
adjgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치
23
adjgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다.
인접행렬로 구현한 그래프를 표현하는 구조체. 인접행렬의 크기는 최대 정점의 수로 한다. 인접행렬로 구현한 그래프와 연관된 함수 들의 원형
24
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 adjgraph
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 adjgraph.c 를 작성한다.
25
adjgraph.c 추가 및 작성 Source File 선택
26
adjgraph.c 추가 및 작성 Ch0901 프로젝트명 확인(자동설정) adjgraph.c 소스 파일명 설정
27
adjgraph.c 추가 및 작성 자동 생성된 빈 소스 파일
우측 그림과 같이 자동생 성된 빈 소스파일에 필요 한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현
28
adjgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.
29
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.
30
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.
31
insertVertex() 함수 그래프에 정점을 추가한다.
인접행렬로 구현한 그래프는 정점의 추가가 정점 의 수만 늘려 주면 된다.
32
insertVertex() 함수 그래프에 정점을 추가한다.
인접행렬로 구현한 그래프는 정점의 추가가 정점 의 수만 늘려 주면 된다.
33
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 행렬의 요소 값을 1로 설정하면 된다.
34
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 행렬의 요소 값을 1로 설정하면 된다.
35
printGraph() 함수 그래프를 출력한다.
36
printGraph() 함수 그래프를 출력한다.
37
이제 그래프를 구현하는 구조체와 그와 연관된 함 수들을 모두 작성했으므로 그래프를 생성하고 출 력해 보는 함수를 작성할 것이다.
이 소스는 ex0901.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1, G2, G3, G4를 생성하고 출 력하여 확인한다.
38
ex0901.c 추가 및 작성 Source File 선택
39
ex0901.c 추가 및 작성 Ch0901 프로젝트명 확인(자동설정) ex0901.c 소스 파일명 설정
40
추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0901.c, adjgraph.c, adjgraph.h
가 추가된 것을 확인할 수 있다.
41
main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 그래프 관련 함수 헤더
42
main 함수 우측 그림과 같은 그 래프를 만들고 출력 을 한다.
43
main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.
44
G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->B 간선 추가
A->D 간선 추가
45
G2,G3, G4를 생성하는 함수
46
빌드 및 실행 결과
47
도전 문제 위 예제에서 printGraph() 함수를 수정하여 각 노 드의 차수를 각 행의 마지막에 출력하도록 하시오.
위 예제를 활용하여 다음 그래프를 작성하고 인접 행렬을 출력하는 프로그램을 작성하시오.
49
예제 9-2 실습하기 연결리스트를 이용한 그래프 구현 그래프를 구현한 소스파일과 헤더파일을 따로 작 성한다. 구현한 함수 목록
initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수
50
실습내용 우측 그림과 같은 4 개의 그래프를 연결 리스트로 구현한 후 인접정보를 출력한 다. 해야할일
우측 그림과 같은 4 개의 그래프를 연결 리스트로 구현한 후 인접정보를 출력한 다. 해야할일 연결리스트로 구현한 그래프형 구조체 선언 그래프를 구성하기 위 한 함수들 구현 이를 테스트하는 main 함수 구현
51
소스 목록 및 내용 linkgraph.h : 그래프구현에 필요한 자료형과 함 수의 원형을 선언하는 헤더 파일
linkgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 ex0902.c : 그래프를 테스트하는 main 소스 파일 정점의 수 정점 데이터 다음 정점 노드 포인터 각 정점의 헤드 노드 배열
52
실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 linkgraph.h 파일 작성 linkgraph.c 파일 작성 ex0902.c 작성 빌드 및 실행 결과 확인
53
소스들 사이의 연관 관계 linkgraph.h ex0902.c 그래프 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다.
구현된 그래프를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. linkgraph.c 그래프 구현에 필요한 함수의 내용을 작성한다.
54
main 소스 코드 그래프를 만들고 인접정보를 출력한다.
55
Eclipse 실행 D:\Lec_hwl\CApp\y2014
56
Eclipse 실행
57
Workspace 확인 D:\Lec_hwl\CApp\y2014
58
CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음
59
CDT Perspective 확인 C/C++ 선택
60
CDT Perspective 확인 C/C++ 로 되어 있음
61
이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다.
다음 슬라이드에 설명한 바 대로 빈 프로젝트를 만 든다.
62
새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것
63
프로젝트 명 설정 Ch0902 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0902
64
프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용
65
생성된 빈 프로젝트 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다.
Ch0902 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음
66
linkgraph.h 추가 및 작성 Header File 선택
67
linkgraph.h 추가 및 작성 Ch0902 프로젝트명 설정(자동설정) linkgraph.h 헤더 파일 명 설정
68
linkgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치
69
linkgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다.
그래프의 정점을 연결리스트로 구현하기 위한 노드 구조체 연결리스트로 구현한 그래프 구조체 정점 노드 배열의 크기는 최대 정점의 수로 했다. 연결리스트로로 구현한 그래프와 연관된 함수 들의 원형
70
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph.c 를 작성한다.
71
linkgraph.c 추가 및 작성 Source File 선택
72
linkgraph.c 추가 및 작성 Ch0902 프로젝트명 확인(자동설정) linkgraph.c 소스 파일명 설정
73
linkgraph.c 추가 및 작성 자동 생성된 빈 소스 파일
아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현
74
linkgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.
75
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.
76
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.
77
clearGraph() 함수 그래프가 사용하는 메모리를 반환한다.
78
freeList() 함수 연결리스트가 사용하는 메모리를 반환한다.
79
insertVertex() 함수 그래프에 정점을 추가한다.
연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.
80
insertVertex() 함수 그래프에 정점을 추가한다.
연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.
81
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.
82
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.
83
printGraph() 함수 그래프를 출력한다.
84
printGraph() 함수 그래프를 출력한다.
85
이제 그래프를 구현하는 구조체와 그와 연관된 함 수들을 모두 작성했으므로 그래프를 생성하고 출 력해 보는 함수를 작성할 것이다.
이 소스는 ex0902.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1, G2, G3, G4를 생성하고 출 력하여 확인한다.
86
ex0902.c 추가 및 작성 Source File 선택
87
ex0902.c 추가 및 작성 Ch0902 프로젝트명 확인(자동설정) ex0902.c 소스 파일명 설정
88
추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0902.c, linkgraph.c, linkgraph.h
가 추가된 것을 확인할 수 있다.
89
main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 그래프 관련 함수 헤더
90
main 함수 우측 그림과 같은 그 래프를 만들고 출력 을 한다.
91
main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.
92
G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->D 간선 추가
인접리스트를 오름차순으로 추가 하기 위하여 큰 노드와 연결된 정보를 먼저 추가함.
93
G2,G3, G4를 생성하는 함수
94
빌드 및 실행 결과
95
도전 문제 위 예제에서 printGraph() 함수를 수정하여 각 노 드의 차수를 각 행의 마지막에 출력하도록 하시오.
위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하는 프로그램을 작성하시오.
97
예제 9-3 실습하기 인접리스트를 이용해 구현한 그래프의 깊이우선 탐색 프로그램
인접리스트를 이용해 구현한 그래프의 깊이우선 탐색 프로그램 그래프를 구현한 소스파일과 헤더파일, 탐색을 위 한 스택을 위한 소스 및 헤더파일을 따로 작성한다. 구현한 함수 목록(그래프 관련) initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수 dfsTraversal : 깊이우선 방법으로 그래프 탐색
98
예제 9-3 실습하기 구현한 함수 목록(스택 관련) push : 스택에 자료 추가 pop : 스택에서 자료 삭제
clearStack : 스택이 사용한 메모리 반환 isEmpty : 스택이 비었는지를 판단하는 함수
99
실습내용 우측 그림과 같은 그래프를 연 결리스트로 구현한 후 깊이우선 탐색 결과를 출력한다. 해야할일
우측 그림과 같은 그래프를 연 결리스트로 구현한 후 깊이우선 탐색 결과를 출력한다. 해야할일 연결리스트로 구현한 그래프형 구 조체 선언 그래프를 구성하기 위한 함수들 구 현 탐색을 위한 스택 구조체 선언 스택에 필요한 함수 구현 깊이 우선 탐색 결과를 출력하는 main함수 구현
100
소스 목록 및 내용 linkgraph.h : 그래프구현에 필요한 자료형과 함수의 원형을 선 언하는 헤더 파일
linkgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 linkstack.h : 스택구현에 필요한 자료형과 함수 원형 을 선언하 는 헤더 linkstack.c : 스택을 구현한 소스 파일 ex0903.c : 그래프를 테스트하는 main 소스 파일 정점의 수 정점 데이터 다음 정점 노드 포인터 각 정점의 헤드 노드 배열 각 정점의 방문 정보 배열
101
실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective는 C/C++ 이어야 한다. 프로젝트 생성 linkstack.h 파일 작성 linkstack.c 파일 작성 linkgraph.h 파일 작성 linkgraph.c 파일 작성 ex0903.c 작성 빌드 및 실행 결과 확인
102
소스들 사이의 연관 관계 linkgraph.h, linkstack.h ex0903.c
그래프와 스택 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. ex0903.c 구현된 그래프를 깊이우선 탐색하는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. linkgraph.c, linkstack.c 그래프와 스택 구현에 필요한 함수의 내용을 작성한다.
103
main 소스 코드 그래프를 만들고 깊이우선 탐색 결과를 출력한다.
104
Eclipse 실행 D:\Lec_hwl\CApp\y2014
105
Eclipse 실행
106
Workspace 확인 D:\Lec_hwl\CApp\y2014
107
CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음
108
CDT Perspective 확인 C/C++ 선택
109
CDT Perspective 확인 C/C++ 로 되어 있음
110
이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다.
다음 슬라이드에 설명한 바 대로 빈 프로젝트를 만 든다.
111
새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것
112
프로젝트 명 설정 Ch0903 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0903
113
프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용
114
생성된 빈 프로젝트 Ch0903 이제 빈 프로젝트가 생성 되었으므로 스택구현을 위한 구조체와 함수 원형을 선언한 헤더와 그래프 를 구현하기 위한 구조체와 함수 원형을 선언한 헤 더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음
115
linkstack.h 추가 및 작성 Header File 선택
116
linkstack.h 추가 및 작성 Ch0903 프로젝트명 설정(자동설정) linkstack.h 헤더 파일 명 설정
117
linkstack.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치
118
linkstack.h 추가 및 작성 스택 구조체 및 함수 원형 선언 스택을 연결리스트로 구현하기 위한 노드 구조체
연결리스트로 구현한 스택과 연관된 함수 들의 원형
119
이제 스택을 구현하기 위한 구조체와 관련 함수의 원형을 선언했으므로 함수의 내용을 작성할 소스 linkstack
이제 스택을 구현하기 위한 구조체와 관련 함수의 원형을 선언했으므로 함수의 내용을 작성할 소스 linkstack.c 를 작성한다. 스택은 항상 자료의 입출력 창구인 top 변수가 있 어야 한다. 스택을 구현하기 위하여 이 변수를 linkstack.c 의 전역 변수로 선언하고 NULL 로 초 기화 한다. 스택과 연관한 모든 함수는 이 전역변수 top을 참 조한다.
120
linkstack.c 추가 및 작성 Source File 선택
121
linkstack.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) linkstack.c 소스 파일명 설정
122
linkstack.c 추가 및 작성 자동 생성된 빈 소스 파일
아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현
123
linkstack.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 스택관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.
124
push() 함수
125
pop 함수
126
clearStack 함수 남아있는 자료가 있는 경우 메모리를 반환한다.
127
isEmpty() 함수
128
이제 탐색을 위한 스택을 구현했으므로 인접리스 트를 이용한 그래프를 구할 차례이다.
다음의 내용은 예제 9-2와 거의 동일하며, 탐색을 위하여 구조체와 함수를 일부 수정한다.
129
linkgraph.h 추가 및 작성 Header File 선택
130
linkgraph.h 추가 및 작성 Ch0903 프로젝트명 설정(자동설정) linkgraph.h 헤더 파일 명 설정
131
linkgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일
헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치
132
linkgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다.
그래프의 정점을 연결리스트로 구현하기 위한 노드 구조체 연결리스트로 구현한 그래프 구조체 정점 노드 배열의 크기는 최대 정점의 수로 했다. 연결리스트로로 구현한 그래프와 연관된 함수 들의 원형
133
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph
이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph.c 를 작성한다.
134
linkgraph.c 추가 및 작성 Source File 선택
135
linkgraph.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) linkgraph.c 소스 파일명 설정
136
linkgraph.c 추가 및 작성 자동 생성된 빈 소스 파일
아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현
137
linkgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성)
표준 입출력 함수 헤더 메모리 할당 함수 헤더 스택관련 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.
138
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.
139
initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.
140
clearGraph() 함수 그래프가 사용하는 메모리를 반환한다.
141
freeList() 함수 연결리스트가 사용하는 메모리를 반환한다.
142
insertVertex() 함수 그래프에 정점을 추가한다.
연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.
143
insertVertex() 함수 그래프에 정점을 추가한다.
연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.
144
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.
145
insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.
146
printGraph() 함수 그래프를 출력한다.
147
printGraph() 함수 그래프를 출력한다.
148
dfsTraversal() 함수 깊이우선 방법으로 주어진 정점으로 부터 탐색을 시작한다.
149
dfsTraversal() 함수
150
이제 스택을 구현하는 구조체와 연관된 함수들과 그래프를 구현하는 구조체와 그와 연관된 함수들 을 모두 작성했으므로 그래프를 생성하고 깊이우 선 탐색 결과를 출력해 보는 함수를 작성할 것이 다. 이 소스는 ex0903.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1을 생성하고 깊이 우선 탐색 을 출력하여 확인한다.
151
ex0903.c 추가 및 작성 Source File 선택
152
ex0903.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) ex0903.c 소스 파일명 설정
153
추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0903.c, linkstack.h, linkstack.c, linkgraph.c, linkgraph.h 가 추가된 것을 확인할 수 있다.
154
main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 스택 관련 함수 헤더
그래프 관련 함수 헤더
155
main 함수 우측 그림과 같은 그래프 를 만들고 깊이우선 탐색 출력을 한다.
156
main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.
157
G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->D 간선 추가
인접리스트를 오름차순으로 추가 하기 위하여 큰 노드와 연결된 정보를 먼저 추가함.
158
G2,G3, G4를 생성하는 함수
159
빌드 및 실행 결과
160
도전 문제 위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하고 깊이우선 탐색 결과를 출력하는 프로그램을 작성하시오.
162
예제 9-4 실습하기 인접리스트를 이용해 구현한 그래프의 너비우선 탐색 프로그램
인접리스트를 이용해 구현한 그래프의 너비우선 탐색 프로그램 그래프를 구현한 소스파일과 헤더파일, 탐색을 위 한 스택을 위한 소스 및 헤더파일을 따로 작성한 다. 구현한 함수 목록(그래프 관련) initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수 bfsTraversal : 너비우선 방법으로 그래프 탐색
163
예제 9-4 실습하기 구현한 함수 목록(큐 관련) createQueue : 큐를 생성하는 함수
enQueue : 큐에 자료 추가 deQueue : 큐에서 자료 삭제 clearQueue : 큐가 사용한 메모리 반환 isEmpty : 큐가 비었는지를 판단하는 함수
164
예제 9-3과 책의 예제 9-4의 소스를 참고하여 예 제 9-4를 완성할 것
165
도전 문제 위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하고 너비우선 탐색 결과를 출력하는 프로그램을 작성하시오.
Similar presentations