행렬

// graph = new int[][] 

public class Main {
	static int[][] graph;
	static int vertex;
	static boolean[] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		vertex = sc.nextInt();
		int edge = sc.nextInt();
		int start = sc.nextInt();
		graph = new int[vertex+1][vertex+1];
		visited = new boolean[vertex+1];
		for (int i = 0; i < edge; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph[a][b] = 1;
			graph[b][a] = 1;
		}

		dfs(start);
		System.out.println();
		Arrays.fill(visited, false);
		bfs(start);
	}
	
	public static void dfs(int v) {
		// 현재 노드 방문 처리
		visited[v] = true;
		// 방문 노드 출력
		System.out.print(v + " ");

		// 인접 노드 탐색
		for (int i=0; i <= vertex; i++) {
			// 방문하지 않은 인접 노드 중 가장 작은 노드 스택에 넣기
			if (graph[v][i] == 1 && visited[i] == false) {
				dfs(i);
			}
		}
	}
	
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v);
		visited[v]= true;
		while (!queue.isEmpty()) {
			int tmp = queue.poll();
			System.out.print(tmp+" ");
			for (int i=0; i <= vertex; i++) {
				if (graph[tmp][i] == 1 && visited[i] == false) {
					queue.offer(i);
					visited[i]=true;
				}
			}
		}
	}
}

인접 리스트

// graph = new ArrayList<Integer>[]

public class Main {
	static ArrayList<Integer>[] graph;
	static int vertex;
	static boolean[] visited;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		vertex = sc.nextInt();
		int edge = sc.nextInt();
		int start = sc.nextInt();
		graph = new ArrayList[vertex+1]; 
		for (int i = 1; i < vertex+1; i++) { graph[i] = new ArrayList<Integer>(); }
		visited = new boolean[vertex+1];
		for (int i = 0; i < edge; i++) { 
			int a = sc.nextInt(); 
			int b = sc.nextInt(); 
			graph[a].add(b); 
			graph[b].add(a);
		}
		for (int i=1; i < vertex+1; i++) { Collections.sort(graph[i]); }

		dfs(start);
		System.out.println(); 
		visited = new boolean[vertex+1];
		bfs(start);
	}
 
	private static void dfs(int v) {
		if (visited[v]) {
			return;
		}
		visited[v] = true;
		System.out.print(v + " ");
		for (int i : graph[v]) {
			if (visited[i] == false)
				dfs(i);
		}
	}
 
	private static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v);
		visited[v] = true;
		while (!queue.isEmpty()) {
			int v = queue.poll();
			System.out.print(v + " ");
			for (int i : list[v]) {
				if (visited[i] == false) {
					queue.offer(i);
					visited[y] = true;
				}
			}
		}
	}

}

DFS

자료구조

Stack 을 사용한다. 혹은 Recursive.

용도

(1) 그래프에서 모든 정점 탐색

• 시간 복잡도: O(V+E)
• 공간 복잡도: O(V) (일직선이면 모든 정점 다 들어가야 함)

(2) 그래프에서 두 정점 사이의 모든 경로 탐색

• 시간 복잡도: O((V-1)!) (완전 그래프에서의 찾은 경로 수 O((V−2)!)에 경로를 찾는 평균 시간 O(V)를 곱한 값)
• 공간 복잡도: O(V^3) (스택에 최대로 존재하는 V(V-1)/2 + 1 개의 경로와 각 경로의 공간 O(V))

DAG(Directed Acyclic) 일 때의 구현 (visited 필요없다)

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
	List<List<Integer>> paths = new ArrayList<>();
	if (graph == null || graph.length == 0) {
		return paths;
	}
	dfs(graph, 0, new ArrayList<>(), paths);
	return paths;
}

void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> paths) {
	path.add(node);
	if (node == graph.length - 1) {
		paths.add(new ArrayList<>(path));
		return;
	}
	int[] nextNodes = graph[node];
	for (int nextNode: nextNodes) {
		dfs(graph, nextNode, path, paths);
		path.remove(path.size() - 1);
	}
}

