밍의 기록들😉

그래프의 탐색DFS : 깊이 우선 탐색BFS : 너비 우선 탐색 깊이 우선 탐색(DFS; Depth First Search)스택(=선행관계)을 이용하여 그래프를 탐색하는 방법나를 먼저 방문하고, 그 다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않음)스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다. 인접 행렬을 이용한 구현 코드private static void dfs(int x) { check[x] = true; System.out.print(x); for(int i=1; i

그래프(Graph) 정점 6개, 간선 8개방향이 없는 그래프정점 : {1, 2, 3, 4, 5, 6}간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} 그래프의 구현 : 인접행렬정점의 개수를 V라고 했을 때V x V 크기의 2차원 배열을 이용정점의 연결관계를 0과 1로 표현A[i][j] = 1(연결이 되어있을 때), 0(연결이 되어있지 않을 때)양방향 그래프일 경우 A[i][j] = A[j][i] 구현 코드import java.util.Scanner; public class AdjacencyMatrix { public static void main(String[] args) { Scanner sc = new Scanner(Syste..

그래프(Graph)자료구조의 일종정점(Node, Vertex)간선(Edge) : 정점간의 관계를 나타냄G = (V,E)로 나타냄 경로(Path)정점 A에서 B로 가는 경로A-> C -> D -> E -> BA -> BA -> C -> BA -> C -> E -> B 사이클(Cycle)정점 A에서 다시 A로 돌아오는 경로A-> C -> B -> AA -> C -> E -> B -> AA -> C -> D -> E -> B -> A 단순 경로와 단순 사이클경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함 방향 있는 그래프A -> C와 같이 간선에 방향이 있음A -> C는 있지만, C-> A는 없음 방향 없는 그..