DFS

DFS

DFS(Depth-First Search)는 루트노드 또는 임의의 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 완전 탐색 방법의 하나이다.

 

DFS의 특징

• DFS는 스택 프레임의 알고리즘으로 구현되기 때문에 재귀 함수 또는 스택 자료구조를 통해 구현할 수 있다.
• 트리의 전위 순회, 중위 순회, 후위 순회 모두 DFS의 한 종류이다.
• 그래프에 대한 DFS를 구현할 경우, 어떤 정점(노드)를 방문했는 지 여부를 반드시 검사해야 무한 루프를 방지할 수 있다.

 

시간 복잡도

그래프의 구현 방법에 따라 시간 복잡도에 차이가 있다. N은 정점의 수, E는 간선의 수이다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

 

DFS를 사용하기 좋은 상황

• 그래프의 모든 정점을 방문하는 것이 목적인 경우
• 특정한 두 정점 간의 경로와 관련된 문제를 해결하는 것이 목적인 경우

 

DFS의 그래프 탐색 과정

DFS의 그래프 탐색 과정은 이전에 방문한 정점은 다시 방문하지 않는 다는 것을 전제로 한다.

1. A를 방문한다. A에 대한 방문 체크를 한다.
2. A와 인접한 정점 B를 방문한다. B에 대한 방문 체크를한다.
3. B의 인접한 정점 C를 방문한다. C에 대한 방문 체크를 한다.
4. 위의 과정을 반복하여 마지막 깊이까지 방문한다.
5. 이전 깊이로 돌아와 다른 인접한 정점을 방문하고 위의 과정을 반복한다. 

 

DFS 구현

인접 행렬과 인접 리스트에 대해 DFS를 구현하였다.

스택 자료구조 보다 재귀 함수가 구현에 용이하여 재귀 함수를 사용하였다.

 

인접 행렬 DFS

public class AdjMatrix_dfs {

	private int[][] adjMatrix;

	public AdjMatrix_dfs(int size) {
		if (size <= 0) {
			System.out.println("그래프는 정점이 1개 이상이어야 합니다.");
			return;
		}

		adjMatrix = new int[size + 1][size + 1]; // vertex의 인덱스를 1부터 시작하기 위함.
	}

	// 무향 간선 - 가중치 X
	public void insertBiDir(int vertex1, int vertex2) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = 1;
		adjMatrix[vertex2][vertex1] = 1;
	}

	// 무향 간선 - 가중치 O
	public void insertBiDir(int vertex1, int vertex2, int weight) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = weight;
		adjMatrix[vertex2][vertex1] = weight;
	}

	// 방향 간선 - 가중치 X
	public void insertSingleDir(int vertex1, int vertex2) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = 1;
	}

	// 방향 간선 - 가중치 O
	public void insertSingleDir(int vertex1, int vertex2, int weight) {
		if (valid(vertex1, vertex2)) {
			return;
		}

		adjMatrix[vertex1][vertex2] = weight;
	}

	public void dfs(int index) {
		if (valid(index, index)) {
			return;
		}

		// 방문 여부 체크를 위한 배열
		boolean[] visited = new boolean[adjMatrix.length];
		// index는 탐색의 시작 정점이다.
		dfsUtil(index, visited);
	}

	private void dfsUtil(int index, boolean[] visited) {
		// 현재 정점을 방문한 경우 방문 여부를 체크한다.
		visited[index] = true;

		System.out.print(index + " ");

		int[] matrix = adjMatrix[index];

		// 정점을 순회하면서 현재 정점의 인접 정점을 확인한다.
		for (int i = 1; i < matrix.length; i++) {
			// 현재 정점의 인접 정점이면서 현재 방문하지 않은 상태인 경우 방문한다.
			if (matrix[i] != 0 && !visited[i]) {
				dfsUtil(i, visited);
			}
		}
	}

	private boolean valid(int vertex1, int vertex2) {
		if (adjMatrix.length <= 1) {
			return true;
		}

		if (vertex1 < 1 || vertex1 >= adjMatrix.length || vertex2 < 1 || vertex2 >= adjMatrix.length) {
			return true;
		}

		return false;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		for (int i = 1; i < adjMatrix.length; i++) {
			for (int j = 1; j < adjMatrix[i].length; j++) {
				sb.append(adjMatrix[i][j]).append(" ");
			}
			sb.append("\n");
		}

		return sb.toString();
	}
}

 

인접 리스트 DFS

public class Edge {
	private int destination;
	private int weight;

	public Edge(int destination, int weight) {
		this.destination = destination;
		this.weight = weight;
	}

	public Edge(int destination) {
		this.destination = destination;
		this.weight = 1;
	}

	public int getDestination() {
		return destination;
	}

	public int getWeight() {
		return weight;
	}
}


public class AdjList_dfs<T> {
	private int size;
	private List<List<Edge>> adjList = new ArrayList<>(); // 정점들의 목록
	private List<T> dataList = new ArrayList<>(); // 정점들의 데이터를 저장한다.

