그래프와 인접행렬 & 인접리스트

그래프란?

• Vertex(node)와 Edge로 이루어진 것
• 그래프의 종류 3가지

1. 무방향 그래프 (양방향 그래프)
   

• 인접 행렬로 표현 (2차원 배열)
  
• 1은 연결된 정보
• 행에서 열로 이동한다라고 생각
• 행(node 1,2,3,4,5)이 증가하면서 연결된 열(node 1,2,3,4,5) 찾기
  graph[a][b]=1;
  graph[b][a]=1; 료 표현

2. 방향 그래프
   

• 방향 그래프는 연결된 정보만 1로 연결
• 행에서 다음 열(Node)로 연결하는 것이다.
  

3. 가중치 방향 그래프
   

• 안에 가중치를 넣어줌
• 1번과 2번이 연결된 가중치는 2이다. ...
  

경로 탐색 (인접행렬)

이슈

• 다음으로 가야 할 노드를 방문처리 해야되는데 들어온 노드를 방문처리하였기 때문에 문제 생김
• 따라서 순서는 다음과 같다
• if문으로 종료 조건을 명시한다
• for문을 돌면서 다음으로 방문할 노드가 연결되어 있을경우, 다음 노드를 방문처리 (현재 노드를 방문처리하는것이 아니다!)
• 그리고 dfs를 재귀로 돌린다.
• 돌린 후에는 다시 방문을 풀어준다.

package inflearn.section7_dfs;
import java.util.*;
public class 인접행렬 {
    static int arr[][];
    static int check[];
    static int answer;

    public void dfs(int node,int n) {

        if (node==n) { // 종료 조건
            answer++;
        }

        // for문은 맞는것 같은데
        else {
            for (int i=1;i<=n;i++) {
                // 도착했으면 종료
                // 종료 조건이 이상한데?!
                if (arr[node][i]==1 && check[i]==0) { // 여기가 틀렸었음, 다음으로 가야 할 노드이기 때문에 check[i]=0으로 해야됨
                    check[i]=1; // 다음으로 가야 할 노드를 방문처리
                    dfs(i,n); // 다음 노드 (노드, 최종 목적지)
                    check[i]=0; // 다 방문 후에는 다시 체크 풀어줌
                }
            }
        }

    }

    public static void main(String[] args) {
        인접행렬 m1=new 인접행렬();

        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt(); //5 (노드)
        int m=scan.nextInt(); //9 (간선)
//        arr[][]=new int[n+1][n+1]; // 각각을 숫자로 표현하기 위해 +1로 증가
        arr=new int[n+1][n+1];
        for (int i=0;i<m;i++) {
            int a=scan.nextInt();
            int b=scan.nextInt();
            arr[a][b]=1;
        }

//        for (int i=1;i<arr.length;i++) {
//            for (int j=1;j<arr.length;j++) {
//                System.out.print(arr[i][j]);
//            }
//            System.out.println();
//        }

        // 방문 리스트는 노드를 적어준다.
        check=new int[n+1];
        answer=0;

        // 첫번째 방문했다고 여기서 미리 해주기
        check[1]=1;
        m1.dfs(1,n);
        System.out.println(answer);
    }

}

인접리스트

• 언제 사용?
• 정점이 너무 많으면 N*N행렬로 만들어야 되기 때문에 너무 커짐
• N이 100까지는 인접행렬로 해도 된다.
• 그 이상은 인접리스트로 해결해야 됨
• 연결된것만 list로 만들어 줌
• ArrayList이용

// 갈수 있는 정보만 넣어준다. 
arraylist1=[2,3,4]
arraylist2=[1,3]
arraylist3=[4]
arraylist4=[2,5]
arraylist5=[]

• 이렇게 하면 graph[a][b]를 할 필요 없음 -> 가는곳은 모두 적어주었기 때문에 방문한 check배열만 보면 됨
• 핵심은 arraylist안에 arraylist 넣기
• node개수만큼 arraylist 생성하기

package inflearn.section7_dfs;
// 인접리스트는 Arraylist를 이용

import java.util.*;
public class 인접리스트 {

    static int answer=0;
    static int n=0;
    // arraylist안에 arraylist
    // 연결된 정점을 표현하기 위해
    static ArrayList<ArrayList<Integer>> graph;
    static int[]check;

    public void dfs(int v) {
        if (v==n) {
            // 종료
            answer++;
        }
        else {
            // arraylist에 접근할때는 for each사용
            for (int nv:graph.get(v)) {
                // v번 노드와 연결된것은 nv
                if (check[nv]==0) {
                    check[nv]=1;
                    dfs(nv);
                    check[nv]=0;
                }
            }
        }

    }

    public static void main(String[] args) {
        인접리스트 m1=new 인접리스트();
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        int m=scan.nextInt();

        graph=new ArrayList<>();
        //n개의 arraylist 추가
        for (int i=0;i<=n;i++) {
            graph.add(new ArrayList<>());
        }

        for (int i=1;i<=m;i++) {
            int a=scan.nextInt();
            int b=scan.nextInt();
            graph.get(a).add(b); // 1번 arraylist에 연결 정보를 넣는다.
        }
        // 첫번째 방문은 방문처리
        check=new int [n+1];
        check[1]=1;
        m1.dfs(1);
        System.out.println(answer);

    }

}

인접리스트 + BFS로 최단 거리 찾기

해결방법

• DIS를 이용
  - DIS는 최단거리를 기록하는 배열
  - 각 노드까지 가는 최단거리를 기록

  • dis[n]=dis[n-1]+1 //dis[n-1]에는 해당 노드까지 가는 최단거리가 기록
    

• 이슈
  - 최단거리는 갔던 Node를 다시 풀어주지 않는다. (check배열)
  - 인접리스트는 arraylist를 사용하며 for Each를 사용해서 풀자

코드

package inflearn.section7_bfs;
// 인접리스트로 그래프 최단 거리 구하기
// 최단거리를 기록하는 곳은 dis배열을 이용한다
import java.util.*;
public class 인접리스트 {
    static ArrayList<ArrayList<Integer>>graph;
    static int check[];
    static int dis[];
    static int n;

    public void bfs(int node) {
        Queue<Integer>queue=new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            int curr=queue.poll();
            int size=queue.size();
            for (int nx:graph.get(curr)) {
                if (check[nx]==0) {
                    check[nx]=1;
                    queue.add(nx);
                    dis[nx]=dis[curr]+1; // 현재 연결된 거에 +1해주기
//                    check[nx]=0; // 최단거리는 갔던 곳을 또 안가기 때문에 이건 해주지 않는다.
                }
            }
        }

    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        int m=scan.nextInt();

        graph=new ArrayList<>();
        for (int i=0;i<=n;i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i=0;i<m;i++) {
            int a=scan.nextInt();
            int b=scan.nextInt();
            graph.get(a).add(b);
        }

        check=new int[n+1];
        dis=new int[n+1];


        인접리스트 bf=new 인접리스트();
        check[1]=1;
        dis[1]=0;
        bf.bfs(1);

        // 2부터 ~N까지 출력해보기
        for (int i=2;i<=n;i++) {
            System.out.println(i + ":" + dis[i]);
        }
    }
}