[자료구조]articulation point를 찾고, 이를 이용해서 biconnected component 구하기

소개글

그래프에 대해서 articulation point를 찾고, 이를 이용해서 biconnected component를 구하는 프로그램을 작성한다.
(1) 입력: 그래프를 adjacent matrix의 형태로 파일로부터 읽어들인다
(graph.txt 참조)
(2) graph.txt 설명
A. 첫번째 줄에 나온 숫자 10은 vertex의 수를 나타내며, vertex의 번호는
0 ~ 9 까지임을 나타냄.
B. 다음에 나오는 10 X 10 행렬은 adjacent matrix로 [i][j]값이 1이면
vertex i와 vertex j간의 edge가 존재함을 나타냄.
(3) 출력:
A. articulation point
B. biconnected component: vertex와 edge를 함께 출력할 것.
실행
파일 입출력을 이용해서 그래프에 대한 정보를 입력받아서 articulation point와 biconnected
component들을 화면에 다음과 같은 형식으로 출력하도록 한다 (graph.txt의 예).
Articulation points: 0, 3, 5, 7
Biconnected component 1: 0, 1, {(0,1)}
Biconnected component 2: 1, 2, 3, 4, {(1,2), (2,4), (1,3), (3,4)}
Biconnected component 3: 3, 5, {(3,5)}

컴파일 실행환경

Microsoft Visual Studio C++

압축파일 내 파일목록

Debug/BuildLog.htm
Debug/Finding Biconnected Components.exe
Debug/Finding Biconnected Components.exe.embed.manifest
Debug/Finding Biconnected Components.exe.embed.manifest.res
Debug/Finding Biconnected Components.exe.intermediate.manifest
Debug/Finding Biconnected Components.ilk
Debug/Finding Biconnected Components.obj
Debug/Finding Biconnected Components.pdb
Debug/mt.dep
Debug/vc90.idb
Debug/vc90.pdb
Finding Biconnected Components.cpp
Finding Biconnected Components.sln
Finding Biconnected Components.suo
Finding Biconnected Components.vcproj
Finding Biconnected Components.vcproj.0681B4264C824B6.류혜정.user
graph.txt

전체 목록 보기

참고 자료

없음