首页 > 代码库 > 深度优先搜索
深度优先搜索
//深度优先搜索 从一条路径的起始顶点开始追溯到达最后一个顶点，然后回溯继续追溯下一条路径，直到最后一个顶点，如此N次，直到没有路径为止。
//创建图
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.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
}
function addEdge(v,w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
function showGraph(){//打印所有顶点及其相邻顶点列表
for(var i=0;i<this.vertices;i++){
console.log(‘顶点‘+i+‘->‘);
for(var j=0;j<this.vertices;j++){
if(this.adj[i][j]){
console.log(this.adj[i][j]+‘ ‘);
}
}
}
}
function dfs(s) {
var queue=[];this.edgeTo=[];
this.marked[s] = true;
queue.push(s)
while(queue.length>0){
var v=queue.shift();
console.log(‘vs:‘+v);
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.edgeTo[w]=v;
this.marked[w]=true;
queue.push(w)
}
}
}
}
g = new Graph(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,3);
g.addEdge(2,4);
g.showGraph();
g.dfs(0);
//0 1 2 3 4
深度优先搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。