글 읽기 - 그래프 구현했는데 질문이요!

qhrrkfl2 7년 전 0

일단 그래프는 무방향 그래프이고 윤성우 아재의 코드를 베끼듯이 만들었습니다.

탐색은 깊이 우선 탐색이며

이미지를 보시면 실행시 0 1 3 4 5 2 방문이여야 하는데

0 1 3 2 4 5 방문을 합니다.

뭐가 문제죠?

그림이 업로드 안되네요;;;

0 - 1 - - 4

3 ↕

0 - 2- - 5

연결은 이렇게 되어있습니다

0-1

0-2

1-3

2-3

3-4

3-5

4-5

#include <iostream>	
#include <list>
using namespace std;
typedef list<int>::iterator Listiter;

template <typename T>
struct Stack{
	list<T> List;
	void push(T data){ List.push_back(data); };
	T pop(){
		T data = List.back();
		List.pop_back();
		return data;
	};
};


class List{
public:
	Listiter cur;
	list<int> iList;
	List(){ cur = iList.begin(); };
Listiter getNextIter()
{
	if (cur == iList.begin())
	{
		Listiter temp = cur;
		cur++;
		return temp;
	}
	else if (cur != iList.end())
		return cur++;
	else
		return iList.end();
}


};

//무방향 그래프
class Graph{

	int numV;// 정점의 수
	int numE; // 간선의 수
	int* visitInfo;
	List* adjList;
public:
	Graph(int _numV){
	visitInfo = new int[_numV];
	adjList = new List[_numV];
	memset(visitInfo, 0, sizeof(int)*_numV);
	numV = _numV;
	}
	~Graph(){ 
		delete[] visitInfo, adjList; }

		void AddEdge(int from, int to){
		adjList[from].iList.push_back(to);
		adjList[from].cur = adjList[from].iList.begin();
		adjList[to].iList.push_back(from);
		adjList[to].cur = adjList[to].iList.begin();
		numE++;
	}

	bool visitVertex(int visit){
		if (!visitInfo[visit]){
			visitInfo[visit] = 1;
			cout << visit << "방문" << endl;
			return true;
		}
		else
			return false;
	}

	void DFShowGraphVertex(int _startV){
		Stack<int> visitlog;
		visitlog.push(_startV);
		visitVertex(_startV);
		int visitV = _startV;
		int nextV;
		Listiter temp;
		while ((temp = adjList[visitV].getNextIter()) != adjList[visitV].iList.end())
		{
			nextV = *temp;
			int visitFlag = false;
			if (visitVertex(nextV))
			{
				visitlog.push(nextV);
				visitV = nextV;
				visitFlag = true;
			}
			else
			{
				while ((temp = adjList[visitV].getNextIter() )!= adjList[visitV].iList.end())
				{
					nextV = *temp;
					if (visitVertex(nextV))
					{
						visitlog.push(visitV);
						visitV = nextV;
						visitFlag = true;
						break;
					}
				}
			}

			if (visitFlag == false){
				if (!visitlog.List.size())
					break;
				else
					visitV = visitlog.pop();
			}
			
			
		}
	
		memset(visitInfo, 0, sizeof(int)*numV);
		for (int i = 0; i < numV; i++)
		{
			adjList[i].cur = adjList[i].iList.begin();
		}
	}

};


void main()
{
	Graph a(6);
	a.AddEdge(0, 1);
	a.AddEdge(0, 2);
	a.AddEdge(1, 3);
	a.AddEdge(2, 3);
	a.AddEdge(3, 4);
	a.AddEdge(3, 5);
	a.AddEdge(4, 5);

	a.DFShowGraphVertex(0);
	
	system("pause");
}

washi 7년 전 0

3번 vertex와 연결된 vertex들의 순서가 1 2 4 5 순으로 되어있어서 dfs하시면 2번 vertex 먼저 방문을 하게 될 것 같아요

washi 7년 전 0

아뇨 틀린 순회는 아니에요.

DFS는 깊이 우선 탐색이니

맨 처음 0에서 시작을 하시면

0에서 방문 가능한 vertex를 찾음 -> 1을 찾아서 이동 -> 1에서 방문 가능한 vertex를 찾음 -> 3을 찾아서 이동 -> 3 에서 방문 가능한 vertex를 찾음 -> 2를 찾아서 이동 -> 2에서 방문 가능한 vertex를 찾음 -> 방문 가능한 vertex가 없으므로 3번 vertex로 돌아감 -> 3번 vertex에서 방문 가능한 vertex를 찾음 -> 4를 찾아서 이동 -> 4에서 방문 가능한 vertex를 찾음 -> 5를 찾아서 이동 -> 5에서 방문 가능한 vertex를 찾음 -> 없으므로 4로 돌아감 -> 4에서 방문 가능한 vertex를 찾음 -> 없으므로 3으로 돌아감 -> 1번에서 방문 가능한 vertex를 찾음 -> 없으므로 0으로 돌아감 -> 0에서 방문 가능한 vertex를 찾음 -> 없으므로 dfs 종료

정상적으로 순회하네요 @_@

DFS에 관련된 내용을 좀 보시면 도움이 되실꺼같아요.

qhrrkfl2 7년 전 0

답변감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그래프 구현했는데 질문이요!

qhrrkfl2 7년 전 0

washi 7년 전 0

qhrrkfl2 7년 전 0

washi 7년 전 0

qhrrkfl2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말