java graph tutorial how implement graph data structure
이 포괄적 인 Java 그래프 자습서에서는 그래프 데이터 구조를 자세히 설명합니다. 여기에는 Java에서 그래프를 생성, 구현, 표현 및 트래버스하는 방법이 포함됩니다.
그래프 데이터 구조는 주로 다양한 지점을 연결하는 네트워크를 나타냅니다. 이러한 점을 정점이라고하며 이러한 정점을 연결하는 링크를 '가장자리'라고합니다. 따라서 그래프 g는 이러한 정점을 연결하는 정점 V와 가장자리 E의 집합으로 정의됩니다.
그래프는 주로 컴퓨터 네트워크, 소셜 네트워크 등과 같은 다양한 네트워크를 나타내는 데 사용됩니다. 또한 소프트웨어 또는 아키텍처의 다양한 종속성을 나타내는 데 사용할 수도 있습니다. 이러한 종속성 그래프는 소프트웨어를 분석하고 때때로 디버깅하는 데 매우 유용합니다.
학습 내용 :
자바 그래프 데이터 구조
다음은 5 개의 정점 {A, B, C, D, E}과 {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}에 의해 주어진 간선이있는 그래프입니다. 모서리에 방향이 표시되지 않으므로이 그래프를 '무 방향 그래프'라고합니다.
위에 표시된 무 방향 그래프 외에도 Java에는 여러 가지 그래프 변형이 있습니다.
이러한 변형에 대해 자세히 살펴 보겠습니다.
그래프의 다른 변형
다음은 그래프의 몇 가지 변형입니다.
# 1) 유향 그래프
유 방향 그래프 또는 digraph는 간선이 특정 방향을 갖는 그래프 데이터 구조입니다. 그들은 한 정점에서 시작하여 다른 정점으로 절정에 이릅니다.
다음 다이어그램은 유 방향 그래프의 예를 보여줍니다.
위의 다이어그램에는 정점 A에서 정점 B까지의 가장자리가 있습니다. 그러나 B에서 A로 지정된 가장자리가없는 한 A에서 B는 무 방향 그래프에서와 같이 B에서 A와 동일하지 않습니다.
방향 그래프는 첫 번째와 마지막 정점이 같은 경로가 하나 이상있는 경우 순환됩니다. 위의 다이어그램에서 경로 A-> B-> C-> D-> E-> A는 방향성주기 또는 순환 그래프를 형성합니다.
반대로 방향성 비순환 그래프는 방향성주기가없는 즉,주기를 형성하는 경로가없는 그래프입니다.
# 2) 가중 그래프
가중 그래프에서 가중치그래프의 각 모서리와 연관됩니다. 가중치는 일반적으로 두 정점 사이의 거리를 나타냅니다. 다음 다이어그램은 가중 그래프를 보여줍니다. 방향이 표시되지 않으므로 이것은 무 방향 그래프입니다.
가중 그래프는 방향성 또는 무 방향성 일 수 있습니다.
그래프를 만드는 방법?
Java는 그래프 데이터 구조의 완전한 구현을 제공하지 않습니다. 그러나 Java의 Collections를 사용하여 프로그래밍 방식으로 그래프를 나타낼 수 있습니다. 벡터와 같은 동적 배열을 사용하여 그래프를 구현할 수도 있습니다.
일반적으로 HashMap 컬렉션을 사용하여 Java에서 그래프를 구현합니다. HashMap 요소는 키-값 쌍의 형식입니다. HashMap에서 그래프 인접 목록을 나타낼 수 있습니다.
그래프를 생성하는 가장 일반적인 방법은 인접 행렬 또는 인접 목록과 같은 그래프 표현 중 하나를 사용하는 것입니다. 다음으로 이러한 표현에 대해 논의한 다음 ArrayList를 사용할 인접 목록을 사용하여 Java에서 그래프를 구현합니다.
자바에서 그래프 표현
그래프 표현은 그래프 데이터가 컴퓨터의 메모리에 저장되는 방식 또는 기술을 의미합니다.
아래와 같이 두 가지 주요 그래프 표현이 있습니다.
인접 행렬
인접 행렬은 그래프의 선형 표현입니다. 이 행렬은 그래프의 정점과 가장자리의 매핑을 저장합니다. 인접 행렬에서 그래프의 정점은 행과 열을 나타냅니다. 즉, 그래프에 N 개의 꼭지점이 있으면 인접 행렬의 크기는 NxN입니다.
V가 그래프의 꼭지점 집합이면 교차 Mij인접 목록에서 = 1은 정점 i와 j 사이에 가장자리가 있음을 의미합니다.
이 개념을 더 잘 이해하기 위해 무 방향 그래프에 대한 인접 행렬을 준비하겠습니다.
위의 다이어그램에서 볼 수 있듯이 정점 A의 경우 교차점 AB와 AE는 A에서 B로, A에서 E로 가장자리가 있으므로 1로 설정됩니다. 마찬가지로 교차점 BA는 방향이 지정되지 않은 1로 설정됩니다. 그래프 및 AB = BA. 마찬가지로 모서리가있는 다른 모든 교차점을 1로 설정했습니다.
그래프가 향하는 경우 교차점 MijVi에서 Vj로 향하는 명확한 가장자리가있는 경우에만 1로 설정됩니다.
다음 그림에 나와 있습니다.
위의 다이어그램에서 볼 수 있듯이 A에서 B까지의 가장자리가 있습니다. 따라서 교차 AB는 1로 설정되지만 교차 BA는 0으로 설정됩니다. 이는 B에서 A로 향하는 가장자리가 없기 때문입니다.
꼭지점 E와 D를 고려하십시오. E에서 D와 D에서 E까지의 가장자리가 있음을 알 수 있습니다. 따라서 우리는 인접 행렬에서이 두 교차점을 모두 1로 설정했습니다.
이제 가중치가있는 그래프로 이동합니다. 가중치가 적용된 그래프에 대해 알고 있듯이 가중치라고도하는 정수가 각 모서리와 연관됩니다. 존재하는 에지에 대한 인접 행렬에이 가중치를 나타냅니다. 이 가중치는 '1'대신 한 정점에서 다른 정점으로 가장자리가있을 때마다 지정됩니다.
이 표현은 아래와 같습니다.
인접 목록
본질적으로 순차적 인 인접 행렬로 그래프를 나타내는 대신 연결된 표현을 사용할 수도 있습니다. 이 링크 된 표현을 인접 목록이라고합니다. 인접 목록은 연결 목록에 불과하며 목록의 각 노드는 꼭지점을 나타냅니다.
두 정점 사이에 가장자리가 있다는 것은 첫 번째 정점에서 두 번째 정점으로의 포인터로 표시됩니다. 이 인접 목록은 그래프의 각 정점에 대해 유지됩니다.
특정 노드에 대해 모든 인접 노드를 순회하면 인접 목록의 마지막 노드의 다음 포인터 필드에 NULL을 저장합니다.
이제 인접 목록을 보여주기 위해 인접 행렬을 나타내는 데 사용한 위의 그래프를 사용합니다.
위 그림은 무 방향 그래프에 대한 인접 목록을 보여줍니다. 각 정점 또는 노드에 인접 목록이 있음을 알 수 있습니다.
무 방향 그래프의 경우 인접 목록의 총 길이는 일반적으로 간선 수의 두 배입니다. 위 그래프에서 총 간선 수는 6이고 모든 인접 목록 길이의 합계 또는 합계는 12입니다.
이제 유 방향 그래프에 대한 인접 목록을 준비하겠습니다.
위 그림에서 볼 수 있듯이 방향 그래프에서 그래프의 인접 목록의 총 길이는 그래프의 간선 수와 같습니다. 위의 그래프에는 9 개의 간선이 있으며이 그래프에 대한 인접 목록 길이의 합계 = 9입니다.
이제 다음 가중 방향 그래프를 고려해 보겠습니다. 가중치가 적용된 그래프의 각 모서리에는 연관된 가중치가 있습니다. 따라서이 그래프를 인접 목록으로 나타낼 때 각 목록 노드에 가장자리의 가중치를 나타내는 새 필드를 추가해야합니다.
가중 그래프의 인접 목록은 다음과 같습니다.
위의 다이어그램은 가중 그래프와 인접 목록을 보여줍니다. 인접 목록에 각 노드의 가중치를 나타내는 새 공간이 있습니다.
자바에서 그래프 구현
다음 프로그램은 Java에서 그래프 구현을 보여줍니다. 여기서는 그래프를 나타 내기 위해 인접 목록을 사용했습니다.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i 산출:
그래프 순회 자바
데이터의 존재를 검색하는 것과 같은 의미있는 작업을 수행하려면 각 꼭지점과 그래프 가장자리를 한 번 이상 방문하도록 그래프를 탐색해야합니다. 이는 그래프를 순회하는 데 도움이되는 일련의 지침에 불과한 그래프 알고리즘을 사용하여 수행됩니다.
Java에서 그래프를 탐색하기 위해 지원되는 두 가지 알고리즘이 있습니다. .
- 깊이 우선 순회
- 폭 우선 순회
깊이 우선 순회
깊이 우선 검색 (DFS)은 트리 또는 그래프를 탐색하는 데 사용되는 기술입니다. DFS 기술은 루트 노드로 시작한 다음 그래프로 더 깊이 들어가 루트 노드의 인접 노드를 탐색합니다. DFS 기술에서 노드는 탐색 할 자식이 더 이상 없을 때까지 깊이 방향으로 이동합니다.
리프 노드에 도달하면 (자식 노드가 더 이상 없음) DFS는 다른 노드로 역 추적하고 시작하며 유사한 방식으로 순회를 수행합니다. DFS 기술은 스택 데이터 구조를 사용하여 순회중인 노드를 저장합니다.
다음은 DFS 기술에 대한 알고리즘입니다.
연산
1 단계 : 루트 노드로 시작하여 스택에 삽입
2 단계 : 스택에서 항목을 꺼내 '방문한'목록에 삽입
3 단계 : '방문 됨'(또는 방문 목록에 있음)으로 표시된 노드의 경우 아직 방문으로 표시되지 않은이 노드의 인접 노드를 스택에 추가합니다.
4 단계 : 스택이 비워 질 때까지 2 단계와 3 단계를 반복합니다.
DFS 기법의 예시
이제 적절한 그래프 예제를 사용하여 DFS 기술을 설명합니다.
아래에 그래프의 예가 나와 있습니다. 탐색 된 노드를 저장하는 스택과 방문한 노드를 저장하는 목록을 유지합니다.
A로 시작하여 방문한 것으로 표시하고 방문한 목록에 추가합니다. 그런 다음 A의 모든 인접 노드를 고려하고 아래에 표시된대로 이러한 노드를 스택에 푸시합니다.
다음으로 스택에서 노드 즉 B를 꺼내 방문한 것으로 표시합니다. 그런 다음 '방문한'목록에 추가합니다. 이것은 아래에 나와 있습니다.
이제 우리는 A와 C 인 B의 인접 노드를 고려합니다.이 A 중 이미 방문한 노드입니다. 그래서 우리는 그것을 무시합니다. 다음으로 스택에서 C를 꺼냅니다. C를 방문한 것으로 표시합니다. C의 인접 노드 즉 E가 스택에 추가됩니다.
다음으로 스택에서 다음 노드 E를 꺼내 방문한 것으로 표시합니다. 노드 E의 인접 노드는 이미 방문한 C입니다. 그래서 우리는 그것을 무시합니다.
이제 노드 D 만 스택에 남아 있습니다. 따라서 방문한 것으로 표시합니다. 인접한 노드는 이미 방문한 A입니다. 그래서 우리는 그것을 스택에 추가하지 않습니다.
이 시점에서 스택은 비어 있습니다. 이는 주어진 그래프에 대해 깊이 우선 순회를 완료했음을 의미합니다.
방문 목록은 깊이 우선 기법을 사용하여 순회의 최종 시퀀스를 제공합니다. 위 그래프의 최종 DFS 시퀀스는 A-> B-> C-> E-> D입니다.
DFS 구현
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list(); // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i 산출:
DFS의 응용
# 1) 그래프에서주기 감지 : DFS는 에지로 역 추적 할 수있을 때 그래프에서주기를 쉽게 감지 할 수 있습니다.
# 2) 길 찾기 : DFS 그림에서 이미 보았 듯이 두 개의 정점이 주어지면이 두 정점 사이의 경로를 찾을 수 있습니다.
# 3) 최소 스패닝 트리 및 최단 경로 : 가중치가없는 그래프에서 DFS 기술을 실행하면 최소 스패닝 트리와 짧은 경로가 제공됩니다.
# 4) 토폴로지 정렬 : 작업을 예약해야 할 때 토폴로지 정렬이 사용됩니다. 우리는 다양한 직업간에 의존성이 있습니다. 링커, 명령 스케줄러, 데이터 직렬화 등 간의 종속성을 해결하기 위해 토폴로지 정렬을 사용할 수도 있습니다.
폭 우선 순회
BFS (Breadth-first) 기술은 대기열을 사용하여 그래프의 노드를 저장합니다. DFS 기술과 달리 BFS에서는 그래프를 넓게 탐색합니다. 이것은 우리가 그래프 수준을 현명하게 횡단한다는 것을 의미합니다. 한 수준에서 모든 정점 또는 노드를 탐색 할 때 다음 수준으로 진행합니다.
다음은 폭 우선 순회 기법에 대한 알고리즘입니다. .
연산
BFS 기법에 대한 알고리즘을 살펴 보겠습니다.
BFS 기술을 수행해야하는 그래프 G가 주어집니다.
- 1 단계: 루트 노드로 시작하여 큐에 삽입하십시오.
- 2 단계: 그래프의 모든 노드에 대해 3 단계와 4 단계를 반복합니다.
- 3 단계 : 큐에서 루트 노드를 제거하고 방문 목록에 추가하십시오.
- 4 단계 : 이제 루트 노드의 모든 인접 노드를 큐에 추가하고 각 노드에 대해 2-4 단계를 반복합니다. (END OF LOOP)
- 6 단계 : 출구
BFS의 그림
아래에 표시된 예제 그래프를 사용하여 BFS 기술을 설명하겠습니다. '방문 됨'이라는 이름의 목록과 대기열이 유지되었습니다. 명확성을 위해 DFS 예제에서 사용한 것과 동일한 그래프를 사용합니다.
먼저 루트, 즉 노드 A로 시작하여 방문 목록에 추가합니다. 노드 A의 모든 인접 노드 즉, B, C 및 D가 대기열에 추가됩니다.
다음으로 큐에서 노드 B를 제거합니다. 방문 목록에 추가하고 방문한 것으로 표시합니다. 다음으로 큐에서 B의 인접 노드를 탐색합니다 (C는 이미 큐에 있음). 인접한 다른 노드 A가 이미 방문되었으므로 무시합니다.
다음으로 큐에서 노드 C를 제거하고 방문한 것으로 표시합니다. 방문 목록에 C를 추가하고 인접 노드 E가 대기열에 추가됩니다.
다음으로 대기열에서 D를 삭제하고 방문한 것으로 표시합니다. 노드 D의 인접 노드 A는 이미 방문 했으므로 무시합니다.
버전 제어를 자동화하도록 설계된 소프트웨어 패키지
이제 노드 E 만 대기열에 있습니다. 방문한 것으로 표시하고 방문한 목록에 추가합니다. E의 인접 노드는 이미 방문한 C입니다. 그러니 무시하십시오.
이 시점에서 큐는 비어 있고 방문 목록에는 BFS 순회의 결과로 얻은 시퀀스가 있습니다. 순서는 A-> B-> C-> D-> E입니다.
BFS 구현
다음 Java 프로그램은 BFS 기술의 구현을 보여줍니다.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list(); //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i 산출:
BFS 탐색의 응용
# 1) 가비지 수집 : 가비지 콜렉션을 복사하기 위해 가비지 콜렉션 기술에서 사용하는 알고리즘 중 하나는 'Cheney의 알고리즘'입니다. 이 알고리즘은 폭 우선 순회 기법을 사용합니다.
# 2) 네트워크에서 방송 : 네트워크의 한 지점에서 다른 지점으로의 패킷 브로드 캐스트는 BFS 기술을 사용하여 수행됩니다.
# 3) GPS 내비게이션 : BFS 기술을 사용하여 GPS를 사용하여 탐색하는 동안 인접 노드를 찾을 수 있습니다.
# 4) 소셜 네트워킹 웹 사이트 : BFS 기술은 특정 사람을 둘러싼 사람들의 네트워크를 찾기 위해 소셜 네트워킹 웹 사이트에서도 사용됩니다.
# 5) 가중치가 적용되지 않은 그래프에서 최단 경로 및 최소 스패닝 트리 : 비가 중 그래프에서 BFS 기술을 사용하여 최소 스패닝 트리와 노드 간의 최단 경로를 찾을 수 있습니다.
자바 그래프 라이브러리
Java는 프로그래머가 프로그램에서 항상 그래프를 구현하도록 의무화하지 않습니다. Java는 프로그램에서 그래프를 사용하는 데 직접 사용할 수있는 많은 준비된 라이브러리를 제공합니다. 이러한 라이브러리에는 그래프와 다양한 기능을 최대한 활용하는 데 필요한 모든 그래프 API 기능이 있습니다.
다음은 Java의 일부 그래프 라이브러리에 대한 간략한 소개입니다.
# 1) 구글 구아바 : Google Guava는 간단한 그래프, 네트워크, 값 그래프 등을 포함한 그래프와 알고리즘을 지원하는 풍부한 라이브러리를 제공합니다.
# 2) Apache Commons : Apache Commons는 그래프 데이터 구조 구성 요소와이 그래프 데이터 구조에서 작동하는 알고리즘이있는 API를 제공하는 Apache 프로젝트입니다. 이러한 구성 요소는 재사용이 가능합니다.
# 3) JGraphT : JGraphT는 널리 사용되는 Java 그래프 라이브러리 중 하나입니다. 간단한 그래프, 방향 그래프, 가중치 그래프 등을 포함하는 그래프 데이터 구조 기능과 그래프 데이터 구조에서 작동하는 알고리즘 및 API를 제공합니다.
# 4) SourceForge JUNG : JUNG은 'Java Universal Network / Graph'의 약자이며 Java 프레임 워크입니다. JUNG은 그래프로 표현하려는 데이터의 분석, 시각화 및 모델링을위한 확장 가능한 언어를 제공합니다.
또한 JUNG은 분해, 클러스터링, 최적화 등을위한 다양한 알고리즘과 루틴을 제공합니다.
자주 묻는 질문
Q # 1) Java에서 그래프 란 무엇입니까?
대답: 그래프 데이터 구조는 주로 연결된 데이터를 저장합니다. 예를 들면 사람의 네트워크 또는 도시의 네트워크. 그래프 데이터 구조는 일반적으로 정점이라고하는 노드 또는 점으로 구성됩니다. 각 정점은 가장자리라는 링크를 사용하여 다른 정점에 연결됩니다.
질문 # 2) 그래프의 유형은 무엇입니까?
대답: 다양한 유형의 그래프가 아래에 나열되어 있습니다.
- 선 그래프: 선 그래프는 시간에 따른 특정 속성의 변화를 표시하는 데 사용됩니다.
- 막대 그래프: 막대 그래프는 다양한 도시의 인구, 전국의 문맹률 등 개체의 숫자 값을 비교합니다.
이러한 주요 유형 외에도 그림 문자, 히스토그램, 영역 그래프, 산점도 등과 같은 다른 유형도 있습니다.
Q # 3) 연결된 그래프 란 무엇입니까?
대답: 연결된 그래프는 모든 꼭지점이 다른 꼭지점에 연결된 그래프입니다. 따라서 연결된 그래프에서 다른 모든 정점에서 모든 정점에 도달 할 수 있습니다.
질문 # 4) 그래프의 용도는 무엇입니까?
대답: 그래프는 다양한 응용 분야에서 사용됩니다. 그래프는 복잡한 네트워크를 나타내는 데 사용할 수 있습니다. 그래프는 소셜 네트워킹 응용 프로그램에서 사람의 네트워크를 나타 내기 위해 사용되며 인접한 사람이나 연결을 찾는 것과 같은 응용 프로그램에도 사용됩니다.
그래프는 컴퓨터 과학에서 계산의 흐름을 나타내는 데 사용됩니다.
질문 # 5) 그래프를 어떻게 저장합니까?
답 : 그래프를 메모리에 저장하는 방법에는 세 가지가 있습니다.
#1) 노드 또는 정점을 객체로, 모서리를 포인터로 저장할 수 있습니다.
#두) 행과 열이 꼭지점 수와 동일한 인접 행렬로 그래프를 저장할 수도 있습니다. 각 행과 열의 교차점은 가장자리의 유무를 나타냅니다. 가중치가 적용되지 않은 그래프에서 간선의 존재는 1로 표시되고 가중치 적용 그래프에서는 간선의 가중치로 대체됩니다.
#삼) 그래프를 저장하는 마지막 접근 방식은 그래프 정점 또는 노드 사이의 인접 에지 목록을 사용하는 것입니다. 각 노드 또는 정점에는 인접 목록이 있습니다.
결론
이 튜토리얼에서는 Java의 그래프에 대해 자세히 설명했습니다. 다양한 유형의 그래프, 그래프 구현 및 순회 기술을 탐색했습니다. 그래프를 사용하여 노드 간의 최단 경로를 찾을 수 있습니다.
다음 튜토리얼에서는 최단 경로를 찾는 몇 가지 방법을 논의하여 그래프를 계속 탐색 할 것입니다.
추천 도서