	// 정점 추가
	public void addVertex(T data) {
		// 인덱스를 1부터 시작하기 위해 첫 번쨰 정점 추가 전에 의미없는 정점을 추가.
		if (size == 0) {
			adjList.add(new ArrayList<>());
			dataList.add(null);
			size++;
		}

		adjList.add(new ArrayList<>()); // 정점들의 목록을 추가한다.
		dataList.add(data); // 정점들의 데이터를 저장한다. 동일한 정점에 대한 adjList와 dataList의 인덱스는 동일하다.
		size++; // 정점 개수 증가
	}

	public void dfs(int index) {
		if (valid(index)) {
			return;
		}

		// 방문 여부 체크를 위한 배열
		boolean[] visited = new boolean[size];
		// index는 탐색의 시작 정점이다.
		dfsUtil(index, visited);
	}

	private void dfsUtil(int index, boolean[] visited) {
		// 현재 정점을 방문한 경우 방문 여부를 체크한다.
		visited[index] = true;

		System.out.print(index + " ");

		ListIterator<Edge> listIterator = adjList.get(index).listIterator();

		// 현재 정점과 인접한 정점을 순회한다.
		while (listIterator.hasNext()) {
			int cur = listIterator.next().getDestination();

			// 현재 정점과 인접한 정점 중 방문하지 않은 상태인 경우 방문한다.
			if (!visited[cur]) {
				dfsUtil(cur, visited);
			}
		}
	}

	// 간선을 추가한다 - 가중치 지정 O
	public void addEdge(int source, int destination, int weight) {
		if (valid(source) || valid(destination)) {
			return;
		}

		adjList.get(source).add(new Edge(destination, weight));
	}

	// 간선을 추가한다 - 가중치 지정 X
	public void addEdge(int source, int destination) {
		if (valid(source) || valid(destination)) {
			return;
		}

		adjList.get(source).add(new Edge(destination));
	}

	// 주어진 인덱스에 해당하는 정점에서 출발하는 간선 정보를 반환한다.
	public List<Edge> getAdjVertices(int index) {
		return adjList.get(index);
	}

	// 주어진 인덱스에 해당하는 정점의 데이터를 반환한다.
	public T getData(int index) {
		return dataList.get(index);
	}

	private boolean valid(int index) {
		if (size <= 1) {
			System.out.println("정점이 없습니다.");
			return true;
		}

		if (index < 1 || index >= size) {
			System.out.println("유효한 정점 인덱스가 아닙니다.");
			return true;
		}
		return false;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < adjList.size(); i++) {
			sb.append("adjVertices to " + i + ": ");
			List<Edge> adjVertices = getAdjVertices(i);

			for (Edge adjVertex : adjVertices) {
				sb.append(adjVertex.getDestination() + "(" + adjVertex.getWeight() + ")" + " ");
			}

			sb.append("\n");
		}

		return sb.toString();
	}
}

 

실제 사용

public class Main {

	public static void main(String[] args) {
		///////////////////// 인접 리스트의 DFS /////////////////////
		AdjList_dfs<Integer> adjList_dfs = new AdjList_dfs<>();

		for (int i = 1; i <= 5; i++) {
			adjList_dfs.addVertex(i);
		}

		adjList_dfs.addEdge(1, 2);
		adjList_dfs.addEdge(1, 4);
		adjList_dfs.addEdge(2, 3);
		adjList_dfs.addEdge(2, 4);
		adjList_dfs.addEdge(2, 5);
		adjList_dfs.addEdge(3, 2);
		adjList_dfs.addEdge(4, 5);
		adjList_dfs.addEdge(4, 1);
		adjList_dfs.addEdge(5, 1);

		for (int i = 1; i <= 5; i++) {
			adjList_dfs.dfs(i);
			System.out.println();
		}

		/*1 2 3 4 5
		  2 3 4 5 1
		  3 2 4 5 1
		  4 5 1 2 3
		  5 1 2 3 4*/

		System.out.println("/////////////////////////////////////");

		///////////////////// 인접 행렬의 DFS /////////////////////
		AdjMatrix_dfs adjMatrix_dfs = new AdjMatrix_dfs(5);

		adjMatrix_dfs.insertSingleDir(1, 2);
		adjMatrix_dfs.insertSingleDir(1, 4);
		adjMatrix_dfs.insertSingleDir(2, 3);
		adjMatrix_dfs.insertSingleDir(2, 4);
		adjMatrix_dfs.insertSingleDir(2, 5);
		adjMatrix_dfs.insertSingleDir(3, 2);
		adjMatrix_dfs.insertSingleDir(4, 5);
		adjMatrix_dfs.insertSingleDir(4, 1);
		adjMatrix_dfs.insertSingleDir(5, 1);

		for (int i = 1; i <= 5; i++) {
			adjMatrix_dfs.dfs(i);
			System.out.println();
		}
		/*1 2 3 4 5
		  2 3 4 5 1
		  3 2 4 5 1
		  4 5 1 2 3
		  5 1 2 3 4*/
	}
}