可以参考这个代码
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script type="text/javascript">
// function Vertex(label){
// this.label=label;
// }
function Graph(v){//图类
this.vertices=v;//结点数
this.edges=0;//边数
this.adj=[];//数组存放顶点数量
this.edgeTo=[];//存放从一个顶点到下一个顶点的所有边
for(var i=0;i<this.vertices;i++){
this.adj[i]=[];//子数组存储相邻顶点
}
this.addEdge=addEdge;//添加边
this.showGraph=showGraph;//显示图
this.dfs=dfs;//深度优先搜索
this.bfs=bfs;//广度优先搜索
this.pathTo=pathTo;
this.hashPathTo=hashPathTo;
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>");
}
}
function dfs(v){//深度优先搜索
this.marked[v]=true;//将标识位设为已访问
if(this.adj[v]!=null){//如果有相邻节点
document.write('访问节点：'+v+'<br>');
}
var len=this.adj[v].length;
for(var i=0;i<len;i++){
var w=this.adj[v];//将所选节点对应路径一条条搜索下去
for(var j=0;j<w.length;j++)
if(!this.marked[w[j]]){//对应一个路径一次搜索到底
this.dfs(w[j]);
}
}
}
function bfs(s){//广度优先搜索
for(var i=0;i<this.vertices;i++){//由于先进行深度优先搜索，所以这里要将标识位重置
this.marked[i]=false;
}
var queue=[];
this.marked[s]=true;
queue.push(s);
while(queue.length>0){
var v=queue.shift();
if(v!=undefined){
document.write("访问节点："+v+'<br>');
}
for(var i=0;i<this.adj[v].length;i++){
var w=this.adj[v];//找到所选节点的相邻子列表
for(var j=0;j<w.length;j++){
if(!this.marked[w[j]]){
this.edgeTo[w[j]]=v;//将对应节点存入边数组
this.marked[w[j]]=true;//依次访问其相邻子列表
queue.push(w[j]);//将子列表推送入队列
}
}
}
}
}
function pathTo(v){//寻找最短路径
var source=0;
var path=[];
for(var i=v;i!=source;i=this.edgeTo[i]){//在相邻边数组中寻找
path.push(i);
}
path.push(source);//将起始节点加进最短路径数组
return path;
}
function hashPathTo(v){
return this.marked[v];
}
//实验
g=new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.bfs(0);
var vertex=4;
var paths=g.pathTo(vertex);
while(paths.length>0){//将路径循环找出
if(paths.length>1){
document.write(paths.pop()+"-");
}else{
document.write(paths.pop());
}
}
// 访问节点：0
// 访问节点：1
// 访问节点：2
// 访问节点：3
// 访问节点：4
// 0-2-4
</script>
</body>
</html>
网友回复
我知道答案，我要回答
私活外包
