C언어 응용 제11주 실습 해보기 제9장 그래프1

실습 내용 예제 9-1 그래프의 인접행렬 표현 예제 9-2 그래프의 인접리스트 표현 예제 9-3 그래프의 깊이우선 탐색 예제 9-4 그래프의 너비우선 탐색

예제 9-1 실습하기 행렬을 이용한 그래프 구현 그래프를 구현한 소스파일과 헤더파일을 따로 작 성한다. 구현한 함수 목록 initializeGraph : 그래프를 초기화하는 함수 insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수

실습내용 우측 그림과 같은 4 개의 그래프를 인접 행렬로 구현한 후 인 접행렬을 출력한다. 해야할일 우측 그림과 같은 4 개의 그래프를 인접 행렬로 구현한 후 인 접행렬을 출력한다. 해야할일 인접행렬로 구현한 그 래프형 구조체 선언 그래프를 구성하기 위 한 함수들 구현 이를 테스트하는 main 함수 구현

소스 목록 및 내용 adjgraph.h : 그래프구현에 필요한 자료형과 함수 의 원형을 선언하는 헤더 파일 adjgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 ex0901.c : 그래프를 테스트하는 main 소스 파일

실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 adjgraph.h 파일 작성 adjgraph.c 파일 작성 ex0901.c 작성 빌드 및 실행 결과 확인

소스들 사이의 연관 관계 adjgraph.h ex0901.c 그래프 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. 구현된 그래프를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. adjgraph.c 그래프 구현에 필요한 함수의 내용을 작성한다.

main 소스 코드 그래프를 만들고 인접행렬을 출력한다.

Eclipse 실행 D:\Lec_hwl\CApp\y2014

Eclipse 실행

Workspace 확인 D:\Lec_hwl\CApp\y2014

CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

CDT Perspective 확인 C/C++ 선택

CDT Perspective 확인 C/C++ 로 되어 있음

이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다. 다음 슬라이드에 설명한 바대로 빈 프로젝트를 만 든다.

새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

프로젝트 명 설정 Ch0901 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0901

프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

생성된 빈 프로젝트 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

adjgraph.h 추가 및 작성 Header File 선택

adjgraph.h 추가 및 작성 Ch0901 프로젝트명 설정(자동설정) adjgraph.h 헤더 파일 명 설정

adjgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일 헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

adjgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다. 인접행렬로 구현한 그래프를 표현하는 구조체. 인접행렬의 크기는 최대 정점의 수로 한다. 인접행렬로 구현한 그래프와 연관된 함수 들의 원형

이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 adjgraph 이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 adjgraph.c 를 작성한다.

adjgraph.c 추가 및 작성 Source File 선택

adjgraph.c 추가 및 작성 Ch0901 프로젝트명 확인(자동설정) adjgraph.c 소스 파일명 설정

adjgraph.c 추가 및 작성 자동 생성된 빈 소스 파일 우측 그림과 같이 자동생 성된 빈 소스파일에 필요 한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현

adjgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성) 표준 입출력 함수 헤더 메모리 할당 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.

insertVertex() 함수 그래프에 정점을 추가한다. 인접행렬로 구현한 그래프는 정점의 추가가 정점 의 수만 늘려 주면 된다.

insertVertex() 함수 그래프에 정점을 추가한다. 인접행렬로 구현한 그래프는 정점의 추가가 정점 의 수만 늘려 주면 된다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 행렬의 요소 값을 1로 설정하면 된다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 행렬의 요소 값을 1로 설정하면 된다.

printGraph() 함수 그래프를 출력한다.

printGraph() 함수 그래프를 출력한다.

이제 그래프를 구현하는 구조체와 그와 연관된 함 수들을 모두 작성했으므로 그래프를 생성하고 출 력해 보는 함수를 작성할 것이다. 이 소스는 ex0901.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1, G2, G3, G4를 생성하고 출 력하여 확인한다.

ex0901.c 추가 및 작성 Source File 선택

ex0901.c 추가 및 작성 Ch0901 프로젝트명 확인(자동설정) ex0901.c 소스 파일명 설정

추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0901.c, adjgraph.c, adjgraph.h 가 추가된 것을 확인할 수 있다.

main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 그래프 관련 함수 헤더

