[JAVA/자바 - 그래프] 인접 그래프 구현

[JAVA/자바 - 그래프] 인접 그래프 구현

728x90

오늘은 자바를 이용하여 인접리스트를 구현해보려고 합니다.

인접 리스트

인접 리스트는 다음과 같이 무방향 그래프가 존재할 때

정점의 개수만큼 리스트를 생성하고 정점의 리스트와 인접한 정점의 정보를 연결해주는 구조입니다.

인접 리스트

1. arraylist를 담을 수 있는 array list를 선언해줍니다.

2. 관계를 입력받습니다.

3. arraylist[from]에 to 값을 삽입해주고, arraylist[to]에 from값을 삽입해줍니다.

공간 복잡도: O(E)

※ V(vertex): 정점 / E(edge): 간선

import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ int N = 5; //정점 갯수 ArrayList[] list = (ArrayList[]) new ArrayList[N]; //인접 리스트 for(int i=0; i(); } for(int i=0; i

반응형

from http://yu1moo.tistory.com/56 by ccl(A) rewrite - 2021-09-16 12:27:30