JavaScript로 그래프 구현

그래프는 꼭짓점(노드라고도 함) 집합과 이들 사이의 관계(또는 가장자리)를 나타내는 비선형 데이터 구조입니다. 꼭짓점은 엔터티나 객체를 나타내고, edges는 꼭짓점 간의 관계나 연결을 나타냅니다. 그래프는 소셜 네트워크, 교통 시스템, 정보 흐름 등 다양한 유형의 관계를 모델링하는 데 사용될 수 있습니다.

그래프에는 방향 그래프(방향 그래프라고도 함)와 무방향 그래프라는 두 가지 주요 유형이 있습니다. 유향 그래프에서 간선은 한 방향을 가지며 한 방향, 즉 시작 꼭지점에서 끝 꼭지점까지만 이동할 수 있습니다. 무방향 그래프에서는 간선에 방향이 없으며 양방향으로 탐색할 수 있습니다.

JavaScript로 이미지 구현

인접 행렬이나 인접 목록을 사용하여 그래프를 구현할 수 있습니다. 여기서는 인접 목록을 사용하여 JavaScript로 그래프를 구현해 보겠습니다.

차트 클래스 만들기

여기서 그래픽 클래스의 청사진을 만듭니다.

정점 추가

이 함수는 adjacencyList 객체에 새 키를 생성하고 빈 배열을 값으로 제공하여 그래프에 새 정점(또는 노드)을 추가합니다. 새 정점은 키 역할을 하며 빈 배열은 이웃을 저장하는 데 사용됩니다.

가장자리 추가

이 기능은 두 정점 사이에 새로운 가장자리를 추가합니다. vertex1과 vertex2라는 두 개의 매개변수를 허용하고 vertex2를 vertex1의 이웃 배열에 추가하거나 그 반대로 추가합니다. 이렇게 하면 두 정점 사이에 연결이 생성됩니다.

차트 인쇄

이 기능은 차트를 콘솔에 기록합니다. adjacencyList 객체의 각 꼭지점을 반복하고 꼭지점과 그 이웃을 기록합니다.

예

아래 예에서는 그래프를 정의하고 그래프에 정점과 모서리를 추가합니다. 마지막으로 차트를 인쇄합니다.

출력

가장자리 삭제

이 기능은 두 정점 사이의 가장자리를 삭제합니다. vertex1과 vertex2라는 두 개의 인수를 취하고 vertex1의 이웃 배열에서 vertex2를 필터링하며 그 반대의 경우도 마찬가지입니다.

정점 삭제

이 기능은 그래프에서 정점을 제거합니다. 정점 인수를 사용하고 먼저 해당 정점에 연결된 모든 가장자리를 제거합니다. 그런 다음 adjacencyList 개체에서 키를 제거합니다.

예

아래 예에서는 그래프를 정의하고 정점과 모서리를 추가한 다음 그래프를 인쇄합니다. 그래프에서 에지 AC를 제거하고 마지막으로 결과 그래프를 인쇄합니다.

출력

그래프 순회 방법

그래프 순회는 그래프의 모든 정점(또는 노드)을 방문하고 이와 관련된 정보를 처리하는 프로세스를 의미합니다. 그래프 순회는 그래프 알고리즘에서 중요한 작업으로 두 노드 사이의 최단 경로 찾기, 주기 감지, 연결된 구성 요소 찾기와 같은 작업에 사용됩니다.

그래프 순회에는 두 가지 주요 방법이 있습니다: 너비 우선 검색(BFS)과 깊이 우선 검색(DFS)

A. 너비 우선 검색(BFS)

breadthFirstSearch() 함수를 사용하여 구현됩니다. 이 함수는 너비 우선 검색 알고리즘을 구현하고 시작 정점인 시작 매개변수를 사용합니다. 큐를 사용하여 방문할 정점을 추적하고, 결과 배열을 사용하여 방문한 정점을 저장하며, 방문 개체를 사용하여 이미 방문한 정점을 추적합니다. 함수는 먼저 시작 정점을 대기열에 추가하고 이를 방문한 것으로 표시합니다. 그런 다음 대기열이 비어 있지 않으면 대기열에서 첫 번째 정점을 가져와 결과 배열에 추가하고 방문한 것으로 표시합니다. 그런 다음 방문하지 않은 모든 이웃을 대기열에 추가합니다. 이 프로세스는 모든 정점을 방문하고 결과 배열이 BFS의 결과로 반환될 때까지 계속됩니다.

비. 깊이 우선 검색

깊이 우선 탐색 방법은 정점을 매개변수로 사용하는 재귀 내부 함수 dfs를 사용하여 DFS 알고리즘을 구현합니다. 이 함수는 방문한 객체를 사용하여 방문한 정점을 추적하고 방문한 각 정점을 결과 배열에 추가합니다. 이 함수는 먼저 현재 정점을 방문한 것으로 표시하고 이를 결과 배열에 추가합니다. 그런 다음 현재 정점의 모든 이웃을 반복하고 방문하지 않은 각 이웃에 대해 dfs 함수를 재귀적으로 호출합니다. 이 프로세스는 모든 정점을 방문하고 결과 배열이 DFS의 결과로 반환될 때까지 계속됩니다.

예

아래 예에서는 BFS(Breadth First Search)와 DFS(Depth First Search)를 보여줍니다.

출력

결론

그래프는 개체 간의 관계와 연결을 나타내는 데 사용할 수 있는 유용한 데이터 구조입니다. JavaScript에서 그래프를 구현하는 것은 인접 목록이나 인접 행렬 사용을 포함한 다양한 기술을 사용하여 수행할 수 있습니다. 이 답변에서 설명하는 Graph 클래스는 인접 목록 표현을 사용합니다. 여기서 각 정점은 객체의 키로 저장되고 해당 가장자리는 배열의 해당 키 값으로 저장됩니다.

Graph 클래스는 그래프에 정점과 모서리를 추가하고, 그래프를 인쇄하고, 깊이 우선 검색 및 너비 우선 검색 순회를 수행하는 메서드를 구현합니다.

위 내용은 JavaScript로 그래프 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!