[java] 그래프 만들기 ( 인접 리스트 구현)

<학습 목표>

- 그래프를 모양을 보고 => 인접 리스트 형태로 구현 =>   ArrayList<ArrayList<Integer>> graph

- 그래프는 총 4가지 종류 - 무방향 , 방향 , 가중치 무방향 , 가중치 방향

- 가중치가 있을 때 구현하는 방법은?

 

1. 무방향 그래프

방향 x, 가중치 x

 

구현 Code

public class Main{
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // n: 정점의 갯수 , m: 간선의 갯수
        int n = 5;
        int m = 5;
        graph = new ArrayList<ArrayList<Integer>>();
        
        // 
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            setNoDirectionGraph(x, y);
        }
        
        for(int i=1; i<=n; i++){
            System.out.print(i + "-");
            for(int j : graph.get(i)){
                System.out.print(j+ ",");
            }
            System.out.println();
        }
    }


    public static void setNoDirectionGraph(int x, int y){
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
    
}

 

2. 방향 그래프

방향 o , 가중치 x

 

구현 Code

public class Main{
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter  bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // n: 정점의 갯수 , m: 간선의 갯수
        int n = 5;
        int m = 5;
        graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            setDirectionGraph(x, y);
        }

        for(int i=1; i<=n; i++){
            System.out.print(i + "->");
            for(int j : graph.get(i)){
                System.out.print(j+ ",");
            }
            System.out.println();
        }
    }

    public static void setDirectionGraph(int x, int y){
        graph.get(x).add(y);
    }

}

 

3. 가중치 무방향 그래프

방향 x, 가중치 o

//정점과 가중치를 포함하는 class 생성
class Edge{
    int node;
    int weigth;

    public Edge(int node, int weigth){
        this.node = node;
        this.weigth = weigth;
    }
}

public class Main{
    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter  bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // n: 정점의 갯수 , m: 간선의 갯수
        int n = 5;
        int m = 5;
        graph = new ArrayList<ArrayList<Edge>>();

        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
           
            setNoDirectionWeigthGraph(x,y,w);
        }
        
        for(int i=1; i<=n; i++){
            System.out.print(i + "-");
            for(Edge e : graph.get(i)){
                System.out.print("node :" + e.node+ " ");
                System.out.print("weight :" +  e.weigth+ ",");
            }
            System.out.println();
        }
    }
    
    public static void setNoDirectionWeigthGraph(int x, int y, int w){
        graph.get(x).add(new Edge(y,w));
        graph.get(y).add(new Edge(x,w));
    }

}

4. 가중치 방향 그래프

방향 o , 가중치 o

//정점과 가중치를 포함하는 class 생성
class Edge{
    int node;
    int weigth;

    public Edge(int node, int weigth){
        this.node = node;
        this.weigth = weigth;
    }
}

public class Main{
    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter  bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // n: 정점의 갯수 , m: 간선의 갯수
        int n = 5;
        int m = 5;
        graph = new ArrayList<ArrayList<Edge>>();

        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            setDirectionWeigthGraph(x,y,w);
        }
        System.out.println();
        for(int i=1; i<=n; i++){
            System.out.print(i + "-");
            for(Edge e : graph.get(i)){
                System.out.print("node :" + e.node+ " ");
                System.out.print("weight :" +  e.weigth+ ",");
            }
            System.out.println();
        }
    }


    public static void setDirectionWeigthGraph(int x, int y, int w){
        graph.get(x).add(new Edge(y, w));
    }
}