그래프정리 및 구현

무방향 그래프 : 간선에 방향이 없음
방향 그래프 :  간선에 방향이 있음
완전 그래프 : 모든 정점에 간선이 있고, 정점끼리 모두 연결되어 있음
가중치 그래프 : 간선에 가중치가 있음

[ 구현 ]
1. 인접행렬
- 2차원 배열 사용
- 연결된 정점 찾기 빠르고 구현 쉬움
- O(n^2)

public static void main(String[] args) {
    int[][] edges = new int[][] {
    	{1, 2}, {1, 3}, {1, 4}, {3, 4}
    };

    int n = 4; //정점의 개수

    int[][] matrix = new int[n + 1][n + 1];

    for(int[] edge : edges) {
        matrix[edge[0]][edge[1]] = 1;
        matrix[edge[1]][edge[0]] = 1;
    }
}

2. 인접리스트
- 공간낭비가 적음
- 인접행렬보다 구현이 어려움

- (1) 배열 + 리스트

public static void main(String[] args) {
    int[][] edges = new int[][] {
    	{1, 2}, {1, 3}, {1, 4}, {3, 4}
    };

    int n = 4;

    ArrayList<Integer>[] list = new ArrayList[n + 1];

    for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();

    for(int[] edge : edges) {
        list[edge[0]].add(edge[1]);
        list[edge[1]].add(edge[0]);
    }
}

- (2) 리스트 + 리스트

public static void main(String[] args) {
    int[][] edges = new int[][] {
    	{1, 2}, {1, 3}, {1, 4}, {3, 4}
    };

    int n = 4;

    ArrayList<ArrayList<Integer>> list = new ArrayList<>();

    for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>());

    for(int[] edge : edges) {
        list.get(edge[0]).add(edge[1]);
        list.get(edge[1]).add(edge[0]);
    }
}

---

이렇게 그래프를 구현할 수 있다.

이 그래프를 조사하기 위한 방법으로는 크게 DFS,BFS가 있다.

DFS는 깊이우선탐색으로, stack자료구조를 이용한다.

BFS는 너비우선탐색으로, Queue자료구조를 이용한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.*;
import java.math.BigInteger;


public class Main {

	public static int n;
	public static int m;
	public static int v;
	public static ArrayList<Integer>[] adjList;
	public static boolean[] visited;

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken()); //vertex
		m = Integer.parseInt(st.nextToken()); //path
		v = Integer.parseInt(st.nextToken()); //start node
		
	
		visited = new boolean[n+1]; //방문 여부를 검사할 배열
		adjList =  new ArrayList[n+1];

		for (int i = 0; i<= n; i++) {
			
			adjList[i] = new ArrayList<Integer>();
			
		}
		
	
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			adjList[v1].add(v2);
			adjList[v2].add(v1);
		}
		
		for (int i = 1; i <= n; i++) {
			Collections.sort(adjList[i]); //방문 순서를 위해 오름차순 정렬
		}
			
		dfs_list(v);
		Arrays.fill(visited, false);
		bfs_list(v);
//		bfs_list(v, adjList, visited);
		
	}
 
    public static void dfs_list (int vertex) {
         
    	Stack<Integer> stack = new Stack<>();
    	stack.push(vertex);
    	
    	visited[vertex] = true;
    	while (!stack.isEmpty()) {
    		int curr = stack.pop();
    					
    		for (int i = 0; i < adjList[curr].size(); i++) {
				int child = adjList[curr].get(i);
				if (!visited[child]) {
					dfs_list(child);
				}
			}    	
    	}
    	
    }
    
    public static void bfs_list(int vertex) {
   	 	StringBuilder sb = new StringBuilder();
   	 	sb.append("\n");
    	Queue<Integer> queue = new LinkedList<Integer>(); //큐를 만들어
   
    	queue.add(vertex); //큐에다가 넣어
    	visited[vertex] = true; //시작경로는 일단 방문했다고 해
    	
    	while(!queue.isEmpty()) {
    		
    		int curr = queue.poll();
    		sb.append(curr).append(" ");
    		Iterator<Integer> iter = adjList[curr].listIterator();

    		while(iter.hasNext()) { //연결리스트에 다음 값이 들어 있는 지 확인
    			int idx = iter.next();
        		
            		if (!visited[idx]) {
            			visited[idx] = true;
            			queue.add(idx);
            	    	

            		}
            		
    		}	
    		
	    	
  
    	}
    	
    	
    	System.out.println(sb);

  		        	


    }
}