개발 알다가도 모르겠네요

이분 그래프를 간단하게 설명하면? 모든 정점들을 두 가지 색으로만 칠하되, 인접한 정점끼리는 서로 다른 색을 칠해야 하는 그래프! 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프. DFS, BFS로 각각의 정점을 돌아다니며 한 가지 색으로 칠합니다. 다음 정점으로 방문하면서 인접 정점들은 다른 색으로 칠합니다. 탐색 진행시 자신과 인접 정점이 같은 색이면 이분 그래프가 아닙니다. 이분 그래프 특징 그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 하는 그래프입니다. DFS와 BFS로 구현이 가능합니다. BFS의 경우 같은 레벨의 정점들은 모두 같은 색깔을 칠한다고 생각하면 쉽습니다. 연결 성분의..

DFS 넓게(wide) 탐색하기 전에 깊게(deep) 탐색합니다. 모든 노드를 방문하고자 할 때 이 방법을 선택합니다. BFS보다 좀 더 간단합니다. 검색 속도 자체는 BFS보다 느립니다. BFS 깊게(deep) 탐색하기 전에 넓게(wide) 탐색합니다. 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고자 할 때 이 방법을 선택합니다. BFS는 재귀적으로 동작하지 않으며 선입선출(FIFO) 원칙으로 탐색합니다. 간선의 가중치가 1이거나, 정점과 간선의 개수가 적을 때 사용하면 효율적입니다.

BFS(Breath First Search)를 간단하게 설명하면? 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘! 시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 큐를 이용하여 구현을 합니다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다. 위의 과정을 수행할 수 없을 때까지 반복합니다. BFS 구현 과정 인접리스트 import java.util.*; public class Main { public static boolean visited[]; public static int v; public static int e; pub..

DFS(Depth First Search)를 간단하게 설명하면? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘! 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수없게 되면 다른 방향으로 다시 탐색을 진행하는 방식입니다. 스택이나 재귀함수를 이용하여 구현합니다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼냅니다. 위의 과정을 수행할 수 없을 때까지 반복합니다. DFS 구현 과정 인접리스트 import java.util.*; public class Main { public static boolean visited[] publi..