図の表示javascript
1506 ワード
一見、図は木や二叉の木に似ていますが、対象に基づいて構築すると問題があります.図が非常に大きくなる可能性がありますので、対象で示すと効率が低下します.
まず、隣接テーブル、すなわちノードに関連するノード配列をadj配列で表す図のクラスを定義する必要がある.marked配列は、ノードがアクセスされたかどうかを示すために用いられ、深さ優先検索および広さ優先検索に用いられる.
//結果
// 0->1
// 1->0
// 2->0 4
// 3->1
//4->2
一つの図が表示されます.次のセクションでは、広さ優先と深さ優先検索の実現について説明します.
まず、隣接テーブル、すなわちノードに関連するノード配列をadj配列で表す図のクラスを定義する必要がある.marked配列は、ノードがアクセスされたかどうかを示すために用いられ、深さ優先検索および広さ優先検索に用いられる.
function Graph(v){//
this.vertices=v;//
this.edges=0;//
this.adj=[];//
for(var i=0;i<this.vertices;i++){
this.adj[i]=[];//
}
this.addEdge=addEdge;//
this.showGraph=showGraph;//
this.dfs=dfs;//
this.bfs=bfs;//
this.marked=[];//
for(var i=0;i<this.vertices;i++){//
this.marked[i]=false;
}
}
次に、関数を定義して二国間関係を追加する必要があります.コードは以下の通りです. function addEdge(v,w){//
this.adj[v].push(w);// w v
this.adj[w].push(v);// v w
this.edges++;//
}
次に、図関係を示す関数を定義します.コードは以下の通りです.function showGraph(){//
for(var i=0;i<this.vertices;i++){
document.write(i+"->");
for(var j=0;j<this.vertices;j++){
if(this.adj[i][j]!=undefined){//
document.write(this.adj[i][j]+" ");
}
}
document.write("<br>");
}
}
テストに来てもいいです.g=new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
実験結果は://結果
// 0->1
// 1->0
// 2->0 4
// 3->1
//4->2
一つの図が表示されます.次のセクションでは、広さ優先と深さ優先検索の実現について説明します.