main 함수 우측 그림과 같은 그 래프를 만들고 출력 을 한다.

main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.

G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->B 간선 추가 A->D 간선 추가

G2,G3, G4를 생성하는 함수

빌드 및 실행 결과

도전 문제 위 예제에서 printGraph() 함수를 수정하여 각 노 드의 차수를 각 행의 마지막에 출력하도록 하시오. 위 예제를 활용하여 다음 그래프를 작성하고 인접 행렬을 출력하는 프로그램을 작성하시오.

예제 9-2 실습하기 연결리스트를 이용한 그래프 구현 그래프를 구현한 소스파일과 헤더파일을 따로 작 성한다. 구현한 함수 목록 initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수

실습내용 우측 그림과 같은 4 개의 그래프를 연결 리스트로 구현한 후 인접정보를 출력한 다. 해야할일 우측 그림과 같은 4 개의 그래프를 연결 리스트로 구현한 후 인접정보를 출력한 다. 해야할일 연결리스트로 구현한 그래프형 구조체 선언 그래프를 구성하기 위 한 함수들 구현 이를 테스트하는 main 함수 구현

소스 목록 및 내용 linkgraph.h : 그래프구현에 필요한 자료형과 함 수의 원형을 선언하는 헤더 파일 linkgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 ex0902.c : 그래프를 테스트하는 main 소스 파일 정점의 수 정점 데이터 다음 정점 노드 포인터 각 정점의 헤드 노드 배열

실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective 는 C/C++ 이어야 한다. 프로젝트 생성 linkgraph.h 파일 작성 linkgraph.c 파일 작성 ex0902.c 작성 빌드 및 실행 결과 확인

소스들 사이의 연관 관계 linkgraph.h ex0902.c 그래프 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. 구현된 그래프를 테스트 해보는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. linkgraph.c 그래프 구현에 필요한 함수의 내용을 작성한다.

main 소스 코드 그래프를 만들고 인접정보를 출력한다.

Eclipse 실행 D:\Lec_hwl\CApp\y2014

Eclipse 실행

Workspace 확인 D:\Lec_hwl\CApp\y2014

CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

CDT Perspective 확인 C/C++ 선택

CDT Perspective 확인 C/C++ 로 되어 있음

이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다. 다음 슬라이드에 설명한 바 대로 빈 프로젝트를 만 든다.

새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

프로젝트 명 설정 Ch0902 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0902

프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

생성된 빈 프로젝트 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. Ch0902 이제 빈 프로젝트가 생성 되었으므로 그래프를 구 현하기 위한 구조체와 함수 원형을 선언한 헤더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

linkgraph.h 추가 및 작성 Header File 선택

linkgraph.h 추가 및 작성 Ch0902 프로젝트명 설정(자동설정) linkgraph.h 헤더 파일 명 설정

linkgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일 헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

linkgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다. 그래프의 정점을 연결리스트로 구현하기 위한 노드 구조체 연결리스트로 구현한 그래프 구조체 정점 노드 배열의 크기는 최대 정점의 수로 했다. 연결리스트로로 구현한 그래프와 연관된 함수 들의 원형

이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph 이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph.c 를 작성한다.

linkgraph.c 추가 및 작성 Source File 선택

linkgraph.c 추가 및 작성 Ch0902 프로젝트명 확인(자동설정) linkgraph.c 소스 파일명 설정

linkgraph.c 추가 및 작성 자동 생성된 빈 소스 파일 아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현

linkgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성) 표준 입출력 함수 헤더 메모리 할당 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.

clearGraph() 함수 그래프가 사용하는 메모리를 반환한다.

freeList() 함수 연결리스트가 사용하는 메모리를 반환한다.

insertVertex() 함수 그래프에 정점을 추가한다. 연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.

insertVertex() 함수 그래프에 정점을 추가한다. 연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.

printGraph() 함수 그래프를 출력한다.

printGraph() 함수 그래프를 출력한다.

이제 그래프를 구현하는 구조체와 그와 연관된 함 수들을 모두 작성했으므로 그래프를 생성하고 출 력해 보는 함수를 작성할 것이다. 이 소스는 ex0902.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1, G2, G3, G4를 생성하고 출 력하여 확인한다.

ex0902.c 추가 및 작성 Source File 선택

