자료구조를 이용한 사이클검사

소개글

임의의 방향 그래프 G 가 주어질 때, G에 존재하는 모든 cycle의 개수와 그 내용을 출력하는 프로그램을 작성하시오
input.txt 파일을 읽어오고 어떤 형식으로 파일의 내용을 담을 것인지, 그리고 담은 내용을 가지고 인접행렬과 인접리스트 어떤 형식으로 표현할 것이며, 그 내용을 가지고 어떻게 사이클인지 검사를 할 것인가, 그리고 어떤 노드들이 사이클을 이루고 있는가, 또한 사이클의 개수는 어떻게 셀 것인가를 생각 하였습니다.
우선 저번 트리때와 마찬가지로 그래프 내용이 인풋 파일로 주어지기 때문에 저번에 사용한 파일 읽어오는 방법을 사용 하였습니다. while 문으로 feof 를 이용하여 끝에 도달하여 NULL 일때까지 내용을 하나줄씩 버퍼에 담고 버퍼내용의 값을 char 형이기 때문에 atoi를 이용하여 int 형으로 변환후 각 노드들을 임시로 Graph in 에 담습니다. arr 의 경우 연결되지 않다면 바로 0 값을 넣고 출력하였습니다.
다음 내용은 소스와 결과사진입니다.

목차

없음

본문내용

CYCLE 검사 및 출력

방향 그래프에 존재하는 모든 Cycle 출력

임의의 방향 그래프 G 가 주어질 때, G에 존재하는 모든 cycle의 개수와 그 내용을 출력하는 프로그램을 작성하시오
2 Cycles input.txt
1, 4 7
4, 5, 6 1 3
1 4
3 2
3 7
4 1
4 5
5 6
6 4
6 7

프로그램 작성에 앞서 전체적인 대략적인 모습을 우선 생각해 보았었습니다.
input.txt 파일을 읽어오고 어떤 형식으로 파일의 내용을 담을 것인지, 그리고 담은 내용을 가지고 인접행렬과 인접리스트 어떤 형식으로 표현할 것이며, 그 내용을 가지고 어떻게 사이클인지 검사를 할 것인가, 그리고 어떤 노드들이 사이클을 이루고 있는가, 또한 사이클의 개수는 어떻게 셀 것인가를 생각 하였습니다.
우선 저번 트리때와 마찬가지로 그래프 내용이 인풋 파일로 주어지기 때문에 저번에 사용한 파일 읽어오는 방법을 사용 하였습니다. while 문으로 feof 를 이용하여 끝에 도달하여 NULL 일때까지 내용을 하나줄씩 버퍼에 담고 버퍼내용의 값을 char 형이기 때문에 atoi를 이용하여 int 형으로 변환후 각 노드들을 임시로 Graph in 에 담습니다. Graph 안에는 노드 자신의 int key 값과 가르키는 노드 key 값을 가질 int link 가 있습니다. 그리고 인접행렬을 표현하기 위해 arr 이중 포인터를 사용하여 노드개수 만큼 크기를 잡고 arr[in.key][in.link] 를 이용하여 배열값에 1을 넣어 줌으로써 노드key 가 link 를 가르키는 방향그래프로 인접행렬을 표현하였습니다. 처음에 바로 값만 넣어주고 출력하였을때 초기화를 시키지 않아 쓰레기 값이 함께 떠 앞에 전체적인 포인터들을 초기화 시켜 주었습니다. arr 의 경우 연결되지 않다면 바로 0 값을 넣고 출력하였습니다.

참고 자료

없음

압축파일 내 파일목록

Cycle검사.c
Cycle검사.ncb
Cycle검사.plg
Cycle검사1-1.JPG
Cycle검사1-2.JPG
Cycle검사 추가 2-1.JPG
Cycle검사 추가 2-2.JPG
Cycle검사 추가 2 그림.JPG
Cycle검사 추가 3-1.JPG
Cycle검사 추가 3-2.JPG
Cycle검사 추가 3 그림.JPG
Cycle검사 추가 4-1.JPG
Cycle검사 추가 4-2.JPG
Cycle검사 추가 4 그림.JPG
Cycle검사 추가 5-1.JPG
Cycle검사 추가 5-2.JPG
Cycle검사 추가 5 그림.JPG
Cycle검사 추가 6-1.JPG
Cycle검사 추가 6-2.JPG
Cycle검사 추가 6-3.JPG
Cycle검사 추가 6 그림.JPG
Cycle검사.dsp
Cycle검사.dsw
Cycle검사.opt
Cyclee 검사 및 출력.hwp
input.txt
input1.txt
input2.txt
input3.txt
input4.txt
input5.txt
Debug/Cycle검사.exe
Debug/Cycle검사.ilk
Debug/Cycle검사.obj
Debug/Cycle검사.pch
Debug/Cycle검사.pdb
Debug/vc60.idb
Debug/vc60.pdb

전체 목록 보기