SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스

#pragma once

#ifndef ___SrchALGraph

#define ___SrchALGraph

//SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스

#include "AdjListGraph.h"

#include "CircularQueue.h"

class SrchALGraph : public AdjListGraph {

bool visited[MAX_VTXS]; //정점의 방문 정보

public:

void resetVisited() { //모든 정점을 방문하지 않았다고 설정

for (int i = 0; i < size; i++)

visited[i] = false;

}

bool isLinked(int u, int v) {

for (Node* p = adj[u]; p != NULL; p = p->getLink())

if (p->getId() == v) return true;

return false;

}

//깊이 우선 함수

void DFS(int v) {

visited[v] = true; //현재 정점을 방문함

printf("%c ", getVertex(v)); //정점의 이름 출력

for (Node* p = adj[v]; p != NULL; p = p->getLink())

if (visited[p->getId()] == false)

DFS(p->getId()); //정점 w에서 DFS 새로 시작

}

//인접 리스트로 표현된 그래프에 대한 너비우선탐색 연산

void BFS(int v) {

visited[v] = true; //현재 정점을 방문함

printf("%c ", getVertex(v)); //정점의 이름 출력

CircularQueue que;

que.enqueue(v); //시작 정점을 큐에 저장

while (!que.dequeue()) {

int v = que.dequeue(); //큐에 정점 추출

for (Node* w = adj[v]; w != NULL; w = w->getLink()) {

int id = w->getId(); //인접 노드의 정점 ID

if (!visited[id]) { //미방문 정점 탐색

visited[id] = true; //방문 표시

printf("%c ", getVertex(id));

que.enqueue(id); //방문한 정점을 큐에 저장

}

}

}

}

};

#endif // !___SrchALGraph