본 프로젝트에서는 그래프를 이용해 그래프 연산 프로그램을 구현한다. 이 프로그램은 그래프 정보가 저장된 텍스트 파일을 통해 그래프를 구현하고, 그래프의 특성에 따라 BFS, DFS, Kruskal, Dijkstra, Bellman-Ford, 그리고 FLOYD 연산을 수행한다. 그래프 데이터는 방향성(Direction)과 가중치(Weight)를 모두 가지고 있으며, 데이터 형태에 따라 List 그래프와 Matrix 그래프로 저장한다. BFS와 DFS는 그래프의 방향성과 가중치를 고려하지 않고, 그래프 순회 또는 탐색 방법을 수행한다. Kruskal 알고리즘은 최소 비용 신장 트리(MST)를 만드는 방법으로 방향성이 없고, 가중치가 있는 그래프 환경에서 수행한다. Dijkstra 알고리즘은 정점 하나를 출발점으로 두고 다른 모든 정점을 도착점으로 하는 최단경로 알고리즘으로 방향성과 가중치 모두 존재하는 그래프 환경에서 연산을 수행한다. 만약 weight가 음수일 경우 Dijkstra는 에러를 출력하며, Bellman-Ford에서는 음수 사이클이 발생한 경우 에러, 음수사이클이 발생하지 않았을 경우 최단 경로와 거리를 구한다. FLOYD에서는 음수 사이클이 발생한 경우 에러, 음수 사이클이 발생하지 않았을 경우 최단 경로 행렬을 구한다. 프로그램의 동작은 명령어 파일에서 요청하는 명령에 따라 각각의 기능을 수행하고, 그 결과를 출력 파일(log.txt)에 저장한다.
11/11 - ver1 업로드
11/24 - ver2 업로드(제한사항 및 구현 시 유의사항에 메모리 누수 조건 추가)
11/30 - ver3 업로드(미사용 클래스(vertexset)에 대한 본문 내용 제거)
Q. command.txt와 graph.txt는 제공하지 않나요?
A. 네, 따로 제공하지 않습니다.
- ls : list로 현재 작업중인 디렉토리의 파일 및 포함된 디렉토리 목록들을 표시 ( -a, -l 속성으로 자세한 출력 가능)
- pwd : print working directory로 현재 작업중인 디렉토리의 절대경로 위치 출력
- cd : change directory로 디렉토리 를 변경( . : 현재 디렉토리, .. : 상위 디렉토리 )
$ ls
Documents Download
$ ls -l
drwxr-xr-x 2 user user 4096 Oct 05 2020 Documents
drwxr-xr-x 2 user user 4096 Oct 05 2020 Downloads
$ pwd
/home/user
$ cd Download
$ pwd
/home/user/Downloads
$ sudo apt-get install git
$ git clone https://github.com/DSLDataStorage/DS_Project_3_2022_2.git
$ make
g++ -std=c++11 -g -o run GraphMethod.cpp ListGraph.cpp Manager.cpp Graph.cpp MatrixGraph.cpp main.cpp Manager.h vertexSet.h Graph.h MatrixGraph.h ListGraph.h GraphMethod.h
$ ls
Graph.cpp Graph.h GraphMethod.cpp GraphMethod.h ListGraph.cpp ListGraph.h main.cpp makefile Manager.cpp Manager.h MatrixGraph.cpp MatrixGraph.h **run**
$ ./run
$ cat log.txt
==> command 1) LOAD
Success