图的搜索算法javascript
目录
图的搜索算法javascript
搜索就是从一个指定的点开始找到其他节点。图的搜索基本上分为深度优先搜索和广度优先搜索。先来说说深度优先搜索。
深度优先搜索包括从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。如下图所示：
算法的思路就是访问一个没有访问过的点，将它标记为已访问，再递归去访问在初始顶点的邻接表中其他没有访问过的点。
代码如下：
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]);
}
}
}实验代码如下：
//实验
g=new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
g.dfs(1);实验结果为：
// 0-> 1 2
// 1-> 0 3
// 2-> 0 4
// 3-> 1
// 4-> 2
//
访问节点：
1
//
访问节点：
0
//
访问节点：
2
//
访问节点：
4
//
访问节点：
3
深度优先搜索的时间复杂度为O(n+e)
再来说说广度优先搜索，就是从第一个顶点开始，尝试访问尽可能靠近它的顶点。先把同层的搜索完再逐渐向下搜索。过程如下图：
算法的思想如下：
首先找到与当前顶点相邻的未访问顶点，将其添加到已访问顶点列表及队列中；
从图中取出下一个顶点v，添加到已访问的顶点列表中；
将所有和v相邻的未访问顶点添加到队列。
代码如下：
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.marked[w[j]]=true;//依次访问其相邻子列表
queue.push(w[j]);//将子列表推送入队列
}
}
}
}
}实验代码如下：
//实验
g=new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
g.dfs(1);
g.bfs(1);
//结果
// 0-> 1 2
// 1-> 0 3
// 2-> 0 4
// 3-> 1
// 4-> 2
// 访问节点：1
// 访问节点：0
// 访问节点：2
// 访问节点：4
// 访问节点：3
// 访问节点：1
// 访问节点：0
// 访问节点：3
// 访问节点：2
// 访问节点：4广度优先搜索的时间复杂度和深度优先搜索一样，都是O(n+e)，两者不同之处仅仅在于对顶点访问的顺序不同。
图的表示和搜索的完整代码如下：
<!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=[];//数组存放顶点数量
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>");
}
}
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.marked[w[j]]=true;//依次访问其相邻子列表
queue.push(w[j]);//将子列表推送入队列
}
}
}
}
}
//实验
g=new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
g.dfs(1);
g.bfs(1);
//结果
// 0-> 1 2
// 1-> 0 3
// 2-> 0 4
// 3-> 1
// 4-> 2
// 访问节点：1
// 访问节点：0
// 访问节点：2
// 访问节点：4
// 访问节点：3
// 访问节点：1
// 访问节点：0
// 访问节点：3
// 访问节点：2
// 访问节点：4
</script>
</body>
</html>