인접리스트를 이용해 구현한 방향성 그래프
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; public class DirectedAdList { /* * 방향성이 있는 그래프를 인접 리스트로 구현 */ static int nV; //총 vertex 개수 static int nE; //총 edge 개수 public static void main(String[] args) { Scanner scan = new Scanner(System.in); nV = scan.nextInt(); nE = scan.nextInt(); ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList(); for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList()); //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트) for(int i=0;i<nE;i++) { int vertex1, vertex2; vertex1 = scan.nextInt(); vertex2 = scan.nextInt(); adList.get(vertex1).add(vertex2); } //인접리스트 출력 for(int i=0;i<nV;i++) { Iterator<Integer> iter = adList.get(i).iterator(); System.out.print(i); if(iter.hasNext()) System.out.print("-"); while(iter.hasNext()) System.out.print(iter.next() + " "); System.out.println(""); } } } | cs |
인접리스트를 이용해 구현한 비방향성 그래프
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | public class UndirectedAdList { /* * 비방향 그래프를 인접리스트를 통해 구현 * 비항향 그래프를 구현하기 위해 방향성 그래프로 변환하여 구현 * 그렇기에 edge정보를 담기위한 공간이 방향성 그래프에비해 많이듬(2배) * 정점과 간선의 개수가 증가하면 증가할수록 공간이 많이 필요하다. * 이를 해결하기 위해 인접행렬이 나옴 */ static int nV; //총 vertex 개수 static int nE; //총 edge 개수 public static void main(String[] args) { Scanner scan = new Scanner(System.in); nV = scan.nextInt(); nE = scan.nextInt(); ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList(); for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList()); //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트) for(int i=0;i<nE;i++) { int vertex1, vertex2; vertex1 = scan.nextInt(); vertex2 = scan.nextInt(); adList.get(vertex1).add(vertex2);//비방향 그래프이기 때문에 번갈아서 구현 adList.get(vertex2).add(vertex1);//비방향 그래프를 방향성그래프로 변환하여 구현하기에 //번갈아서 edge를 구현해야한다. } //인접리스트 출력 for(int i=0;i<nV;i++) { Iterator<Integer> iter = adList.get(i).iterator(); System.out.print(i); if(iter.hasNext()) System.out.print("-"); while(iter.hasNext()) System.out.print(iter.next() + " "); System.out.println(""); } } } | cs |
인접행렬를 이용해 구현한 방향성 그래프
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | import java.util.Scanner; public class DirectedAdMatrix { /* * 인접행렬을 이용해 구현한 방향성 그래프 */ static int nV; //총 vertex 수 static int nE; //총 edge 수 static int[][] adMatrix; public static void main(String[] args) { Scanner scan = new Scanner(System.in); nV = scan.nextInt(); nE = scan.nextInt(); adMatrix = new int[nV][nV]; for(int i=0;i<nE;i++) { int vertex1, vertex2; vertex1 = scan.nextInt(); vertex2 = scan.nextInt(); adMatrix[vertex2][vertex1] = 1; } for(int i=0;i<nV;i++) { System.out.print(i + "-" ); for(int j=0;j<nV;j++) { System.out.print(adMatrix[j][i]+ " "); } System.out.println(); } } } | cs |
인접행렬를 이용해 구현한 방향성 그래프
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | public class UndirectedADMatrix { /* * 인접행렬을 이용해 구현한 비방향성 그래프 */ static int nV; //총 vertex 수 static int nE; //총 edge 수 static int[][] adMatrix; public static void main(String[] args) { Scanner scan = new Scanner(System.in); nV = scan.nextInt(); nE = scan.nextInt(); adMatrix = new int[nV][nV]; for(int i=0;i<nE;i++) { int vertex1, vertex2; vertex1 = scan.nextInt(); vertex2 = scan.nextInt(); adMatrix[vertex2][vertex1] = 1; //비방향성이기에 같이 표현 adMatrix[vertex1][vertex2] = 1; } for(int i=0;i<nV;i++) { System.out.print(i + "-" ); for(int j=0;j<nV;j++) { System.out.print(adMatrix[j][i]+ " "); } System.out.println(); } } /* * 공간 복잡도가 vertex의 수 * vertex의 수 * 공간이 항상 미리 정해지기에 edge가 vertex에 비해 적을 경우 * 공간 낭비가 일어난다. * * 그래프가 드문드문이면 인접리스트 E<V*V * 촘촘하면 인접행렬 (행렬은 1비트만 사용) * * 간선을 찾는데 걸리는 시간 * 인접행렬 : 1 * 인접리스트 : V * * 모든 간선을 찾거나 방문하는데 걸리는 시간 * 인접행렬 : V*V * 인접리스트 : V+E */ } | cs |
'자료구조' 카테고리의 다른 글
| [Map] HashMap (0) | 2017.03.10 |
|---|---|
| [Set]HashSet의 특징 (1) | 2017.03.09 |
| [그래프]넓이 우선 탐색(BFS) (0) | 2017.03.07 |
| ArrayList와 LinkedList (0) | 2017.01.02 |
| Array 배열 for Java (0) | 2016.12.23 |