JavaScript 데이터 구조 및 알고리즘 그래프 및 그래프 알고리즘_기본 지식

그래프의 정의

그래프는 비어 있지 않은 유한 정점 집합과 정점 사이의 간선 집합으로 구성됩니다. 일반적으로 G(V,E)로 표현됩니다. 여기서 G는 그래프를 나타내고 V는 그래프 G의 정점입니다. 집합, E는 그래프 G의 간선 집합입니다.

유향 그래프

방향성 가장자리: 꼭지점 Vi에서 Vj까지의 가장자리에 방향이 있으면 이 가장자리를 방향성 가장자리라고 하며 호(Arc)라고도 하며 순서쌍 로 표시되며 Vi를 호출합니다. 는 호꼬리(arc tail)이고, Vj는 호두(arc head)라고 불린다.

순서가 지정되지 않은 그래프

무방향 에지: 정점 Vi와 Vj 사이의 에지에 방향이 없는 경우, 이 에지를 무방향 에지(Edge)라고 하며 순서가 없는 쌍(Vi, Vj)으로 표현됩니다.

간단한 그림

간단한 그래프: 그래프 구조에서 꼭지점과 정점 사이에 간선이 없고 동일한 간선이 반복적으로 나타나지 않는 경우 이러한 그래프를 단순 그래프라고 합니다.

그래픽

은 정점

을 나타냅니다.

그래프 클래스 생성의 첫 번째 단계는 정점과 모서리를 저장하는 Vertex 클래스를 생성하는 것입니다. 이 클래스의 기능은 연결리스트, 이진검색트리의 Node 클래스와 동일하다. Vertex 클래스에는 두 개의 데이터 멤버가 있습니다. 하나는 정점을 식별하고 다른 하나는 방문했는지 여부를 나타내는 부울 값입니다. 각각 label 및 wasVisited라는 이름이 지정됩니다.

코드 복사 코드는 다음과 같습니다.

함수 정점(레이블){
This.label = 라벨;
}

모든 정점을 배열에 저장하고 그래프 클래스에서 배열의 위치로 참조할 수 있습니다

은 가장자리를 나타냅니다

그래프의 실제 정보는 그래프의 구조를 설명하기 때문에 "가장자리"에 저장됩니다. 이진 트리의 상위 노드에는 두 개의 하위 노드만 있을 수 있지만 그래프의 구조는 훨씬 더 유연합니다. 정점에는 하나의 가장자리 또는 여러 개의 가장자리가 연결될 수 있습니다.

그래프의 모서리를 표현하는 방법을 인접 리스트(Adjacency List) 또는 인접 리스트 배열(Adjacency List Array)이라고 부릅니다. 정점의 인접한 정점 목록으로 구성된 배열을 저장합니다

구성도

다음과 같이 Graph 클래스를 정의합니다.

코드 복사 코드는 다음과 같습니다.

함수 그래프(v){
This.vertices = v;//정점 최고점
This.edges = 0;
This.adj = [];
for(var i =0;I This.adj[i] = [];
This.adj[i].push('');
}
This.addEdge = addEdge;
This.toString = toString;
}

그래프가 얼마나 많은 변을 나타내는지 기록하고, 그래프의 길이와 꼭지점 개수를 이용하여 꼭지점 개수를 기록하는 클래스입니다.

코드 복사 코드는 다음과 같습니다.

함수 addEdge(){
This.adj[v].push(w);
This.adj[w].push(v);
This.edges ;
}

여기에서는 for 루프를 사용하여 배열의 각 요소에 하위 배열을 추가하여 모든 인접 정점을 저장하고 모든 요소를 ​​빈 문자열로 초기화합니다.

그래프 순회

깊이 우선 순회

DepthFirstSearch는 깊이 우선 검색이라고도 하며 DFS라고도 합니다.

예를 들어 방에서 열쇠를 찾는 경우 방의 구석, 침대 옆 탁자, 침대, 침대 밑, 옷장, TV 캐비닛 등을 하나씩 검색할 수 있습니다. , 하나도 놓치지 않도록 모든 서랍과 수납장을 검색한 후 다음 방을 찾으세요.

깊이 우선 검색:

깊이 우선 탐색은 방문하지 않은 정점을 방문하여 방문했다고 표시한 후 초기 정점의 인접 목록에 있는 방문하지 않은 다른 정점에 재귀적으로 접근하는 것입니다

Graph 클래스에 배열 추가:

코드 복사 코드는 다음과 같습니다.

this.marked = [];//방문한 정점 저장
for(var i=0;i This.marked[i] = false;//false로 초기화
}