ex0902.c 추가 및 작성 Ch0902 프로젝트명 확인(자동설정) ex0902.c 소스 파일명 설정

추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0902.c, linkgraph.c, linkgraph.h 가 추가된 것을 확인할 수 있다.

main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 그래프 관련 함수 헤더

main 함수 우측 그림과 같은 그 래프를 만들고 출력 을 한다.

main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.

G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->D 간선 추가 인접리스트를 오름차순으로 추가 하기 위하여 큰 노드와 연결된 정보를 먼저 추가함.

G2,G3, G4를 생성하는 함수

빌드 및 실행 결과

도전 문제 위 예제에서 printGraph() 함수를 수정하여 각 노 드의 차수를 각 행의 마지막에 출력하도록 하시오. 위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하는 프로그램을 작성하시오.

예제 9-3 실습하기 인접리스트를 이용해 구현한 그래프의 깊이우선 탐색 프로그램 인접리스트를 이용해 구현한 그래프의 깊이우선 탐색 프로그램 그래프를 구현한 소스파일과 헤더파일, 탐색을 위 한 스택을 위한 소스 및 헤더파일을 따로 작성한다. 구현한 함수 목록(그래프 관련) initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수 dfsTraversal : 깊이우선 방법으로 그래프 탐색

예제 9-3 실습하기 구현한 함수 목록(스택 관련) push : 스택에 자료 추가 pop : 스택에서 자료 삭제 clearStack : 스택이 사용한 메모리 반환 isEmpty : 스택이 비었는지를 판단하는 함수

실습내용 우측 그림과 같은 그래프를 연 결리스트로 구현한 후 깊이우선 탐색 결과를 출력한다. 해야할일 우측 그림과 같은 그래프를 연 결리스트로 구현한 후 깊이우선 탐색 결과를 출력한다. 해야할일 연결리스트로 구현한 그래프형 구 조체 선언 그래프를 구성하기 위한 함수들 구 현 탐색을 위한 스택 구조체 선언 스택에 필요한 함수 구현 깊이 우선 탐색 결과를 출력하는 main함수 구현

소스 목록 및 내용 linkgraph.h : 그래프구현에 필요한 자료형과 함수의 원형을 선 언하는 헤더 파일 linkgraph.c : 그래프구현에 필요한 함수의 내용을 작성한 소스 linkstack.h : 스택구현에 필요한 자료형과 함수 원형 을 선언하 는 헤더 linkstack.c : 스택을 구현한 소스 파일 ex0903.c : 그래프를 테스트하는 main 소스 파일 정점의 수 정점 데이터 다음 정점 노드 포인터 각 정점의 헤드 노드 배열 각 정점의 방문 정보 배열

실습하는 순서 Eclipse 를 실행한다. Workspace와 Perspective가 맞는지 확인 하고 맞지 않으면 수정한다. Workspace 는 D:\Lec_hwlee\Capp\y2014 이고 Perspective는 C/C++ 이어야 한다. 프로젝트 생성 linkstack.h 파일 작성 linkstack.c 파일 작성 linkgraph.h 파일 작성 linkgraph.c 파일 작성 ex0903.c 작성 빌드 및 실행 결과 확인

소스들 사이의 연관 관계 linkgraph.h, linkstack.h ex0903.c 그래프와 스택 구현에 필요한 구조체와 필요한 함수의 원형을 선언한다. ex0903.c 구현된 그래프를 깊이우선 탐색하는 main 소스 포함한다. 포함한다. 실제 함수를 호출하여 사용한다. linkgraph.c, linkstack.c 그래프와 스택 구현에 필요한 함수의 내용을 작성한다.

main 소스 코드 그래프를 만들고 깊이우선 탐색 결과를 출력한다.

Eclipse 실행 D:\Lec_hwl\CApp\y2014

Eclipse 실행

Workspace 확인 D:\Lec_hwl\CApp\y2014

CDT Perspective 확인 이 버튼을 클릭해서 수정 Java EE 로 되어 있음

CDT Perspective 확인 C/C++ 선택

CDT Perspective 확인 C/C++ 로 되어 있음

이제 프로그램을 작성할 준비가 되었으므로 실행 파일을 작성할 프로젝트를 생성한다. 다음 슬라이드에 설명한 바 대로 빈 프로젝트를 만 든다.

