JavaScript의 데이터 구조:깊이 우선 검색 맵이 있는 토폴로지 정렬

당신의 직업 생활의 어느 순간(오늘?!)너는 데이터 구조를 배우고 싶을 것이다.기술 면접에서 우수한 성적을 거두고 이상적인 직업을 얻기 위해서만은 아니다.데이터 구조를 배우는 것은 소프트웨어가 어떻게 작동하는지 이해하고 문제를 해결하는 능력을 향상시키는 데 도움이 될 것이다.이 자습서에서는 JavaScript에서 Topology Search 그림을 사용하여 Topology 순서를 지정하는 방법을 학습합니다.
본문은 최초로 jarednielsen.com에 발표되었다
만약 네가 방금 우리에 가입했다면, 너는 아마 Learn JavaScript Graph Data Structure부터 시작하고 싶을 것이다.

검색 실천

검색 연습은 모든 새로운 지식을 공고히 하는 가장 믿을 만한 방법이다.계속하기 전에 다음 질문에 대답해 보십시오.

그래픽이란 무엇입니까?

다이어그램은 어떤 문제를 해결합니까?

깊이 우선 검색이란 무엇입니까?

무엇이 도형입니까?

그림은 모서리로 연결된 노드나 정점으로 구성되어 있다.모서리는 교점 쌍으로 구성됩니다.예를 들어 만약에 우리가 두 정점 A과 B 사이에 한 쌍을 이루면 우리는 이 관련 짝을 변이라고 부른다.그것들은 가장자리를 통해 연결되어 있기 때문에 A과 B은 서로 인접해 있다.

도표는 어떤 문제를 해결할 수 있습니까?

최적화: GPS

과 같이 그래픽 데이터 구조를 최적화 알고리즘과 결합하여 최적의 경로를 정할 수 있습니다.

네트워크 토폴로지: 우리는 네트워크 토폴로지를 모델링할 때 도형 데이터 구조를 사용할 수 있다. 예를 들어 인터넷이나 페이스북의 친구!

깊이 우선 검색이란 무엇입니까?

Depth First Search(Depth First Search)는 경로에 연결된 모든 정점을 확인한 다음 인접한 정점을 계속 확인하여 도면에서 특정 대상을 검색하는 알고리즘입니다.

우리 메타 찾아가자.

토폴로지란?

유방향 무환도는 무엇입니까?

토폴로지 순서란?

토폴로지학은 무엇입니까?

위키백과에 의하면...

In mathematics, topology is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling and bending, but not tearing or gluing.

🙄
데이터 구조의 측면에서 이 문제를 고려합시다.우리의 기하학적 물체는 무엇입니까?우리 그래프!우리는 통상적으로 도형이 2차원이라고 생각하지만, 그것들은 3차원으로 표시하기 쉽다.무엇이 연속 변형입니까?정점과 모서리를 추가하고 삭제하는 방법.

무엇이 유방향 무환도입니까?

Wikipedia에 따르면 유방향 무환도는 하나의...

consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop

이 용어에 대해 역방향 공사를 진행합시다.
우리는 도형이라는 용어에 익숙하다.그러나 비순환은 무엇을 의미하는가?순환은 무엇입니까?

a series of events that are regularly repeated in the same order.

따라서 만약에 어떤 일이 주기적이라면 그것은 바로'주기적으로 발생하고 규칙적으로 중복된다'는 것이다.만약 어떤 일이 비순환적이라면, 그것과 반대로, 이것은 그것이 순환 중에 발생하지 않는다는 것을 의미한다.
만약 그림이 방향이 있다면, 이것은 무엇을 의미합니까?그림이 있는 변은 한 정점에서 다른 정점까지의 방향을 가리킨다.

토폴로지 정렬은 무엇입니까?

토폴로지 정렬을 설명할 수 있는 유행하는 유형이 많은데, 예를 들어 특정한 순서에 따라 실행해야 하는 작업이나 기술 목록과 그 선결 조건을 설명할 수 있다.
내가 가장 좋아하는 유형은 Corment 등이 Introduction to Algorithms에서 사용하는 유형인데 그 중에서 범스팀 교수가 작업복을 입고 있다.목욕 후, 브룸스터드 교수는 옷장을 열고 다음과 같은 옷을 골랐다.

짧은

긴바지
벨트
양말
신발
셔츠
넥타이

도관틀

