그래프

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; /* (입력예시) 1 7 6 1 7 1 2 2 4 2 5 1 3 3 6 6 7 (그래프 예시) 1 / \ 2 3 / \ \ 4 5 6 | 7 */ public class bfs_Samplecode { static int T, N, M, A, B; // 정점을 담을 큐 (row, col, cost) static Queue<Integer> que = new LinkedList<Integer>(); // 출발지 S, 목적지 E static int S, E; // 인접 행렬 static int MAT[][] = new int[101][101]; static int visited[] = new int[101]; // 방문 횟수 static int cnt = 0; public static void bfs() { // 1. 시작점을 큐에 넣는다. que.add(S); visited[S] = 1; cnt++; // 5. 큐가 비어있는지 않다면 반복 while(!que.isEmpty()) { // 2. 큐에서 한 점을 꺼내서 기준점으로 삼는다. System.out.println("now : " + que.peek()); int now = que.poll(); // 3. 기준점이 목적지이면 탐색을 종료한다. if( now == E ) break; // 4. 그렇지 않은 경우 기준점에서 갈 수 있는 다른 정점들을 큐에 넣는다. else { for (int i = 1; i <= N; i++) { // 기존에 방문하지 않고 // 현재 정점과 연결된 점을 탐색 if( visited[i] == 0 && MAT[now][i] == 1 ) { visited[i] = 1; cnt++; // 해당 지점을 큐에 넣는다. que.add(i); System.out.println(i + "번 정점 방문"); } } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { // N : 정점의 수 // M : 간선의 수 N = sc.nextInt(); M = sc.nextInt(); // S : 출발지 // E : 목적지 S = sc.nextInt(); E = sc.nextInt(); // visited배열 초기화 for (int i = 1; i <= N; i++) { visited[i] = 0; } // 인접배열 초기화 for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { MAT[i][j] = 0; } } // 인접배열 정점간의 관계 지정 for (int i = 1; i <= M; i++) { A = sc.nextInt(); B = sc.nextInt(); MAT[A][B] = 1; } // 인접배열 출력 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { System.out.print(MAT[i][j] + " "); } System.out.println(); } // 그래프 탐색 - BFS(Breadth First Search) bfs(); System.out.println(cnt + "개의 정점 방문"); } } }

import java.util.Scanner; /* 깊이 우선 탐색(Depth First Search, DFS) - 깊이 우선탐색은 트리나 그래프를 탐색하는 알고리즘 중 하나로, 한 정점에서 출발하여 가능한 멀리까지 탐색하는 방법이다. - dfs는 지나온 경로를 쉽게 파악할 수 있는 장점이 있으며, 스택(Stakc) 이나 재귀함수(Recursion Func)로 구현할 수 있다. (입력예시) 1 6 5 1 2 2 3 2 4 1 5 5 6 (그래프 예시) 1 / \ 2 5 / \ \ 3 4 6 */ public class dfs_Samplecode { static int T, N, M, A, B; // i번째 정점을 방문했는지 여부를 체크할 배열 // i번째 정점을 방문(O) visited[i] = 1 // i번째 정점을 방문(x) visited[i] = 0 static int visited[] = new int[101]; // 인접 배열 static int MAT[][] = new int[101][101]; // 방문 횟수 static int cnt = 0; // void dfs(int idx, int depth) // - idx : 현재위치, depth : 깊이 2가지를 기본적인 인자로 가진다. public static void dfs(int idx, int depth) { System.out.println("depth: " + depth); // 종료조건 if( idx == N ) { } // 탐색조건 else { for (int i = 1; i <= N; i++) { // 기존에 방문한 정점이 아니고 // 현재 정점과 연결된 정점인 경우에만 탐색 if( visited[i] == 0 && MAT[idx][i] == 1 ) { // i번째 정점을 방문 System.out.println(i + "번 정점 방문 " ); cnt++; visited[i] = 1; dfs(i, depth+1); // 탐색이 끝나면 해제 System.out.println(i + "번으로 돌아옴"); visited[i] = 0; } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { // N : 정점의 수 // M : 간선의 수 N = sc.nextInt(); M = sc.nextInt(); // visisted배열 초기화 for (int i = 0; i < N; i++) { visited[i] = 0; } // 인접배열 초기화 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { MAT[i][j] = 0; } } // 인접배열 정점간의 관계 지정 for (int i = 1; i <= M; i++) { A = sc.nextInt(); B = sc.nextInt(); MAT[A][B] = 1; } // 인접배열 출력 for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { System.out.print(MAT[i][j] + " "); } System.out.println(); } // 그래프 탐색 - DFS(Depth First Search) dfs(1, 1); // root(+1) 포함 정점 방문 수 System.out.println(cnt+1 + "개의 정점 방문"); } } }

public class Graph { private int V; // 정점의 개수 private LinkedList<Integer>[] adj; // 인접 리스트 // 그래프 생성자 public Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList(); } // 간선 추가 public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); // 무방향 그래프의 경우 } }

import java.util.*; public class GraphWithCollections { private Map<Integer, List<Integer>> adjacencyList; public GraphWithCollections() { adjacencyList = new HashMap<>(); } // 정점 추가 public void addVertex(int vertex) { adjacencyList.putIfAbsent(vertex, new ArrayList<>()); } // 간선 추가 public void addEdge(int source, int destination) { // 정점이 없다면 추가 adjacencyList.putIfAbsent(source, new ArrayList<>()); adjacencyList.putIfAbsent(destination, new ArrayList<>()); // 양방향 간선 추가 adjacencyList.get(source).add(destination); adjacencyList.get(destination).add(source); } // 인접 정점 가져오기 public List<Integer> getAdjVertices(int vertex) { return adjacencyList.get(vertex); } }