1 表示方法
有许多种方式来表示图，这里我用邻接表来表示。
邻接表由图中每个顶点的相邻顶点列表组成。
图
vertices = []
vertices['A'] = ['B','E']
vertices['B'] = ['A','F','E']
vertices['C'] = ['F','D']
vertices['D'] = ['C','F']
vertices['E'] = ['A','B']
vertices['F'] = ['B','C','D']
代码实现
function Graph () {
let vertices = []
let adjList = new Map()
this.addVertex = function (v) {
vertices.push(v)
adjList.set(v,[])
}
this.addEdge = function(v,w){
adjList.get(v).push(w)
adjList.get(w).push(v)
}
this.toString = function(){
let s = ''
vertices.forEach(v=>{
s+= v + '->'
let neighbors = adjList.get(v)
neighbors.forEach(vv=>{
s+=vv+' '
})
s+='\n'
})
return s
}
// body...
}
var g=new Graph()
var myVertices = ['A','B','C','D','E','F','G','H','I']
myVertices.forEach(v=>{
g.addVertex(v)
})
g.addEdge('A','B')
g.addEdge('A','C')
g.addEdge('A','D')
g.addEdge('C','D')
g.addEdge('C','G')
g.addEdge('D','G')
g.addEdge('D','H')
g.addEdge('B','E')
g.addEdge('B','F')
g.addEdge('E','I')
2 搜索
图.PNG
声明:当要标注已经访问过的顶点，我们用三种颜色来反映他们的状态。
白色:表示该顶点还没有被访问
灰色: 表示该顶点被访问过，但并未被探索
黑色:表示该顶点被访问过且被完全探索过
2.1 广度优先 breadth first search
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。
代码
this.bfs = function(v,callback){
let color = initColor()
q = new Queue()
q.enqueue(v)
while(!q.isEmpty()){
let u = q.dequeue(),
neighbors= adjList.get(u)
color[u]='grey' // 第一次探索
/*
一:分析刚才开始顶点为A 邻接点为B C D
u= A
neighbors =[B,C,D]
1
color[B]='grey'
q=[B]
2
color[C]='grey'
q=[B,C]
3
color[D]='grey'
q=[B,C,D]
二:
u= B
neighbors =[A,C,E]
1
color[A]='grey'
q=[C,D,A]
2
color[C]='grey'
q=[C,D,A,C]
3
color[E]='grey'
q=[C,D,A,C,E]
分析到第二步的时候已经发现了两个问题
第一个问题，A已经出队了又加来，这样会无限循环
第二问题C虽然没有被探索过，但是在队列里面的存在两次所以
才有一个顶点至多被访问两次
增加判断条件if(color[w]==='white'){
}
*/
neighbors.forEach(w=>{
if(color[w]==='white'){
color[w]='grey'
q.enqueue(w)
}
})
color[u]='black'
if(callback){
callback(u)
}
}
}
2.1.2: 使用bsf寻找最短路径
this.BFS = function (v) {
let color = initColor()
let q = new Queue()
let d = []
let pred = []
q.enqueue(v)
vertices.forEach(vv => {
d[vv] = 0
pred[vv] = null
}
)
while (!q.isEmpty()) {
let u = q.dequeue()
let neighbors = adjList.get(u)
color[u] = 'grey'
neighbors.forEach(w => {
if(color[w] === 'white'){
color[w]= 'grey '
d[w] = d[u] + 1
pred[w] = u
q.enqueue(w)
}
})
color[u] = 'black'
}
return {
distances: d,
predecessor: pred
}
}
分析:以A点为例。
计算到各点到A的距离，那些不直接接触A的点的点，只能通过A的邻接点来接触A，一层层的接触到A点，所以反过来。那些A的邻接点假设为BCD,则计算了BCD到A的距离，将BCD加入队列，假设B的邻接点为EFG，EFG的前任指向B，从而算出的EFG到A的距离就是最短的距离。
2.2 深度优先 depth first search
this.dfs = function (callback) {
var color = initColor()
vertices.forEach(v=>{
if(color[v] === 'white'){
dfsVisit(v,color,callback)
}
})
}
let dfsVisit = function (u, color, callback) {
color[u] = 'grey'
if(callback){
callback(u)
}
let neighbors = adjList.get(u)
neighbors.forEach(w=>{
if(color[w]==='white'){
dfsVisit(w,color,callback)
}
})
color[u] = 'black'
}
最后: 所有代码
function Graph() {
let vertices = []
let adjList = new Map()
this.addVertex = function (v) {
vertices.push(v)
adjList.set(v, [])
}
this.addEdge = function (v, w) {
adjList.get(v).push(w)
adjList.get(w).push(v)
}
this.toString = function () {
let s = ''
vertices.forEach(v => {
s += v + '->'
let neighbors = adjList.get(v)
neighbors.forEach(vv => {
s += vv + ' '
})
s += '\n'
})
return s
}
let initColor = function () {
let color = []
vertices.forEach(v => {
color[v] = 'white'
}
)
return color
}
this.bfs = function (v, callback) {
let color = initColor()
let q = new Queue()
q.enqueue(v)
while (!q.isEmpty()) {
let u = q.dequeue(),
neighbors = adjList.get(u)
color[u] = 'grey' // 第一次探索
neighbors.forEach(w => {
if(color[w] === 'white'
)
{
color[w] = 'grey'
q.enqueue(w)
}
})
color[u] = 'black'
if (callback) {
callback(u)
}
}
}
this.BFS = function (v) {
let color = initColor()
let q = new Queue()
let d = []
let pred = []
q.enqueue(v)
vertices.forEach(vv => {
d[vv] = 0
pred[vv] = null
}
)
while (!q.isEmpty()) {
let u = q.dequeue()
let neighbors = adjList.get(u)
color[u] = 'grey'
neighbors.forEach(w => {
if(color[w] === 'white'){
color[w]= 'grey '
d[w] = d[u] + 1
pred[w] = u
q.enqueue(w)
}
})
color[u] = 'black'
}
return {
distances: d,
predecessor: pred
}
}
this.dfs = function (callback) {
var color = initColor()
vertices.forEach(v=>{
if(color[v] === 'white'){
dfsVisit(v,color,callback)
}
})
}
let dfsVisit = function (u, color, callback) {
color[u] = 'grey'
if(callback){
callback(u)
}
let neighbors = adjList.get(u)
neighbors.forEach(w=>{
if(color[w]==='white'){
dfsVisit(w,color,callback)
}
})
color[u] = 'black'
}
}
var g = new Graph()
var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
myVertices.forEach(v => {
g.addVertex(v)
})
g.addEdge('A', 'B')
g.addEdge('A', 'C')
g.addEdge('A', 'D')
g.addEdge('C', 'D')
g.addEdge('C', 'G')
g.addEdge('D', 'G')
g.addEdge('D', 'H')
g.addEdge('B', 'E')
g.addEdge('B', 'F')
g.addEdge('E', 'I')
/*console.log(g.BFS('I'))*/
g.dfs((v)=>{
console.log(v)
})
function Queue() {
let items = []
//队尾添加项
this.enqueue = function (v) {
items.push(v)
}
//移除队列第一项
this.dequeue = function () {
return items.shift()
}
//查看队列第一项
this.front = function () {
return items[0]
}
//检查是否为空
this.isEmpty = function () {
return items.length == 0
}
//返回队列长度
this.size = function () {
return items.length
}
//打印队列
this.print = function () {
console.log(items.toString())
}
}
网友评论