본문 바로가기

728x90

java39

[graph] 인접 리스트로 무방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 각 정점에 대한 인접 정점들을 연결 리스트로 만드는 것 리스트의 각 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성된다. 어떤 정점의 연결 리스트는 그 정점에 인접한 정점의 수(= 정점의 차수)만큼 노드가 연결되어 있다. 정점 i의 차수 = i에 연결되어 있는 노드 수 ex) 정점 2의 차수 = 3 JAVA 자료구조 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTo.. 2023. 3. 4.

[graph] 인접 배열로 방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 앞의 무방향 그래프를 구현한 게시글과 마찬가지로 n X n 이차원 배열(정점의 수에 대한 정방행렬)을 사용하여 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 저장한다. 행렬의 대각선 값은 항상 0이다. 그러나 ≠ 이므로 대칭을 이루지는 않는다. 행 i의 합 = 정점 i의 진출 차수 열 i의 합 = 정점 i의 진입 차수 ex) 정점 2의 진출 차수 = 0 + 0 + 1 + 1 = 2 정점 2의 집입 차수 = 1 + 0 + 0 + 0 = 1 JAVA 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java... 2023. 3. 4.

[graph] 인접 배열로 무방향 그래프 구현하기 ★ 정점의 개수 n개 , 모서리의 개수 m개 ★ 그래프를 구성하는 정점에 대해서 두 정점을 연결하는 간선의 유무를 저장하는 방법 n X n 이차원 배열(정점의 수에 대한 정방행렬)을 사용하여 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 저장한다. 이때, 하나의 정점에서 자기 자신으로 간선(=자체 간선)은 존재할 수 없으므로 행렬의 대각선 값은 항상 0 무방향 그래프의 경우 행렬의 (i, j)와 (j,i)의 값이 같으므로 대각선을 중심으로 대칭을 이룬다. 무방향 그래프에서 행 i의 합 = 열 i의 합 = 정점 i의 차수 ex) 정점 2의 차수 = 2행의 합(=1+0+1+1) = 2열의 합(=1+0+1+1) = 3 JAVA로 구현한 코드 import java.io.BufferedReader;.. 2023. 3. 4.

이전 1 2 3 다음

728x90

티스토리툴바