7. 그래프

노드 관점

해당 노드에 연결된 다른 노드가 뭔지 알고싶을때

0: []
1: [3,2]
2: [1]
3: [4]

 

정수 노드

가중치가 없는 그래프

ArryList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// 노드 개수만큼 추가
for (int i = 1; i <= n; i++) {
    graph.add(new ArrayList<Integer>());
}

StringTokenizer st;
for(int j=0; j<m; j++){
    st = new StringTokenizer(br.readline());
    int s = Integer.valueOf(st.nextToken());
    int e = Integer.valueOf(st.nextToken());
    graph.get(s).add(e);
}


/* 간선 정보가 아래 처럼 들어온다.
간선 개수 m
1 3
3 4
5 6
*/

0: []
1: [3]
2: []
3: [4]
4: []
5: [6]
6: []

 

가중치 그래프

클래스로 구현하는 방법

class Node {
    int index;
    int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
}


ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 노드 개수만큼 추가
for (int i = 1; i <= n; i++) {
    graph.add(new ArrayList<Node>());
}

StringTokenizer st;
for(int j=0; j<m; j++){
    st = new StringTokenizer(br.readline());
    int s = Integer.valueOf(st.nextToken());
    int e = Integer.valueOf(st.nextToken());
    int w = Integer.valueOf(st.nextToken());
    graph.get(s).add(new Node(e,w));
}

0: []
1: [Node(index=2, distance=5)]
2: [Node(index=3, distance=10)]
3: []

 

단순 배열을 사용하는 방법

int n = 4; // 노드의 개수
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}


StringTokenizer st;
for(int j=0; j<m; j++){
    st = new StringTokenizer(br.readline());
    int s = Integer.valueOf(st.nextToken());
    int e = Integer.valueOf(st.nextToken());
    int w = Integer.valueOf(st.nextToken());
    graph.get(s).add(new int[] {e,w});
}

0: 
1: [2, 5] 
2: [3, 10] 
3:

 

다른 타입 노드 표현

HashMap을 통해 구현 가능

HashMap<Character, ArrayList<Character>> graph = new HashMap<>();
int n; // 노드의 개수
int m; // 간선의 개수

// 노드 입력받기
System.out.println("노드 개수 n을 입력하세요: ");
n = Integer.parseInt(br.readLine());
System.out.println("노드를 입력하세요 (예: A B C): ");
StringTokenizer nodeTokenizer = new StringTokenizer(br.readLine());
while (nodeTokenizer.hasMoreTokens()) {
    char node = nodeTokenizer.nextToken().charAt(0);
    graph.put(node, new ArrayList<>());
}

// 간선 입력받기
System.out.println("간선 개수 m을 입력하세요: ");
m = Integer.parseInt(br.readLine());
System.out.println("간선을 입력하세요 (예: A B): ");
for (int j = 0; j < m; j++) {
    StringTokenizer edgeTokenizer = new StringTokenizer(br.readLine());
    char start = edgeTokenizer.nextToken().charAt(0);
    char end = edgeTokenizer.nextToken().charAt(0);
    graph.get(start).add(end);
}

A: [B]
B: [C]
C: []

 

간선 관점

그래프를 형성하는 간선들을 확인하고 싶을때 사용

class Edge implements Comparable<Edge> {
    int distance;
    int nodeA;
    int nodeB;

    public Edge(int distance, int nodeA, int nodeB) {
        this.distance = distance;
        this.nodeA = nodeA;
        this.nodeB = nodeB;
    }
}

ArrayList<Edge> edges = new ArrayList<>();

// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    int cost = sc.nextInt();
    edges.add(new Edge(cost, a, b));
}

[Edge(distance=4, nodeA=1, nodeB=2), Edge(distance=6, nodeA=2, nodeB=3)]