図の表示javascript

1506 ワード

一見、図は木や二叉の木に似ていますが、対象に基づいて構築すると問題があります.図が非常に大きくなる可能性がありますので、対象で示すと効率が低下します.
         まず、隣接テーブル、すなわちノードに関連するノード配列を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
一つの図が表示されます.次のセクションでは、広さ優先と深さ優先検索の実現について説明します.