图和图算法

发表于   |   分类于

深度优先搜索、广度优先搜索与最短路径

一、概念

1、图的常用存储方式有两种，邻接表和邻接矩阵。邻接表将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否有一条边。
2、深度优先搜索：从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径位置。
3、广度优先搜索：从第一个顶点开始，尝试访问尽可能靠近它的顶点。这种搜索在图上逐层移动，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层。

二、算法分析

1、深度优先搜索
访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

2、广度优先搜索
从第一个顶点开始，查找与这个顶点相邻的未访问节点，将它标记为已访问，并加入队列中；
第一个元素出队列，并查找这个顶点相邻的未访问节点，将它标记为已访问，并加入队列中

3、最短路径
广度优先搜索时，记录从一个顶点到另一个相连顶点的最短路径，this.edgeTo[this.adj[v][w]] = v;。
查找初始节点到最终节点的最短路径时，通过最终节点找到能访问这个最终节点的上一个节点，通过上一个节点继续找能访问这个节点的上上个节点，如此往复，直到上一个节点是初始节点为止。

三、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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;
    }
    this.edgeTo = [];
    this.pathTo = pathTo;
    this.hasPathTo = hasPathTo;
}
//添加一条边
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] != undefined){
                console.log(this.adj[i][j] + ' ');
            }
        }
    }
}
//深度优先搜索
function dfs(v){
    this.marked[v] = true;
    if(this.adj[v] !== undefined){
        console.log("Visited vertex: " + v);
    }
    for(var w in this.adj[v]){
        if(!this.marked[this.adj[v][w]]){
            this.dfs(this.adj[v][w]);
        }
    }
}
//广度优先搜索
function bfs(s){
    var queue = [];
    this.marked[s] = true;
    queue.push(s);
    while(queue.length > 0){
        var v = queue.shift();
        if(v !== undefined){
            console.log("Visited vertex: " + v);
        }
        for(var w in this.adj[v]){
            if(!this.marked[this.adj[v][w]]){
                this.edgeTo[this.adj[v][w]] = v;
                this.marked[this.adj[v][w]] = true;
                queue.push(this.adj[v][w]);
            }
        }
    }
}
//基于广度优先搜索，到某个点的最短路径，边没有权值
function pathTo(v){
    var source = 0;
    if(!this.hasPathTo(v)){
        return undefined;
    }
    var path = [];
    for(var i=v; i!=source; i=this.edgeTo[i]){
        path.push(i);
    }
    path.push(source);
    return path;
}
function hasPathTo(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.showGraph();
// g.dfs(0);
g.bfs(0);
var vertex = 2;
var paths = g.pathTo(vertex);
while(paths.length > 0){
    if(paths.length > 1){
        console.log(paths.pop() + '-');
    }else{
        console.log(paths.pop());
    }
}