**進行中の作業**
私たちはすべての開発者として密接に精通しているが、それを知らないかもしれないデータ構造構造でこのシリーズをキックオフしたかったです:有向非循環グラフ。 「それは聞いたことがない。 お前は俺を知らない!”あなたは言うかもしれませんが、このグラフはバージョン管理を可能にするものです。 Gitは非循環グラフです。 この記事では、Dagに関する高いレベルの知識を少し与えてから、いくつかのコードを使用してDagを作成する方法を示します。DAGとは何ですか？
では、それはどういう意味ですか？ DAGは、ある方向に流れるグラフであり、要素はそれ自身の子にすることはできません。 だから私たちのほとんどは、LinkedLists、ツリー、さらにはグラフに精通しています。 DAGは最初の2つと非常によく似ており、3番目の実装です。p>
- ノード：データを格納する場所。
- 有向エッジ: 一つの方向を指す矢印（このデータ構造を異なるものにするもの）
- 親のないいくつかの偉大な先祖ノード。 （楽しい事実：いとこがある時点でお互いに結婚するので、ほとんどの祖先の木は実際にはDagであり、実際には木ではありません。Li>
- Leaves:子のないノード
一つを作ってみましょう
だから、いくつかのコードを書いてみましょう。 最初に、2つのプロパティを持つコンストラクターを作成し、それをDAGと呼びましょう。
function DAG() {
this.nodes = ;
this.vertices = {};
}
次に、addメソッドを追加します。 私がそこで何をしたか見て？p>
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;
};
これはどのように機能しますか？ 頂点オブジェクトは、すべての良いものが起こる場所です。 ノード、着信ノードのオブジェクト、およびそれらのすべての名前を持つ配列、それが何かと値を指すかどうかのブール値を追加します。 私たちは少し後にこれらのいくつかを取得します。
今、いくつかのエッジを追加し、ものがお互いに接続するようにしましょう。 それを行う前に、そのノードを訪問したかどうかをチェックするヘルパー関数を作成する必要があります。 それを訪問と呼びましょう。p>
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();
}
ここで何が起こるかは
それが本当に原因である信用を与えてみましょう
この記事を研究し、私は驚くほどスマートな人々によるいくつかの素晴らしい記事を読んで、情報のほとんどは彼らから来た。 私はDagとバージョン管理に関するこのよく書かれた投稿を読むことによって理論の大部分を学びました。 ここのコードは、emberjsのソースコードとその背後にある華麗な著者からインスピレーションを得ました。 私はまた、インターネットの周りの偉大な人々からのDAGsに関する多数の他の記事やブログ記事を読んだことがあります。 読んでくれてありがとう！