이것은 "Practical Computer Science" 시리즈의 다음 편으로, Ruby를 사용하여 실제 문제를 해결하기 위해 고전적인 컴퓨터 과학 개념을 적용하는 방법을 배우게 될 것입니다.
오늘은 그래프 이론에 대해 이야기하겠습니다. .
이진 트리에 대해 들어본 적이 있을 것입니다. 이진 트리는 다음과 같습니다.
문제는 이진 트리가 그래프의 특수한 버전일 뿐이므로 그래프가 얼마나 널리 퍼져 있는지에 대한 아이디어를 제공해야 한다는 것입니다.
그래프 이론의 기초에 대한 개요부터 시작하여 몇 가지 실용적인 용도와 이를 Ruby에서 구현하는 방법을 살펴보겠습니다!
그래프 기초
그래프는 두 가지 요소로 구성됩니다.
- 노드(또는 꼭짓점)
- 가장자리
하나의 노드는 지도를 나타내는 그래프에서 도시 또는 거리와 같은 그래프의 한 요소를 나타냅니다. 가장자리는 노드 간의 연결을 나타냅니다.
컴퓨터 과학이나 수학 책을 보면 다음 공식으로 정의된 그래프를 볼 수 있습니다. G(V, E) .
G 위치 그래프, V를 의미합니다. 정점 및 E의 집합입니다. 가장자리의 집합입니다.
그래프는 유향 또는 무향일 수 있습니다. 즉, 한 방향(유향 그래프) 또는 양방향(무향 그래프)으로만 이동할 수 있습니다.
가장 인기 있는 그래프 유형은 방향성 비순환 그래프입니다. (가리비). 비순환은 루프가 없고 역추적할 방법이 없음을 의미합니다.
그래프의 용도
기본 사항에 대한 개요를 살펴보았으므로 이제 그래프의 몇 가지 일반적인 용도를 살펴보겠습니다.
그래프를 사용하여 다음과 같은 작업을 수행할 수 있습니다.
- 두 위치 사이의 가장 짧은(또는 가장 긴) 경로 찾기
- 두 항목이 서로 관련되어 있는지 확인
- 추천 엔진 구축
- 종속성 분석
또 다른 예는 목적지에 대한 최적의 경로를 찾는 것입니다(GPS 장치를 생각하십시오).
그래프 구현 및 사용 방법
자신만의 그래프 구현을 작성할 수 있지만 이 기사에서는 이미 구현한 RGL gem을 사용할 것입니다.
RGL을 사용하여 기본 그래프를 만들려면:
require 'rgl/adjacency' graph = RGL::DirectedAdjacencyGraph.new graph.add_edge 1,2 graph.add_edge 3,4 graph.add_edge 1,4 graph.add_edge 4,3
이 코드는 다음 그래프를 생성합니다.
다음과 같이 그래프의 그래픽 표현을 얻을 수 있습니다.
require 'rgl/dot' graph.print_dotted_on
그런 다음 점 언어를 처리할 수 있는 사이트에서 해당 메서드의 출력을 복사합니다. 이것처럼.
또는 컴퓨터에 Graphviz를 설치하여 로컬에서 이미지를 생성할 수 있습니다.
이제 그래프가 있으므로 정보를 찾기 위해 그래프를 탐색할 수 있습니다.
그래프 검색을 위한 두 가지 기본 알고리즘이 있습니다. :
- 너비 우선 검색(BFS)
- 깊이 우선 탐색(DFS)
BFS에서는 가장 가까운 노드를 먼저 가져오고 DFS에서는 모든 노드에 대해 가능한 한 깊게 이동합니다. 이러한 알고리즘은 스택 데이터 구조를 사용하여 구현할 수 있습니다.
RGL gem은 이미 다음 알고리즘을 구현하고 있습니다.
require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2]
그래프를 다시 보고 눈만 사용하여 이 알고리즘이 수행한 경로를 따르십시오(원하는 경우 손가락도 사용할 수 있음). 그러면 무슨 일이 일어나고 있는지 이해하는 데 도움이 될 것입니다.
가중 그래프
그래프에 가중치 형태로 더 많은 정보를 추가하여 더 유용하게 만들 수 있습니다.
두 노드 사이의 경로인 가장자리에 가중치가 부여됩니다. ("정점"이라고도 함). 이 가중치는 한 지점에서 다른 지점으로 이동하는 비용을 나타냅니다.
예를 들어 그래프 형태의 국가 지도가 있고 가능한 한 최단 시간에 특정 목적지에 도달하려는 경우 가중치는 두 도시 간의 거리를 나타냅니다.
또는 컴퓨터 네트워크가 있는 경우 가중치는 특정 네트워크에 도달하는 데 필요한 홉 수를 나타낼 수 있습니다.
<블록 인용>“컴퓨터 네트워킹에서 홉은 소스와 대상 사이의 경로 중 하나입니다. 데이터 패킷은 원본과 대상 사이를 이동할 때 브리지, 라우터 및 게이트웨이를 통과합니다. 패킷이 다음 네트워크 장치로 전달될 때마다 홉이 발생합니다." – 위키피디아
다음은 가중 그래프의 코드 예입니다.
graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"
edge_weights =
{
["New York", "Los Angeles"] => 2445,
["Los Angeles", "Chicago"] => 2015,
["Los Angeles", "Houston"] => 1547,
["Chicago", "Houston"] => 939,
["Seattle", "Los Angeles"] => 1548
}
edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }
이제 한 지점에서 다른 지점으로 가는 최단 경로를 찾을 수 있습니다. 이것이 바로 다음 섹션의 주제입니다!
최단 경로 찾기
그래프 내에서 최단 경로를 찾는 데 널리 사용되는 알고리즘은 "Dijkstra의 최단 경로" 알고리즘입니다.
가중치 그래프가 주어지면 Dijkstra 알고리즘을 사용하여 이 질문을 해결할 수 있습니다.
"A 지점에서 B 지점으로 가는 가장 빠른 방법은 무엇입니까?"
다음은 RGL gem을 사용한 코드 예입니다.
p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"]
이것은 그래프에 있는 정보를 사용하여 뉴욕에서 휴스턴까지의 최단 경로를 알려줍니다.
요약
그래프 데이터 구조가 무엇이고 RGL gem과 함께 사용하는 방법을 배웠습니다.
또한 DFS, BFS 및 Dijkstra와 같은 그래프 작업을 위한 일반적인 알고리즘에 대해서도 배웠습니다.
이 게시물을 공유하는 것을 잊지 마세요 더 많은 사람들이 즐길 수 있도록 유용하게 활용하셨다면 🙂