만약 범스팀 교수의 옷장이 하나의 도형이고 옷이 정점이라면 우리는 교수가 반드시 일정한 순서나 방향에 따라 옷을 입어야 한다는 것을 볼 수 있다.물론 그가 정신을 딴 데 팔고 있는 교수가 아니라면.

JavaScript에서 DFS(딥 우선 순위 검색)를 사용하여 토폴로지 정렬

그래프 클래스를 살펴보겠습니다.

class Graph {
    constructor() {
        this.vertices = [];
        this.adjacent = {};
        this.edges = 0;
    }

    addVertex(v) {
        this.vertices.push(v);
        this.adjacent[v] = [];
    }

    addEdge(v, w) {
        this.adjacent[v].push(w);
        this.adjacent[w].push(v);
        this.edges++;
    }


    bfs(goal, root = this.vertices[0]) {
        let adj = this.adjacent;

        const queue = [];
        queue.push(root);

        const discovered = [];
        discovered[root] = true;

        const edges = [];
        edges[root] = 0;

        const predecessors = [];
        predecessors[root] = null;

        const buildPath = (goal, root, predecessors) => {
            const stack = [];
            stack.push(goal);

            let u = predecessors[goal];

            while(u != root) {
                stack.push(u);
                u = predecessors[u];
            }

            stack.push(root);

            let path = stack.reverse().join('-');

            return path;
        }


        while(queue.length) {
            let v = queue.shift();

            if (v === goal) {
                return { 
                    distance: edges[goal],
                    path: buildPath(goal, root, predecessors)
                };
            }

            for (let i = 0; i < adj[v].length; i++) {
                if (!discovered[adj[v][i]]) {
                    discovered[adj[v][i]] = true;
                    queue.push(adj[v][i]);
                    edges[adj[v][i]] = edges[v] + 1;
                    predecessors[adj[v][i]] = v;
                }
            }
        }

        return false;
    }

    dfs(goal, v = this.vertices[0], discovered = []) {
        let adj = this.adjacent;

        discovered[v] = true;

        for (let i = 0; i < adj[v].length; i++){
            let w = adj[v][i];

            if (!discovered[w]) {
                this.dfs(goal, w, discovered);
            }
        }

        return discovered[goal] || false;
    }
}

다음은 새로운 도형을 초기화하고 정점과 변을 추가합니다.

const g = new Graph();

g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addVertex("G");

g.addEdge("A","B");
g.addEdge("A","C");
g.addEdge("A","D");
g.addEdge("B","C");
g.addEdge("B","D");
g.addEdge("C","D");
g.addEdge("C","E");
g.addEdge("D","F");
g.addEdge("F","G");

토폴로지 정렬의 목표를 다시 한번 말씀드리겠습니다.

Given a directed acylcic graph, select a vertex with an indegree of zero and return all vertices in the order discovered on each path of the graph.

우리가 말한 "indegree"는 무슨 뜻입니까?Indegree와 그 대립면 outdegree는 모서리가 정점을 가리키거나 오는지 설명합니다.여기서 독립도가 0인 정점은 그 정점을 가리키지 않았다는 것을 의미한다.위의 그림에서 정점 "A"의 indegree는 0이지만 그 가장자리는 정점 "B", "C"과 "D"을 가리킬 때의outdegree는 3이다.

다음을 반환하는 방법을 작성하려고 합니다.

[
  'A', 'B',
  'C', 'E',
  'D', 'F',
  'G'
]

📝 "E"는 "C"다음에 "D"앞에 있습니다.
왜?
만약 우리가 DFS 방법의 제어 절차를 따른다면 우리는'A'에서 시작하여'B'를 발견하고'A'로 거슬러 올라간 다음에'C'와'E'를 발견한 다음에 다시'A'로 거슬러 올라가'D','F'를 발견하고 마지막에'G'를 발견한다.
방금 설명한 DFS를 위조 코드로 변환합니다.

은 도형, 목표와 시작 정점을 정한다...

표시가 발견한 시작 정점.

은 인접한 각 교점에 대해 이 교점이 발견되지 않으면 인접한 교점을 이미 발견된 것으로 표시합니다.

은 각 인접 정점에 사용됩니다...반복

에서 발견된 정점을 되돌려줍니다.

