**작업이 진행 중**
나는 원하는 이 시리즈로 데이터 구조 구조는 우리 모두 개발이 익숙하지 않을 수 있습니다 심지어 그것을 알고:지시 비순환 그래프. “나는 들어 본 적이 없다. 너는 나를 모른다!”라고 말할 수도 있지만이 그래프는 버전 제어를 가능하게하는 것입니다. 힘내는 비순환 그래프입니다. 이 게시물에,나는 당신에게 줄 것이다 조금 높은 수준의 지식에 Dag 다음 방법 중 하나를 만드와 일부 코드입니다.
DAG 란 무엇입니까?
그래서 그게 무슨 뜻입니까? DAG 는 어떤 요소도 그 자체의 자식이 될 수없는 한 방향으로 흐르는 그래프입니다. 그래서 우리 대부분은 링크에 익숙합니다.목록,나무,심지어 그래프. DAG 는 처음 두 개와 매우 유사하며 세 번째 구현입니다.
최소한,DAG4 일:
- 노드는 위치 데이터를 저장합니다.
- 지시된 가장자리: 한 방향을 가리키는 화살표(이 데이터 구조를 다르게 만드는 것)
- 부모가없는 훌륭한 조상 노드. (재미있는 사실 대부분의 조상 나무는 실제로 Dag 및 실무기 때문에 사촌에서 어떤 시점이 결혼하다.)
- 잎:자식이없는 노드
하나를 만들자
그래서 몇 가지 코드를 작성합시다. 먼저 두 개의 속성을 가진 생성자를 만들고 DAG 라고 부르 자.
function DAG() {
this.nodes = ;
this.vertices = {};
}
다음으로 추가 방법을 추가 할 것입니다. 내가 거기에서 무엇을했는지 보시겠습니까?
DAG.prototype.add = function(node) {
if (!node) { return; }
if (this.vertices) {
return this.vertices;
}
const vertex = {
node: node,
incoming: {},
incomingNodes: ,
hasOutgoing: false,
value: null
};
this.vertices = vertex;
this.nodes.push(node);
return vertex;
};
그렇다면 어떻게 작동합니까? 정점 객체는 모든 좋은 물건이 일어나는 곳입니다. 우리는 노드를 추가,개체의 들어오는 노드와 배열에 모두 자신의 이름을,부울에 여부를 포인트 뭔가 값이 있습니다. 우리는 조금 후에 이들 중 일부에 도착할 것입니다.이제 가장자리를 추가하고 물건을 서로 연결하도록 할 수 있습니다. 그렇게하기 전에 해당 노드를 방문했는지 여부를 확인하는 도우미 함수를 만들어야합니다. 방문이라고 부르 자.
function visit(vertex, fn, visited, path) {
const name = vertex.name,
vertices = vertex.incoming,
names = vertex.incomingNames,
len = names.length,
i;
if (!visited) {
visited = {};
}
if (!path) {
path = ;
}
if (visited.hasOwnProperty(name)) {
return;
}
path.push(name);
visited = true;
for (i = 0; i < len; i++) {
visit(vertices], fn, visited, path);
}
fn(vertex, path);
path.pop();
}
어떻게 여기
신용을 제공 할 수 있 그것이 정말로 인해
이 기사를 연구하고,제가 읽을 몇 가지 훌륭한 게시물에 의해 놀라 울 정도로 똑똑한 사람과 정보의 대부분에서 나온다. 나는 DAGs 와 버전 제어에 대한이 잘 쓰여진 게시물을 읽음으로써 이론의 대부분을 배웠다. 여기에있는 코드는 emberjs 소스 코드와 그 뒤에있는 화려한 저자로부터 모든 영감을 얻었습니다. 나는 또한 인터넷 주변의 위대한 사람들의 Dag 에 관한 수많은 다른 기사와 블로그 게시물을 읽었습니다. 읽어 주셔서 감사합니다!