다이어그램의 정의
그래프는 유한 비어 있지 않은 정점 세트와 정점 사이의 가장자리 세트로 구성됩니다. 일반적으로 다음과 같이 표시됩니다. G (v, e), 여기서 g는 그래프를 나타내고, v는 그래프 G의 정점 세트이고, E는 그래프 G의 가장자리 세트입니다.
지시 된 그래프
지시 된 가장자리 : 정점 VI에서 VJ로의 가장자리에 방향이있는 경우,이 가장자리는 방향 가장자리라고하며 아크 (아크)가됩니다. 주문 <vi, vj>로 표시됩니다. VI는 Arc Tail이라고하며 VJ를 Arc 헤드라고합니다.
무질서한 다이어그램
변환되지 않은 가장자리 : 정점 VI에서 VJ 사이의 모서리가 방향이 없으면이 가장자리를 방향 가장자리 (가장자리)라고하며, 정렬되지 않은 쌍 (VI, VJ)으로 표시됩니다.
간단한 그림
간단한 다이어그램 : 그래프 구조에서 자체 가장자리에 정점이없고 동일한 모서리가 반복적으로 나타나지 않으면이 그림을 간단한 다이어그램이라고합니다.
사진 수업
정점을 나타냅니다
그래프 클래스를 만드는 첫 번째 단계는 정점과 가장자리를 저장하기 위해 정점 클래스를 만드는 것입니다. 이 클래스는 링크 된 목록의 노드 클래스 및 이진 검색 트리와 동일합니다. 정점 클래스에는 두 개의 데이터 구성원이 있습니다. 하나는 정점을 식별하고 다른 하나는 액세스되었는지 여부를 나타냅니다. 그들은 라벨이 지정되어 있으며 각각 방문되었습니다.
코드 사본은 다음과 같습니다.
함수 vertex (레이블) {
this.label = 레이블;
}
우리는 모든 정점을 배열에 저장하고 그래프 클래스에서 배열에서 그들의 위치를 참조 할 수 있습니다.
가장자리를 나타냅니다
그래프의 실제 정보는 그래프의 구조를 설명하기 때문에 "가장자리"에 저장됩니다. 이진 트리의 부모 노드에는 두 개의 자식 노드 만 가질 수 있지만 그래프의 구조는 훨씬 유연합니다. 정점은 하나의 모서리 또는 여러 모서리에 연결될 수 있습니다.
그래프의 가장자리를 나타내는 방법을 사용하여 인접 테이블 또는 인접 테이블 배열이됩니다. 인접한 정점 정점 목록으로 구성된 배열을 저장합니다.
그래프를 작성하십시오
다음 그래프 클래스를 정의하십시오.
코드 사본은 다음과 같습니다.
기능 그래프 (v) {
this.vertices = v; // 하이 포인트의 정점
this.edges = 0;
this.adj = [];
for (var i = 0; i <this.vertices; ++ 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라고도하는 DepthFirstSearch는 짧은 DFS라고합니다.
예를 들어, 방에서 열쇠를 찾으려면 어느 방을 시작하든 방 모서리, 밤 스탠드, 침대 옆 테이블, 침대, 옷장, TV 캐비닛 등을 검색 할 수 있습니다. 모든 서랍과 저장 캐비닛을 검색 한 후 다음 방을 검색합니다.
깊이 우선 순위 검색 :
깊이 최초의 검색은 방문되지 않은 정점에 액세스하여 액세스 한 것으로 표시 한 다음 초기 정점의 인접 테이블에서 방문하지 않은 다른 정점에 재귀 적으로 액세스하는 것을 의미합니다.
그래프 클래스에 배열 추가 :
코드 사본은 다음과 같습니다.
this.marked = []; // 방문한 정점을 저장합니다
for (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // false로 초기화합니다
}
깊이 우선 검색 기능 :
코드 사본은 다음과 같습니다.
함수 dfs (v) {
this.marked [v] = true;
// 여기에서 문이 필요하지 않은 경우
if (this.adj [v]! = 정의되지 않은) {
print ( "방문 vertex :" + v);
각각 (var w this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
폭 넓은 첫 번째 검색
BFS (Broadness-First Search)는 맹인 검색 방법이며, 그래프의 모든 노드를 체계적으로 확장하고 검사하여 결과를 찾을 수 있습니다. 다시 말해, 결과의 가능한 위치를 고려하지 않으며 결과가 발견 될 때까지 전체 그림을 철저히 검색합니다.
폭이 첫 번째 검색에서 첫 번째 정점에서 시작하여 다음 그림과 같이 가능한 한 가까운 정점에 액세스하려고합니다.
그 원칙은 다음과 같습니다.
1. 먼저 현재 정점에 인접한 미공개 정점을 찾아 방문한 정점 목록 및 대기열에 추가하십시오.
2. 그런 다음 그래프에서 다음 정점 V를 꺼내서 방문한 Vertice 목록에 추가하십시오.
3. 마지막으로 V에 인접한 모든 방문되지 않은 정점을 대기열에 추가합니다.
다음은 광선 검색 기능의 정의입니다.
코드 사본은 다음과 같습니다.
함수 bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // 큐 끝에 추가하십시오
while (queue.length> 0) {
var v = queue.shift (); // 팀 리더에서 제거됩니다
if (v == 정의되지 않은) {
print ( "방문 vertex :" + v);
}
각각 (var w this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
가장 짧은 경로
폭이 넓은 검색을 수행 할 때 한 정점에서 다른 연결된 정점까지의 가장 짧은 경로가 자동으로 발견됩니다.
경로를 결정하십시오
가장 짧은 경로를 찾으려면 한 정점에서 다른 정점으로 경로를 기록하려면 폭이 먼저 검색 알고리즘을 수정해야합니다. 한 정점에서 다음 정점의 모든 모서리를 저장하려면 배열이 필요합니다. 우리는이 배열 Edgeto의 이름을 지정합니다
코드 사본은 다음과 같습니다.
this.edgeto = []; //이 줄을 그래프 클래스에 추가합니다
// bfs 함수
함수 bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // 큐 끝에 추가하십시오
while (queue.length> 0) {
var v = queue.shift (); // 팀 리더에서 제거됩니다
if (v == 정의되지 않은) {
print ( "방문 vertex :" + v);
}
각각 (var w this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
토폴로지 분류 알고리즘
토폴로지 분류는 지시 된 그래프의 모든 정점을 정렬하여 전방 정점에서 뒷면 정점까지 지시 된 가장자리가 가리 킵니다.
토폴로지 분류 알고리즘은 BFS와 유사합니다. 차이점은 토폴로지 분류 알고리즘이 액세스 된 정점을 즉시 출력하지 않고 대신 현재 정점 인접 테이블의 인접한 정점에 액세스한다는 것입니다. 이 목록이 소진 될 때까지 현재 정점은 스택으로 밀리지 않습니다.
토폴로지 분류 알고리즘은 두 가지 함수로 나뉩니다. 첫 번째 함수는 TOPSORT ()이며, 분류 프로세스를 설정하고 도우미 기능 topsorthelper ()를 호출 한 다음 정렬 된 정점 목록을 표시하는 데 사용됩니다.
토폴로지 분류 알고리즘의 주요 작업은 재귀 함수 topsorthelper ()에서 수행되며, 이는 현재 정점을 액세스 한 것으로 표시 한 다음 현재 정점 인접 테이블에서 각 정점에 다시 액세스하여 이러한 정점에 액세스 한 것으로 표시합니다. 마지막으로 현재 정점을 스택으로 밀어 넣으십시오.
코드 사본은 다음과 같습니다.
// topsort () 함수
함수 topsort () {
var 스택 = [];
var 방문 = [];
for (var i = 0; i <this.vertices; i ++) {
방문 [i] = 거짓;
}
for (var i = 0; i <this.vertices; i ++) {
if (방문한 [i] == 거짓) {
this.topsorthelper (i, 방문, 스택);
}
}
for (var i = 0; i <stack.length; i ++) {
if (stack [i]! = undefined && stack [i]! = false) {
print (this.vertexlist [stack [i]]);
}
}
}
// topSorthelper () 함수
기능 topsorthelper (v, 방문, 스택) {
방문 [V] = 참;
각각 (var w this.adj [v]) {
if (! 방문 [w]) {
this.topsorthelper (방문, 방문, 스택);
}
}
stack.push (v);
}