검색어 입력폼

Articulation Point & Bicomponent 설계 보고서

저작시기 2006.05 |등록일 2006.12.21 한글파일한글 (hwp) | 9페이지 | 가격 300원

소개글

그래프 구조에서 DFS(Depth First Search, 깊이 우선 검색) 탐색 기법을 이용하여 Articulation Point와 그로 인하여 분리되는 각 그래프의 서브 그래프의 집합인 Bicomponents들을 찾는 알고리즘을 구현한다.

목차

1. Overview
2. System (class) Design
3. Data Structure Used
4. Key Algorithms
5. Simple input / output
6. Analysis

본문내용

2. Systerm(class) Design
1) CNode

enum eStatus{WHITE, GRAY, BLACK};

class CNode
{
public:
CNode(); // 생성자
CNode(const char chNodeName); // szNodeName 이름을 가진 노드 생성
~CNode(); // 소멸자

friend class CGraph;

private:
char m_chNodeName; // 노드의 이름
eStatus Status; // 노드의 탐색 여부를 색으로 표현
// 현재 노드와 연결된 주변의 노드를 가리키는 포인터
CNode * m_pNextLinkNode;
CNode * m_pNextHeadNode; // 각 Head Node들을 연결하는 포인터
CNode * m_pParentNode; // 현재 노드의 부모 노드를 가리키는 포인터
int m_nDFSNum; // 노드의 DFS 값
int m_nBackNum; // 노드의 Back 값
bool m_bIsArtPoint; // 현재 노드가 Articulation Point인지 여부 확인

};

4. Key Algorithms
2) key 알고리즘 분석

연결 무방향 그래프 G의 Biconnected components는 G의 Depth first spanning
tree를 이용하여 구하며, 최소한 두개의 자식을 갖는 Depth first spanning tree의 root는 단절점

정점 w와 w의 후손들과 단 하나의 백 간선(back edge)으로만 구성된 경로를 이용해서는 u의 조상에 도달할 수 없는 그런 정점 w를 적어도 하나의 자식 정점으로 갖는 정점 u도 단절점
L(u): u의 후손들과 많아야 하나의 백 간선으로 된 경로를 이용해 u로부터 도달할 수 있는 가장 적은 깊이 우선 번호
L(u)=min {dfn(u), min {L(w)|w는 u의 자식}, min {dfn(v)|(u, v)는 백간선} }

정점 1은 L(0)=4≥dfn(1)=3인 자식 0을 가지므로 단절점
정점 7은 L(8)=9≥dfn(7)=7인 자식 8을 가지므로 단절점
정점 5은 L(6)=5≥dfn(5)=5인 자식 6을 가지므로 단절점
다운로드 맨위로