인접 행렬 (Adjacent Matrix) : 2차원 배열로 간단하게 표현, 메모리 낭비가 심하다
인접 리스트 (Adjacent List) : List를 이용하여 메모리 낭비가 적다, 구현이 복잡
인접 셋 (Adjacency Set)
간선의 배열
// list 배열로 그래프 간선 표현하기 -> 어느 한쪽이 고정되어 있을 때 많이 사용
// declare
public static ArrayList< Node > g [];
//init
g = new ArrayList[N+1];
for (int i = 0;i <= N; i++) {
g[i] = new ArrayList<>();
}
//input
for (int e = 1; e <= E; e++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 무방향 그래프
g[a].add(new Node(b,c));
g[b].add(new Node(a,c));
}
// 이중 리스트로 그래프 간선 표현하기 -> 메모리 최적으로 많이 사용된다
// LinkedList 를 사용하면 순차적으로 검색하여 찾아가기때문에 시간초과
// 따라서 ArrayList를 많이 사용
// declare
public static ArrayList < ArrayList < Integer > > graph;
// init
graph = new ArrayList< ArrayList < Integer > >();
// input
for (int i = 0; i < N+1; i++) {
graph.add(new ArrayList());
}
// adjacent list example
for (int i = 0; i < M; i++) {
int []temp = new int[2];
temp[0] = in.nextInt(); // src
temp[1] = in.nextInt(); // dst
graph.get(temp[0]).add(temp[1]); // from src to dst
}
// 한 정점에 붙어있는 인접 행렬 순회할때 참조
for (int[] next : g.get(cur)) { // 간단하게 나타낼수있다
// next ....
}
public static int bfs () {
int answer = 0;
dq = new ArrayDeque<>();
dq.add(new Node(1,1,input[1][1]));
visited[1][1] = true;
while (!dq.isEmpty()) {
Node cur= dq.pollFirst();
answer = cur.sum;
int nx = cur.x;
int ny = cur.y;
if (nx == M && ny == N) {
return answer;
}
for (int i = 0; i < 4; i++) {
nx = cur.x + x[i];
ny = cur.y + y[i];
if (nx < 1 || nx > M || ny < 1 || ny > N)
continue;
if (visited[ny][nx])
continue;
visited[ny][nx] = true;
if (input[ny][nx] == 1) {
dq.addLast(new Node(nx,ny,answer+input[ny][nx])); // 1을 맨 뒤에 넣는다
} else {
dq.addFirst(new Node(nx,ny,answer+input[ny][nx])); // 0을 맨 앞에 넣어 먼저 꺼낸다
}
}
}
return answer;
}
최단 경로 찾기
최단 거리 알고리즘 문제유형
비가중 그래프에서 최단 경로
가중 그래프에서 최단경로
최단 경로 알고리즘의 응용
한곳에서 다른 곳으로 이동하는 가장 빠른길 찾기
한 도시에서 다른 도시로 데이터를 보내거나 이동하는 가장 경제적인 방법 찾기
간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
// 가중치 그래프 init
mat = new ArrayList>();
for (int i = 1 ; i <= n+1; i++) {
mat.add(new ArrayList<>());
}
// 선언부
d = new int [n+1]; // 각 노드에서 최단거리 가중치 저장
path = new int [300]; // 잡하장 개수 <= 200
pq = new PriorityQueue<>((int [] a, int [] b)-> (a[1] > b[1])? 1: -1); // 거리가 짧은 순 오름차순
for (int i = 0; i < m; i++) {
int src = in.nextInt();
int dst = in.nextInt();
int value = in.nextInt();
mat.get(src).add(new int[] {dst, value}); // 양방향 그래프임
mat.get(dst).add(new int[] {src, value}); // 문제에서 "그 사이를 오가는데 필요한 시간"
}
// 다익스트라 알고리즘
public static void dijkstra (int src) {
pq.add(new int[] {src, 0}); // 현재 위치 + 해당 위치에서 가중치, 0 에서 시작
for (int i = 1; i < n+1; i++) {
d[i] = Integer.MAX_VALUE; // 각 시발점마다 초기화
}
d[src] = 0; // 시작점
while (!pq.isEmpty()) {
int [] node = pq.poll(); // 현재 시작점
int cur_node = node[0];
int cur_dist = node[1];
// 최적화 2021-03-26 추가 (나동빈님 다익스트라 강의 참조)
if (cur_dist > d[cur_node]) // 이미 방문이 끝난 것으로 간주
continue;
for (int i = 0; i < mat.get(cur_node).size(); i++) {
int next_node = mat.get(cur_node).get(i)[0];//현재노드에서 다음 노드로 이동할때 cost
int cost = mat.get(cur_node).get(i)[1]; //현재노드에서 다음 노드로 이동할때 cost
if (d[next_node] > cost + cur_dist) {
d[next_node] = cost + cur_dist; //최단거리 배열 업데이트
path [next_node] = cur_node; // 정답 출력을 위 next_node 최단거리를 위한 cur_node 인덱스 저장, 끝점에서 거꾸로 추적할 수 있다
pq.add(new int[] {next_node, d[next_node]}); // 다음노드 큐에 넣기
}
}
}
}
V = in.nextInt(); // 정점
E = in.nextInt(); // 간선
g = new int[V+1][V+1]; // 경로
for (int i = 0; i <= V; i++) {
for (int j = 0; j <=V; j++) {
g[i][j] = INF; // 최대값으로 세팅
}
}
for (int i = 0; i < E; i++) {
int from = in.nextInt();
int to = in.nextInt();
int value = in.nextInt();
// 경로 채우기
g[from][to] = value;
}
// 거쳐 가는 노드
for (int k = 1; k <= V; k++) {
// 출발 노드
for (int i = 1; i <= V; i++) {
// 도착 노드
for (int j = 1; j <= V; j++) {
g[i][j] = Math.min(g[i][j], g[i][k]+g[k][j]); // 기존 값과 k를 거쳐서 온 값 비교해 최소값 입력, 점화식 암기!!
}
}
}
for (int i = 1; i <= V; i++) {
answer = Math.min(g[i][i], answer); // 출력
}