그래프 관련 정리 -(1)

그래프 관련 정리 -(1)

그래프의 종류  
⬛ 1) 무방향 그래프
G = (V, E) 로 표시
⬛ 2) 방향 그래프
G = <V.E> 로 표시
⬛ 3) 가중치 방향 그래프

그래프의 구현
⬛ 1) 인접행렬
graph[a][b] 로 표현
⬛ 2) 인접리스트
ArryList<ArrayList> graph 로 표현각 정점에 연결된 정점들 정보를 ArrayList 하나에 표현하는데, 그 정점들을 모아 전체 그래프로 표현한 것

그래프의 순회
⬛ 1) 깊이 우선 탐색 DFS
⬛ 2) 너비 우선 탐색 BFS

---

7-11. 경로 탐색 (인접 행렬) | DFS

import java.util.Scanner;

/* 7-12. 경로 탐색 (인접행렬) */
class Main1 {
    static int n, m, answer = 0; //입출력 변수 
    static int[][] graph; //그래프 표시 (인접행렬)
    static int[] ch; //방문 체크용 

    //DFS() 함수
    public void DFS(int v) {
        //들어온 정점v가 목적지n 도달시 카운팅++
        if(v==n) answer++;
        else {
            //각 정점 v에 대하여 가능한 정점i들 탐색하여 뻗어나감
            for(int i=1; i<=n; i++) {
                //각 정점v에 대해 가능한 i 탐색 동시에 방문전인 정점에 대하여 뻗어나감
                if(graph[v][i] == 1 && ch[i] == 0) {
                    ch[i] = 1;//방문 체크
                    DFS(i); //해당 i정점에 대하여 다시 뻗어나감 
                    //여기부터는 DFS(i) 재귀 복귀주소라 다시 Back 작업
                    ch[i] = 0; //체크 해제 (다른 정점에 대하여 다시 시도해야 하므로)
                }
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        //n, m 입력받고
        n= kb.nextInt();
        m= kb.nextInt();

        //n+1 해주는 이유는 1~ 사용할 것이므로 
        graph = new int[n+1][n+1];

        ch = new int[n+1] ; //체크용 동적 배열 생성시 0 초기화
        //가선의 수 만큼 돌면서 간선 정보 임력받음
        for(int i=0; i<m; i++) {
            int a= kb.nextInt();
            int b= kb.nextInt();
            graph[a][b] = 1; //입력받은 각 정점의 정점 정보에 1 세팅 
        }
        //일단 1은 무조건 '출발점'이므로 1체크
        ch[1] = 1;
        //1부터 보내서 DFS() 호출 
        T.DFS(1);
        //정답 출력
        System.out.println(answer);
    }
}

---

7-12. 경로 탐색 (인접 리스트) | DFS

import java.util.ArrayList;
import java.util.Scanner;

/* 7-13. 경로탐색 (인접리스트, ArrayList)
 * */
class Main2 {
    static int n, m, answer =0 ;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch; //체크 배열 
    //DFS 함수 
    public void DFS(int v) {
        if(v==n) answer++;
        else {
            //그래프 속 v번 정점에 연결된 nv 정점들 하나씩 가져옴
            for(int nv : graph.get(v)) {
                //방문 전인 정점에 대하여 
                if(ch[nv] == 0) {
                    ch[nv] = 1; //방문체크
                    DFS(nv);//해당 정점에 대해 다시 찾음
                    //복귀 후 back
                    ch[nv] = 0; //백 처리
                }
            }    
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();

        //전체 크래프에 담을 각 정점 ArrayList 객체 생성 
        for(int i=0; i<=n; i++) {
            //각 정점i들을 담을 ArrayList 생성 
            graph.add(new ArrayList<Integer>());
        }
        //체크용 배열 생성 
        ch=new int[n+1];
        for(int i=0; i<m; i++) {
            int a =kb.nextInt();
            int b =kb.nextInt();
            //각각의 정점 a 가져와서, 다시 add 연결정점 b담음
            graph.get(a).add(b);
        }
        //최초 출발점 정점1 방문 세팅
        ch[1] = 1;
        T.DFS(1);
        //출력
        System.out.println(answer);
    }    
}

---

7-13. 그래프 최단 거리트) | BFS

풀이 설명

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/* 7-14. 그래프 최단 거리 (BFS) */
class Main3 {
    static int n, m, answer =0 ;
    static ArrayList<ArrayList<Integer>> graph; 
    static int[] ch, dis;//방문 체크용, 거리측정용
    //BFS() 함수
    public void BFS(int v) {
        //큐 필요
        Queue<Integer> queue = new LinkedList<>();
        ch[v] = 1; //들어온 v에 대한 방문 체크
        dis[v]= 0; //등로은 v에 대한 거리 일단 0 세팅
        queue.offer(v);//큐에 담음

        while(!queue.isEmpty()) {
            //일단 큐 하나 뽑음 
            int cv = queue.poll();
            //이 cv에 연결된 정점 탐색
            for(int nv : graph.get(cv)) {
                if(ch[nv] == 0){
                    ch[nv] =1;
                    queue.offer(nv);
                    dis[nv] = dis[cv]+1;//직전 cv의 거리+1
                }
            }
        }
    }    
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();

        graph = new ArrayList<ArrayList<Integer>>();
        //그래프 내부에 각 정점에 대한 정보 담을 ArrayList 객체 생성
        for(int i=0; i<=n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n+1];
        dis = new int[n+1];
        //각 정점a 대한 연결 b 정보 담음 
        for(int i=0; i<m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);
        }
        //호출 2~n까지 최단거리 출력
        T.BFS(1);
        for(int i=2; i<=n; i++) {
            System.out.println(i+" : "+dis[i]);
        }
    }    
}

---