새 프로젝트 생성 File->New->C Project 반드시 C Project를 택할 것

프로젝트 명 설정 Ch0903 Empty Project Cygwin GCC D:\Lec_hwl\capp\y2014\Ch0903

프로젝트 구성 설정 Debug 버전과 Release 버전 모두 사용

생성된 빈 프로젝트 Ch0903 이제 빈 프로젝트가 생성 되었으므로 스택구현을 위한 구조체와 함수 원형을 선언한 헤더와 그래프 를 구현하기 위한 구조체와 함수 원형을 선언한 헤 더를 추가한다. 본인 컴퓨터의 사양에 따라 내용은 약간씩 다를 수 있음

linkstack.h 추가 및 작성 Header File 선택

linkstack.h 추가 및 작성 Ch0903 프로젝트명 설정(자동설정) linkstack.h 헤더 파일 명 설정

linkstack.h 추가 및 작성 자동 생성된 빈 헤더 파일 헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

linkstack.h 추가 및 작성 스택 구조체 및 함수 원형 선언 스택을 연결리스트로 구현하기 위한 노드 구조체 연결리스트로 구현한 스택과 연관된 함수 들의 원형

이제 스택을 구현하기 위한 구조체와 관련 함수의 원형을 선언했으므로 함수의 내용을 작성할 소스 linkstack 이제 스택을 구현하기 위한 구조체와 관련 함수의 원형을 선언했으므로 함수의 내용을 작성할 소스 linkstack.c 를 작성한다. 스택은 항상 자료의 입출력 창구인 top 변수가 있 어야 한다. 스택을 구현하기 위하여 이 변수를 linkstack.c 의 전역 변수로 선언하고 NULL 로 초 기화 한다. 스택과 연관한 모든 함수는 이 전역변수 top을 참 조한다.

linkstack.c 추가 및 작성 Source File 선택

linkstack.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) linkstack.c 소스 파일명 설정

linkstack.c 추가 및 작성 자동 생성된 빈 소스 파일 아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현

linkstack.c 추가 및 작성 필요한 코드 작성(빈 함수 작성) 표준 입출력 함수 헤더 메모리 할당 함수 헤더 스택관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

push() 함수

pop 함수

clearStack 함수 남아있는 자료가 있는 경우 메모리를 반환한다.

isEmpty() 함수

이제 탐색을 위한 스택을 구현했으므로 인접리스 트를 이용한 그래프를 구할 차례이다. 다음의 내용은 예제 9-2와 거의 동일하며, 탐색을 위하여 구조체와 함수를 일부 수정한다.

linkgraph.h 추가 및 작성 Header File 선택

linkgraph.h 추가 및 작성 Ch0903 프로젝트명 설정(자동설정) linkgraph.h 헤더 파일 명 설정

linkgraph.h 추가 및 작성 자동 생성된 빈 헤더 파일 헤더가 여러 소스에서 포함되었을 때 이중으로 포함되지 않도록 하는 매크로 실제 헤더의 내용이 들어갈 위치

linkgraph.h 추가 및 작성 그래프 구조체 및 함수 원형 선언 최대 정점의 수를 30으로 한다. 그래프의 정점을 연결리스트로 구현하기 위한 노드 구조체 연결리스트로 구현한 그래프 구조체 정점 노드 배열의 크기는 최대 정점의 수로 했다. 연결리스트로로 구현한 그래프와 연관된 함수 들의 원형

이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph 이제 그래프를 구현하기 위한 구조체와 관련 함수 의 원형을 선언했으므로 함수의 내용을 작성할 소 스 linkgraph.c 를 작성한다.

linkgraph.c 추가 및 작성 Source File 선택

linkgraph.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) linkgraph.c 소스 파일명 설정

linkgraph.c 추가 및 작성 자동 생성된 빈 소스 파일 아래 그림과 같이 자동생성된 빈 소스파일에 필 요한 코드를 추가한다. 필요한 헤더 추가 선언된 각 함수 구현

linkgraph.c 추가 및 작성 필요한 코드 작성(빈 함수 작성) 표준 입출력 함수 헤더 메모리 할당 함수 헤더 스택관련 함수 헤더 그래프관련 함수 헤더 필요한 각 함수의 원형에 맞게 함수의 몸체를 작성하되, 내용은 모두 빈 것으로 작성한다. 차후에 한 함수씩 코드의 내용을 작성한다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다. 이 함수가 하는 일을 기술하면 다음과 같다.