(3) 경로가 있는지 확인

• 시간 복잡도: O(V+E)
• 공간 복잡도: O(V+E) (adjacency list V+E, stack E)

public boolean validPath(int n, int[][] edges, int start, int end) {
	List<List<Integer>> adjacency_list = new ArrayList<>();        
	for (int i = 0; i < n; i++) {
		adjacency_list.add(new ArrayList<>());
	}
        
	for (int[] edge : edges) {
		adjacency_list.get(edge[0]).add(edge[1]);
		adjacency_list.get(edge[1]).add(edge[0]);
	}
        
	Deque<Integer> stack = new ArrayDeque<>();
	stack.push(start);
	boolean seen[] = new boolean[n];
	Arrays.fill(seen, false);
        
	while (!stack.isEmpty()) {
		// Get the current node.
		int node = stack.pop();
            
		// Check if we have reached the target node.
		if (node == end) {
			return true;
		}
            
		// Check if we've already visited this node.
		if (seen[node]) {
			continue;
		}
		seen[node] = true;
            
		// Add all neighbors to the stack.
		for (int neighbor : adjacency_list.get(node)) {
			stack.push(neighbor);
		}
	}    
	return false;
}

BFS

자료 구조

Queue 를 사용한다.

용도

(1) 모든 정점 탐색

• 시간 복잡도: O(V+E) (모든 정점, 모든 간선 방문)
• 공간 복잡도: O(V) (visited 확인하므로 큐에 최대 V)

(2) 두 정점 사이의 최단 경로 (모든 경로 탐색 않고도)

• 시간 복잡도: O(V+E) (시작점 끝점 제일 멀 때)
• 공간 복잡도: O(V) (모든 정점 다 저장해야 할 때)

(3) 경로가 있는지 확인

• 시간 복잡도: O(V+E)
• 공간 복잡도: O(V+E) (adjacency list V+E, stack V)

public boolean validPath(int n, int[][] edges, int start, int end) {
	List<List<Integer>> adjacency_list = new ArrayList<>();        
	for (int i = 0; i < n; i++) {
		adjacency_list.add(new ArrayList<>());
	}
        
	for (int[] edge : edges) {
		adjacency_list.get(edge[0]).add(edge[1]);
		adjacency_list.get(edge[1]).add(edge[0]);
	}
        
	Queue<Integer> queue = new LinkedList<>();
	queue.add(start);
	boolean seen[] = new boolean[n];
	Arrays.fill(seen, false);
	seen[start] = true;
        
	while (!queue.isEmpty()) {
		// Get the current node.
		int node = queue.poll();
            
		// Check if we have reached the target node.
		if (node == end) {
			return true;
		}
            
		// Add all neighbors to the stack.
		for (int neighbor : adjacency_list.get(node)) {
			// Check if neighbor has been added to the queue before.
			if (!seen[neighbor]) {
				seen[neighbor] = true;
				queue.add(neighbor);
			}
		}
	}
	return false;
}

(4) 그래프에서 두 정점 사이의 모든 경로 탐색

DAG(Directed Acyclic) 일 때의 구현 (visited 필요없다)

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
	List<List<Integer>> paths = new ArrayList<>();
	if (graph == null || graph.length == 0) {
		return paths;
	}

	Queue<List<Integer>> queue = new LinkedList<>();
	List<Integer> path = new ArrayList<>();
	path.add(0);
	queue.add(path);

	while (!queue.isEmpty()) {
		List<Integer> currentPath = queue.poll();
		int node = currentPath.get(currentPath.size() - 1);
		for (int nextNode: graph[node]) {
			List<Integer> tmpPath = new ArrayList<>(currentPath);
			tmpPath.add(nextNode);
			if (nextNode == graph.length - 1) {
				paths.add(new ArrayList<>(tmpPath));
			} else {
				queue.add(new ArrayList<>(tmpPath));
			} 
		}
	}
	return paths;
}