Bfs_dfs

DFS(깊이 우선 탐색)

시작노드를 출발하여 깊에 들어갈 수 있을때까지 들어가고 정점에 도달하면 다시 나오는 알고리즘이다.

스택과 재귀를 이용해서 구현한다.

시작이 1이라면 1->2, 2->4로 간다. 정점까지 도달했으므로 다시 나온다.

3->5로 간 후 다시 나오고 3->6, 3->7식으로 정점까지 도달 후 나온다.

중요한 점은 방문한 곳은 체크해줘야 한다. 재방문을 하지 않기 위함이다.

재귀로 만든 이유는 스택구조로 만들기 위해서다.

만약 더이상 갈 점이 없다면 다시 돌아가야 하기 때문이다.

	//깊이 우선 탐색
	public static void dfs(int i){
		visited[i] = true;
		System.out.print(i+" ");
		
		//정점을 방문하지않고 인접행렬인 경우
		for(int j=1; j<=N; j++){
			if(graph[i][j]==1 && visited[j]==false){
				dfs(j);
			}
		}
	}

BFS(너비 우선 탐색)

시작노드를 출발하여 시작 정점을 방문한 후 인접한 모든 정점들을 우선 방문하는 방법이다.

큐를 이용해서 구현한다.

1에서 시작한다면 인접한 정점으로 이동한다.

인접한 정점은 2와 3이다.

1->2, 1->3으로 이동한다.

2와 인접한 정점은 4밖에 없으니 2->4

3의 인접한 정점은 5,6,7이므로 3->5, 3->6, 3->7 이동한다.

public static void bfs(int i){
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(i);
		visited[i] = true;
		System.out.print(i+" ");
		
		int temp;
		// 정점을 방문하지않고 인접행렬일 경우
		// 방문시에 큐에 저장, 방문이 끝나면 큐에서 꺼내 꺼낸 값의 정점들을 찾음.
		while(!q.isEmpty()){
			temp = q.poll();
			for(int j=0; j<N+1; j++){
				if(graph[temp][j]==1 && visited[j]==false){
					q.offer(j);
					visited[j] = true;
					System.out.print(j+ " ");
				}
			}
		}
	}

예제코드 [jekyll-gh]: https://github.com/quarl894