// 封装图结构 这里需要自己引入封装的字典/对象和队列
function Graph() {
// 属性 1、顶点、 2边 边是一个字典/对象，字典/对象里面的建就是顶点，值[] 里面放和顶点有连线的顶点
this.vertexes = []
const edges = new derectory()
// 1、添加顶点的方法 我在添加这个顶点的同时 我需要给他同时创建一个字典/对象来保存边的数据
this.addVertex = function (v) {
this.vertexes.push(v)
this.edges.set(v, [])
}
// 2、添加边的方法 v1是要往哪个顶点添加边，v2是你要添加的顶点 两个顶点会连成一条线
this.addEdge = function (v1, v2) {
// if (v1 === v2) return false 是否需要判断
// 无向图应该是互相连线的
this.edges.get(v1).push(v2)
this.edges.get(v2).push(v1)
}
// 3、返回边的邻近表字符串
this.toString = function () {
let resStr = ''
for (let i of vertexes) {
resStr += i + '->'
let edgesArr = this.edges.get(i) //这里返回的是一个数组
for (let j of edgesArr) {
resStr += j + ' ' //继续往后拼接 每一个字符串都往后连续拼接 j 直到循环完毕 再返回第一个循环的起点
}
resStr += '\n'
}
}
// 4.1、初始化状态颜色
this.initColor = function () {
let color = []
for (let i in this.vertexes) {
colors[this.vertexes[i]] = 'white' //数组本身也是一种对象 数组的下标也能改变
}
return color
}
let bstArr = []
// 4.2、广度优先遍历 广度优先采用队列作为基础数据结构
// 1、传入起始顶点作为参数,firstV 无论是广度优先还是深度优先都需要一个起始点
this.bst = function (firstV) {
// 2、要用到队列，所以构造一个实例对象
const queue = new Queue()
// 3、用状态颜色来判断顶点是否被访问过
let color = this.initColor()
// 先将起始点进队
queue.enQueue(firstV)
// 只要队列里还有顶点就循环
while (!this.queue.size) {
// 第一个顶点先出队，并且颜色改为已访问过的grey
let outV = queue.deQueue() //第二次outV已经变成了下一个顶点
color[outV] = 'grey'
// 此时遍历他的边
for (let i of this.edges.get(outV)) {
queue.enQueue(i)
if (color[i] === 'white') {
color[i] = 'grey'
}
}
// push的应该是每次从队列出去的顶点 第一次outV为你传入的起点，第二次变为他的边顶点
this.bstArr.push(outV)
color(outV) = 'black'
}
}
let dftArr = []
// 5.1、深度优先遍历 deep-first traversal
this.dft = function (firstV) {
// 不能把初始化颜色写在递归函数里，这样递归过程中会把他再初始化
let color = this.initColor
return this.dftRecursion(firstV, color)
}
//5.2、深度优先遍历的递归函数
this.dftRecursion = function (firstV, color) {
// 1、从firstV开始 被访问过的顶点变为灰色
color[firstV] = 'grey'
// 2、按遍历顺序处理顶点
this.dftArr[firstV]
// 3、这时候要访问他的边顶点了
for (let i of this.edges.get[firstV]) {
// 此时i为B 此时就应该调用递归函数 遍历B的边顶点
if (color[i] === 'white')
this.dftRecursion(i, color)
}
// 4、遍历过渡顶点为黑色
color[firstV] = 'black'
}
}
总结
1、图结构需要的属性为顶点和边，边用字典表示最好，key为顶点，value为与顶点有连线的其他顶点数组
2、添加顶点时需要同时为这个顶点创建一个对应的空字典，保存之后的连线顶点
3、有向图是只能A到B或者B到A ，无向图是可以互相通行，所以无向图的连线应该是互相的
4、图结构的广度优先遍历 (采用队列) 和深度优先遍历 (采用递归) 都需要一个初始顶点，并且应该用颜色状态来表示是否被访问过和处理过
广度优先搜索.png
深度优先搜索.png
