1.工具类:队列和字典
export class DictionNary {
constructor ( ) {
this . items = { }
}
set ( key, value) {
this . items[ key] = value
}
has ( key ) {
return this . items. hasOwnProperty ( key)
}
get ( key) {
return this . has ( key) ? this . items[ key] : undefined
}
remove ( key ) {
if ( this . has ( key) ) {
delete this . items[ key]
return true
}
return false
}
keys ( ) {
return Object. keys ( this . items)
}
values ( ) {
return Object
}
size ( ) {
return this . keys ( ) . length
}
clear ( ) {
this . items = { }
}
toString ( ) {
if ( this . size ( ) > 0 ) {
let objString = ` { ${ this . keys ( ) . join ( ',' ) } } `
return objString
} else {
return '{}'
}
}
}
export class Queue {
constructor ( ) {
this . items = [ ]
}
enqueue ( element ) {
this . items. push ( element)
}
dequeue ( ) {
return this . items. shift ( )
}
front ( ) {
return this . items[ 0 ]
}
isEmpty ( ) {
return this . items. length == 0
}
size ( ) {
return this . items. length
}
toString ( ) {
return this . items. toString ( )
}
}
2. 图的封装
class Graph {
constructor ( ) {
this . vertexes = [ ]
this . edges = new DictionNary ( )
}
addVertex ( v ) {
this . vertexes. push ( v)
this . edges. set ( v, [ ] )
}
addEdge ( v1, v2 ) {
this . edges. get ( v1) . push ( v2)
this . edges. get ( v2) . push ( v1)
}
toString ( ) {
let result = ''
for ( let i = 0 ; i < this . vertexes. length; i++ ) {
result += this . vertexes[ i] + ' -> '
const neighbors = this . edges. get ( this . vertexes[ i] )
for ( let j = 0 ; j < neighbors. length; j++ ) {
result += neighbors[ j] + ' '
}
result += '\n'
}
return result
}
initializeColor ( ) {
const colors = [ ]
for ( let i = 0 ; i < this . vertexes. length; i++ ) {
colors[ this . vertexes[ i] ] = 'white'
}
return colors
}
bfs ( firstVertex, callback ) {
const colors = this . initializeColor ( )
const queue = new Queue ( )
queue. enqueue ( firstVertex)
while ( ! queue. isEmpty ( ) ) {
const v = queue. dequeue ( )
const neighbors = this . edges. get ( v)
colors[ v] = 'gray'
for ( let i = 0 ; i < neighbors. length; i++ ) {
const w = neighbors[ i]
if ( colors[ w] === 'white' ) {
colors[ w] = 'gray'
queue. enqueue ( w)
}
}
colors[ v] = 'black'
callback ( v)
}
}
dfs ( initVertex, callback ) {
const colors = this . initializeColor ( )
this . dfsVisit ( initVertex, colors, callback)
}
dfsVisit ( vertexes, colors, callback ) {
colors[ vertexes] = 'gray'
callback ( vertexes)
const neighbors = this . edges. get ( vertexes)
for ( let i = 0 ; i < neighbors. length; i++ ) {
const w = neighbors[ i]
if ( colors[ w] === 'white' ) {
this . dfsVisit ( w, colors, callback)
}
}
colors[ vertexes] = 'black'
}
}
图测试用例
const graph = new Graph ( )
const myVertices = [ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' , 'G' , 'H' , 'I' ]
for ( let i = 0 ; i < myVertices. length; i++ ) {
graph. addVertex ( myVertices[ i] )
}
graph. addEdge ( 'A' , 'B' )
graph. addEdge ( 'A' , 'C' )
graph. addEdge ( 'A' , 'D' )
graph. addEdge ( 'C' , 'D' )
graph. addEdge ( 'C' , 'G' )
graph. addEdge ( 'D' , 'G' )
graph. addEdge ( 'D' , 'H' )
graph. addEdge ( 'B' , 'E' )
graph. addEdge ( 'B' , 'F' )
graph. addEdge ( 'E' , 'I' )
console. log ( graph. toString ( ) )
let result = ''
graph. bfs ( graph. vertexes[ 0 ] , function ( v ) {
result += v + ' '
} )
console. log ( result)
let deepRsult = ''
graph. dfs ( graph. vertexes[ 0 ] , function ( v ) {
deepRsult += v + ' '
} )
console. log ( deepRsult)