Week11_그래프순회_DFS_실습

그래프 순회란?

 순회: '모든 정점과 간선'을 그래프를 탐험하는 체계적인 절차

 ex)웹 검색엔진의 데이터 수집 부문: 웹의 하이퍼텍스트 문서(정점), 문서 내 링크(간선)를 검사하여 탐색

 

1. DFS(깊이우선탐색) 

-이진트리에 대한 선위순회와 유사함.

 

<HOW? by pseudo code>

 

Alg DFS(G)

  input graph G

  output labeling of the edges of G as 트리 간선 & 후향 간선

{The algorithm uses a mechanism for setting and getting ''labels'' of vertices and edges}

1. 정점 u의 라벨 = Fresh

2. 간선 e의 라벨 = Fresh

3. if (출발 정점 v의 라벨 = Fresh) --> rDFS(G, v)

 

Alg rDFS(G, v)

  input graph G and a start vertex v of G

  output labeling of the edges of G in the connected component of v as 트리 간선 & 후향 간선

1. v의 라벨 = Visisted {방문 기록 남김}

2. <------v의 인접정점 e 들을 순회----->

  if(e의 라벨 = Fresh) 

    w=??

    if(w의 라벨 = Fresh)

         e의 라벨 = 트리

         rDFS(G, w) {재귀 호출}

    else

         e의 라벨 = 후향 {이미 방문했으므로}

 

*rDFS(G,v)는 v의 연결요소 내의 모든 정점과 간선을 방문함.

*rDFS(G,v)에 의해 라벨된 트리 간선들은 v의 연결요소의 신장트리(DFS tree라 불림)를 형성함.

 

 

A->B

B->C

C->A (후향, A는 이미 방문했으므로)

C->D

D->A (후향, A는 이미 방문했으므로)

C->E

E->A (후향, A는 이미 방문했으므로) 

 

 

**DFS 알고리즘은 미로를 탐험하는데 있어 모험적임.

 

---

STEP1. 인접정점 구조체 만들기

typedef struct IncidentEdge{
   char aName;
   struct IncidentEdge *next;
}IncidentEdge;

STEP2. 정점 구조체 만들기

typedef struct Vertex{
   char vName;
   int isVisit;
   struct Vertex *next;
   IncidentEdge *iHead;
}Vertex;

STEP3. 그래프 구조체 만들고 초기화

typedef struct{
   Vertex * vHead;
}Graph;

void init(Graph *G){
   Vertex *vHead=NULL;
}

STEP4. 정점 만들기

void makeVertex(Graph *G, char vName){
   Vertex *v= (Vertex*)malloc(sizeof(Vertex));
   v->vName=vName, v->isVisit=FALSE;
   v->next=NULL, v->iHead=NULL;
   
   Vertex *p=G->vHead;
   
   if(p==NULL) p->next=v;
   else{
      while(p->next!=NULL){
          p=p->next;
      }
      p->next=v;
    }
 }

STEP5. 인접정점 삽입

void insertIncidentEdge(Vertex *v, char aName){
   IncidentEdge *p=(IncidentEdge*)malloc(sizeof(IncidentEdge));
   	p->aName = aName;
	p->next = NULL;
	//*인접리스트에서 오름차순 정렬!!
	IncidentEdge* q = v->iHead;
	if (q == NULL) {
		v->iHead = p;
	}
	else if (aName < q->aName) {
		p->next = q;
		v->iHead = p;
		return;
	}
	else {
		while (q->next != NULL) {
			if (q->next->aName < aName) {
				q = q->next;
			}
			else {
				p->next = q->next;
				q->next = p;
				return;
			}
		
		}
		q->next = p;
	}

}

STEP6. 정점 찾기

Vertex* findVertex(Graph* G, char vName) {
	Vertex* p = G->vHead;
	int cnt = 0;
	while (p->vName != vName) {
		p = p->next;
	}
	return p;
}

STEP7. 간선 삽입

void insertEdge(Graph* G, char v1, char v2) {
	
	if (v1 != v2) {
		Vertex* v = findVertex(G, v1);
		insertIncidentEdge(v, v2);
		v = findVertex(G, v2);
		insertIncidentEdge(v, v1);
	}
	else {
		Vertex* v = findVertex(G, v1);
		insertIncidentEdge(v, v2);
	}
}

STEP8. DFS

//깊이우선탐색
void dfs(Graph* G, char vName) {
	Vertex* v = findVertex(G, vName);
	IncidentEdge* p;

	if (v->isVisit == FALSE) {
		v->isVisit = TRUE; //방문기록 o
		printf("%c\n", v->vName);
	}
	//인접정점으로
	for (p = v->iHead; p != NULL; p = p->next) {
		v = findVertex(G, p->aName);
		if (v->isVisit == FALSE) {
			dfs(G, v->vName);
		}
	}
}