만약 우리의 목표가 정점을 발견한 순서에 따라 정점으로 돌아가는 것이라면 어떻게 위조 코드를 수정합니까?
우리는 이전에 어디에서 이것이나 유사한 물건을 본 적이 있습니까?
🤔
광도 우선 검색!
BFS 의 "비법"은 무엇입니까?
줄을 서다.
왜?
우리는 정점 사이를 이동하기 때문이다.
DFS에서 큐가 유효합니까?
🙅‍♀️
왜?
우리가 정점을 위아래로 이동하기 때문이다.
그렇다면 어떤 데이터 구조가 작용할까요?
한 무더기.
위조 코드에 새 단계를 삽입합니다.

은 도형, 목표와 시작 정점을 정한다...

은 스택을 선언합니다.

표시가 발견한 시작 정점.

은 인접한 각 교점에 대해 이 교점이 발견되지 않으면 인접한 교점을 이미 발견된 것으로 표시합니다.

은 각 인접 정점에 사용됩니다...반복

은 정점을 스택으로 밀어 넣습니다.

스택으로 돌아갑니다.

이제 위조 코드를 자바스크립트로 번역해 봅시다.우리는 처음부터 topoSort 방법을 작성할 수 있지만, dfs과 매우 비슷하기 때문에 그것을 복제하고 재구성할 것이다.다음은 Dell의 dfs 방법입니다.

    dfs(goal, v = this.vertices[0], discovered = []) {
        let adj = this.adjacent;

        discovered[v] = true;

        for (let i = 0; i < adj[v].length; i++){
            let w = adj[v][i];

            if (!discovered[w]) {
                this.dfs(goal, w, discovered);
            }
        }

        return discovered[goal] || false;
    }

우리는 단지 약간의 조정만 할 수 있다.

    topoSort(v = this.vertices[0], discovered = [], s) {
        const stack = s || [];

        let adj = this.adjacent;

        discovered[v] = true;

        for (let i = 0; i < adj[v].length; i++){
            let w = adj[v][i];

            if (!discovered[w]) {
                this.topoSort(w, discovered, stack);
            }
        }

        stack.unshift(v);
        return stack || false;
    }

우리는 goal 파라미터를 삭제했다. 왜냐하면 우리는 특정한 정점을 검색하지 않았기 때문이다. 우리는 s 파라미터를 추가했다. 그러면 우리는 stack 수조에서memonization을 사용할 수 있다.그리고 우리는 stack에 저장된 값을 분배하여 s을 설명하거나 새로운 빈 그룹을 초기화합니다.stack으로 돌아가기 전에, 우리는 정점을 수조에 미리 추가할 것이다.
너는 그것을 뛰어넘을 수 있니?
그래, 사실 너는 할 수 있어.토폴로지 정렬 알고리즘을 실현할 수 있는 몇 가지 방법이 있다.Introduction to Algorithms에서 개술한 방법은 창고가 아닌 체인 시계를 사용하는데 이것은 매우 기이하다.또 다른 유행하는 방법은 해시 시계를 사용하는 것이다.배열을 선택하는 이유는 매우 간단하기 때문입니다. 또한 이러한 배열을 다루는 것을 기억할 때, 배열의 작업 원리는 스택과 유사하며, 자바스크립트에서 그것을 실현하는 것은 말할 것도 없습니다.또 일부 실현은 발견 정점에서'완성'까지의 시간을 계산할 수 있는데 이것은 모든 인접 정점이 탐지된다는 것을 의미한다.그런 다음 정렬된 토폴로지에서 정점의 위치를 결정하는 데 사용됩니다.

거꾸로 비친 그림자

토폴로지란?

유방향 무환도는 무엇입니까?

토폴로지 순서란?

토폴로지학은 무엇입니까?

우리의 의도와 목적에서 토폴로지학은 데이터 구조의 형상을 연구하는 것이고 본 예에서는 도형이다.우리는 그림의 성질, 변과 정점, 그리고 그것들 사이의 관계에 대해 특히 흥미를 느낀다.

무엇이 유방향 무환도입니까?

DAG는 하나 이상의 색인이 0인 정점을 포함하는 그림으로, 정점 순서를 지정하는 모서리로 구성되어 있으며, 모서리(u, v)는 정점 u가 v 앞에 있음을 의미합니다.

토폴로지 정렬은 무엇입니까?

토폴로지 정렬은 그림 스트리밍 알고리즘으로 가장자리가 정의한 순서에 따라 무환도의 정점을 되돌려줍니다.
계속 참여하고 싶으세요?나는 매주 프로그래밍, 문제 해결, 평생 공부에 관한 시사 통신을 한 부 쓴다.
✉️ Sign up for The Solution