グラフィックと隣接マトリクス&隣接リスト

グラフとは?

無方向図(双方向図)

隣接行列(2 D配列)として表される

方向図

行から次の列に接続します.

加重方向図

1番と2番の接続の重み付けは2...

ブラウズパス(隣接マトリクス)

話題

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);
    }

}

りんせつひょう

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

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[n]=dis[n-1]+1/dis[n-1]このノードまでの最短距離を記録する

コード#コード#

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]);
        }
    }
}