图
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
注意：顶点有时也称为节点或者交点，边有时也称为链接
主要研究的目的是 事物之间的关系， 顶点代表事物，边代表两个事物之间的关系
以下图栗子
image.png
image.png
image.png
图通常的特点
- 一组顶点： 通常用V(Vertex)表示顶点的集合
- 一组边： 通常用E(Edge)表示边的集合
- 边是顶点之间的连线
- 边可以是有向的，也可以是无向的
- 比如： A---B，通常表示无向。 A-->B通常表示有向
图的术语
- 顶点
- 边
- 相邻顶点： 由一条边连接在一起的顶点称为相邻顶点
- 度：一个顶点的度是相邻顶点的数量
- 路径： 顶点v1,v2....vn的一个连续序列
- 简单路径： 简单路径要求不包含重复的顶点
- 回路： 第一个顶点和最后一个顶点相同的路径
- 无向图： 所有的边都没有方向
- 有向图： 图中的边是有方向的
- 无权图： 边没有携带权重
- 有权图：边有一定的权重（表示你希望的数据：如花费的时间更少）
图的表示
一种比较常见的便是图的方式:
邻接矩阵
- 邻接矩阵让 每个节点 和 一个整数 相 关联， 该整数作为数组的 下标值。
-
我们用一个数组来表示顶点之间的连接
image.png
解析
- 在二维数组中 ， 0表示没有连线，1表示有连线
*通过二维数组，我们可以很快找到一个顶点和哪些顶点有连线
邻接矩阵的问题
如果图是一个稀疏图， 那么矩阵中将存在大量的0，浪费存储空间来表示不存在的边。
另一种表示图的方式
邻接表
邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
这个列表有很多方式来储存：数组、链表、字典(哈希表)都可以
image.png
图解析：
比如我们要表示和 A顶点有关联的顶点(边）， A和B,C,D有边
那么我们可以通过A找到对应的数组/链表/字典，取出其中的内容。
邻接表问题
邻接表计算“出度”是比较简单的（出度：指向别人的数量，入度：指向自己的数量）
邻接表如果要计算有向图的“入度”，是非常麻烦的事情，必须构造一个“逆邻接表”
图的遍历算法：
- 广度优先搜索(Breadth-First Search)BFS
- 深度优先搜索(Depth-First Search) DFS
两种遍历算法，都需要明确指定第一个被访问的顶点
两种算法思想
- BFS: 基于队列，入队列的顶点先被探索
- DFS：基于栈或使用递归， 通过将顶点存入栈中，顶点沿着路径被探索，存在新的相邻顶点就去访问
为了记录顶点访问状态，用三种颜色来表示
- 白色： 该顶点没有被访问过
- 灰色： 顶点被访问过，但是没有被探索过
- 黑色： 顶点被访问过且被探索过。
image.png
image.png
代码实现
<script src="dict.js"></script>
<script src="queue.js"></script>
<script>
// 封装图结构
function Graph() {
// 属性
this.vertexes = [] // 存储顶点
this.edges = new Dictionay() // 存储边
// 添加方法
// 添加顶点 参数 v: 顶点
Graph.prototype.addVertex = function (v) {
// 把顶点放到 vertexes
this.vertexes.push(v)
// 并且在 字典中 设置key为v， value为空数组
// 后面有边之后 放到 空数组中
this.edges.set(v, [])
}
// 添加边
// 参数 v1第一个顶点 v2为第二个顶点
// 这里实行的无向图， v1和v2之间都要有边
Graph.prototype.addEdge = function (v1, v2) {
// 在字典中 取出第一个顶点v1的 数组 。并把顶点v2放到数组中
this.edges.get(v1).push(v2)
// 同理把v2放到v1对应的数组中
this.edges.get(v2).push(v1)
}
Graph.prototype.toString = function () {
var resultStr = ""
for (var i = 0; i < this.vertexes.length; i++) {
resultStr += this.vertexes[i] + "->"
var adj = this.edges.get(this.vertexes[i])
for (var j = 0; j < adj.length; j++) {
resultStr += adj[j] + " "
}
resultStr += "\n"
}
return resultStr
}
// 初始化颜色
// * 白色： 该顶点没有被访问过
// * 灰色： 顶点被访问过，但是没有被探索过
// * 黑色： 顶点被访问过且被探索过。
Graph.prototype.initializeColor = function () {
// 定义每个顶点对应的颜色
var colors = []
// 把所有顶点 初始化为 白色
for (var i = 0; i < this.vertexes.length; i++) {
colors[this.vertexes[i]] = "white"
}
return colors
}
// 广度优先搜索
// 参数 v 初始化 顶点 handler 处理函数
Graph.prototype.bfs = function (v, handler) {
// 1.初始化颜色 获取所有顶点颜色列表
var color = this.initializeColor()
// 2.创建队列
var queue = new Queue()
// 3.将传入的顶点放入队列中
queue.enqueue(v)
// 4.从队列中依次取出和放入数据
while (!queue.isEmpty()) {
// 4.1.从队列中取出数据（顶点）
var qv = queue.dequeue()
// 4.2.获取qv相邻的所有顶点
var qList = this.edges.get(qv)
// 4.3.将qv的颜色设置成灰色 被访问了，但是还没被探测
color[qv] = "gray"
// 4.4.将qList的所有顶点依次压入队列中
for (var i = 0; i < qList.length; i++) {
var item = qList[i]
// 当前顶点 是白色(没有被访问) 才加入队列（避免队列中有重复的顶点）
if (color[item] === "white") {
// 并且把顶点颜色 设置为灰色（已经被访问过了）
color[item] = "gray"
queue.enqueue(item)
}
}
// 4.5.处理qv 探测
handler && handler(qv)
// 4.6.因为qv已经探测完毕, 将qv设置成黑色
color[qv] = "black"
}
}
// 深度优先搜索
Graph.prototype.dfs = function (handler) {
// 1.初始化颜色
var color = this.initializeColor()
// 2.遍历所有的顶点, 开始访问
for (var i = 0; i < this.vertexes.length; i++) {
if (color[this.vertexes[i]] === "white") {
this.dfsVisit(this.vertexes[i], color, handler)
}
}
}
// dfs的递归调用方法
// u 当前访问的顶点
// color 颜色列表 （有所有的顶点）
// handler 处理函数
Graph.prototype.dfsVisit = function (u, color, handler) {
// 1.开始访问 将u的颜色设置为灰色
color[u] = "gray"
// 2.处理u顶点
handler && handler(u)
// 3.访问 u的所有邻接顶点
var uList = this.edges.get(u)
for (var i = 0; i < uList.length; i++) {
var item = uList[i]
// 当前顶点 是白色(没有被访问) 才递归调用
if (color[item] === "white") {
this.dfsVisit(item, color, handler)
}
}
// 4.将u设置为黑色
color[u] = "black"
}
}
// 测试代码
var graph = new Graph()
// 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (var i = 0; i < myVertexes.length; i++) {
graph.addVertex(myVertexes[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');
// 打印结果
alert(graph)
// 调用广度优先算法
var result = ""
graph.bfs(graph.vertexes[0], function (v) {
result += v + " "
})
console.log(result) // A B C D E F G H I
// 调用深度优先算法
result = ""
graph.dfs(function (v) {
result += v + " "
})
console.log(result) // A B E I F C D G H
</script>
dict.js
// 创建字典的构造函数
function Dictionay() {
// 字典属性
this.items = {}
// 字典操作方法
// 在字典中添加键值对
Dictionay.prototype.set = function (key, value) {
this.items[key] = value
}
// 判断字典中是否有某个key
Dictionay.prototype.has = function (key) {
return this.items.hasOwnProperty(key)
}
// 从字典中移除元素
Dictionay.prototype.remove = function (key) {
// 1.判断字典中是否有这个key
if (!this.has(key)) return false
// 2.从字典中删除key
delete this.items[key]
return true
}
// 根据key去获取value
Dictionay.prototype.get = function (key) {
return this.has(key) ? this.items[key] : undefined
}
// 获取所有的keys
Dictionay.prototype.keys = function () {
return Object.keys(this.items)
}
// 获取所有的value
Dictionay.prototype.values = function () {
return Object.values(this.items)
}
// size方法
Dictionay.prototype.size = function () {
return this.keys().length
}
// clear方法
Dictionay.prototype.clear = function () {
this.items = {}
}
}
queue.js
// 自定义队列
function Queue() {
var items = []
// 队列操作的方法
// enter queue方法
this.enqueue = function (element) {
items.push(element)
}
// delete queue方法
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
}
}
网友评论