깊이 우선 검색 기능:

코드 복사 코드는 다음과 같습니다.

함수 dfs(v){
This.marked[v] = true;
//여기에서는 if 문이 필요하지 않습니다
If(this.adj[v] != 정의되지 않음){
​​​​print("방문한 정점: " v );
각(this.adj[v]의 var w){
If(!this.marked[w]){
This.dfs(w);
            }
}
}
}

폭 우선 검색

BFS(Breadth-First Search)는 그래프의 모든 노드를 체계적으로 확장하고 조사하여 결과를 찾는 것을 목표로 하는 블라인드 검색 방법입니다. 즉, 결과의 가능한 위치를 고려하지 않고 결과를 찾을 때까지 전체 그래프를 철저하게 검색합니다.

폭 우선 검색은 아래와 같이 첫 번째 정점부터 시작하여 가능한 한 가까운 정점을 방문하려고 시도합니다.

작동 원리는 다음과 같습니다.

1. 먼저 현재 정점에 인접한 방문하지 않은 정점을 찾아 방문한 정점 목록 및 대기열에 추가합니다. 2. 그런 다음 그래프에서 다음 정점 v를 가져와 방문한 정점 목록에 추가합니다
3. 마지막으로 v에 인접한 모든 방문하지 않은 정점을 대기열에 추가합니다
너비 우선 탐색 기능의 정의는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

함수 bfs(들){
var 대기열 = [];
This.marked = true;
Queue.push(s);//대기열 끝에 추가
동안(queue.length>0){
          var v = queue.shift();//대기열 헤드에서 제거
If(v == 정의되지 않음){
                                    print("방문한 정점: " v);
}
각(this.adj[v]의 var w){
If(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
}
}
}

최단 경로

폭 우선 탐색을 수행하면 한 정점에서 연결된 다른 정점까지의 최단 경로가 자동으로 검색됩니다.

경로 결정

최단 경로를 찾으려면 한 정점에서 다른 정점으로의 경로를 기록하도록 너비 우선 검색 알고리즘을 수정해야 합니다. 우리는 이것을 한 정점에서 다음 정점으로의 모든 가장자리를 저장하는 배열이 필요합니다. 배열 edgeTo

코드 복사 코드는 다음과 같습니다.

this.edgeTo = [];//그래프 클래스에 이 줄을 추가하세요

//bfs 함수
함수 bfs(들){
var 대기열 = [];
This.marked = true;
Queue.push(s);//대기열 끝에 추가
동안(queue.length>0){
          var v = queue.shift();//대기열 헤드에서 제거
If(v == 정의되지 않음){
                                    print("방문한 정점: " v);
}
각(this.adj[v]의 var w){
If(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
}
}
}

위상 정렬 알고리즘

토폴로지 정렬은 방향성 간선이 이전 정점에서 이후 정점을 가리키도록 방향성 그래프의 모든 정점을 정렬합니다.
위상 정렬 알고리즘은 BFS와 유사하지만, 위상 정렬 알고리즘은 방문한 정점을 즉시 출력하지 않고, 대신 현재 정점의 인접 목록에 있는 모든 인접 정점을 방문합니다. 목록이 스택에서 소진되었습니다.

위상 정렬 알고리즘은 두 가지 함수로 나뉩니다. 첫 번째 함수는 정렬 프로세스를 설정하고 보조 함수 topSortHelper()를 호출한 다음 정렬된 정점 목록을 표시하는 데 사용되는 topSort()입니다.

토폴로지 정렬 알고리즘의 주요 작업은 재귀 함수 topSortHelper()에서 완료됩니다. 이 함수는 현재 정점을 방문한 것으로 표시한 다음 현재 정점 인접 목록의 각 정점에 재귀적으로 액세스하여 이러한 정점을 방문한 것으로 표시합니다. 마지막으로 현재 정점이 스택으로 푸시됩니다.

코드 복사 코드는 다음과 같습니다.

//topSort() 함수
함수 topSort(){
var 스택 = [];
방문한 var = [];
for(var i =0;i         방문함[i] = false;
}
for(var i = 0;i If(방문함[i] == false){
This.topSortHelper(i,visited,stack);
}
}
for(var i = 0;i If(스택[i] !=정의되지 않음 && 스택[i] != false){
                   print(this.vertexList[stack[i]]);
}
}
}

//topSortHelper() 함수
함수 topSortHelper(v,visited,stack){
방문함[v] = true;
각(this.adj[v]의 var w){
If(!방문[w]){
This.topSortHelper(방문[w],방문,스택);
}
}
​ stack.push(v);
}