initializeGraph() 함수 매개변수로 주어진 그래프를 초기화 한다.

clearGraph() 함수 그래프가 사용하는 메모리를 반환한다.

freeList() 함수 연결리스트가 사용하는 메모리를 반환한다.

insertVertex() 함수 그래프에 정점을 추가한다. 연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.

insertVertex() 함수 그래프에 정점을 추가한다. 연결리스트로 구현한 그래프는 정점의 추가가 정 점의 수만 늘려 주면 된다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.

insertEdge() 함수 그래프에 간선을 추가한다. 간선을 추가하는 것은 해당하는 정점노드에 새로 운 노드를 추가한다.

printGraph() 함수 그래프를 출력한다.

printGraph() 함수 그래프를 출력한다.

dfsTraversal() 함수 깊이우선 방법으로 주어진 정점으로 부터 탐색을 시작한다.

dfsTraversal() 함수

이제 스택을 구현하는 구조체와 연관된 함수들과 그래프를 구현하는 구조체와 그와 연관된 함수들 을 모두 작성했으므로 그래프를 생성하고 깊이우 선 탐색 결과를 출력해 보는 함수를 작성할 것이 다. 이 소스는 ex0903.c 로 작성하고 main 함수를 작 성하여 앞 그림의 G1을 생성하고 깊이 우선 탐색 을 출력하여 확인한다.

ex0903.c 추가 및 작성 Source File 선택

ex0903.c 추가 및 작성 Ch0903 프로젝트명 확인(자동설정) ex0903.c 소스 파일명 설정

추가된 빈 소스 파일 프로젝트에 3 개의 파일 ex0903.c, linkstack.h, linkstack.c, linkgraph.c, linkgraph.h 가 추가된 것을 확인할 수 있다.

main 함수 작성 빈 main 함수 작성 표준 입출력 함수 헤더 메모리 관련 함수 헤더 스택 관련 함수 헤더 그래프 관련 함수 헤더

main 함수 우측 그림과 같은 그래프 를 만들고 깊이우선 탐색 출력을 한다.

main 함수 작성 프로그램의 가독성을 높이기 위하여 G1, G2, G3, G4를 생성하는 함수를 따로 작성함.

G1을 생성하는 함수 A:0, B:1, C:2, D:3 그래프 초기화 4 개의 정점 추가 A->D 간선 추가 인접리스트를 오름차순으로 추가 하기 위하여 큰 노드와 연결된 정보를 먼저 추가함.

G2,G3, G4를 생성하는 함수

빌드 및 실행 결과

도전 문제 위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하고 깊이우선 탐색 결과를 출력하는 프로그램을 작성하시오.

예제 9-4 실습하기 인접리스트를 이용해 구현한 그래프의 너비우선 탐색 프로그램 인접리스트를 이용해 구현한 그래프의 너비우선 탐색 프로그램 그래프를 구현한 소스파일과 헤더파일, 탐색을 위 한 스택을 위한 소스 및 헤더파일을 따로 작성한 다. 구현한 함수 목록(그래프 관련) initializeGraph : 그래프를 초기화하는 함수 clearGraph : 그래프에서 사용하는 메모리를 반환한다. freeList : 연결 리스트의 메모리를 반환한다. insertVertex : 정점을 추가하는 함수 insertEdge : 간선을 추가하는 함수 printGraph : 그래프를 출력하는 함수 bfsTraversal : 너비우선 방법으로 그래프 탐색

예제 9-4 실습하기 구현한 함수 목록(큐 관련) createQueue : 큐를 생성하는 함수 enQueue : 큐에 자료 추가 deQueue : 큐에서 자료 삭제 clearQueue : 큐가 사용한 메모리 반환 isEmpty : 큐가 비었는지를 판단하는 함수

예제 9-3과 책의 예제 9-4의 소스를 참고하여 예 제 9-4를 완성할 것

도전 문제 위 예제를 활용하여 다음 그래프를 작성하고 인접 리스트 출력하고 너비우선 탐색 결과를 출력하는 프로그램을 작성하시오.