数据结构TypeScript之邻接表实现示例详解
目录
图的结构特点
图由顶点和顶点之间的边构成，记为G(V, E)。其中V是顶点集合，E是边集合。作为一种非线性的数据结构，顶点之间存在多对多关系。
图的分类
无向图：两个顶点之间有两条互相关联的边。A和B之间为双向互通。
有向图：两个顶点之间有一条或两条关联的边。从A到B或者从B到A，只能单向通过。
带权无向图：在无向图的基础上增加一个权值，代表距离等衡量单位。
带权有向图：在有向图的基础上增加一个权值，代表距离等衡量单位。
图的表示
图的表示分为两种方法：邻接矩阵和邻接表。
基于邻接表的概念手动构建四种类型的图，演示如下：
// 有向图
let graph = {
A: { B: null, C: null },
B: { C: null },
C: {},
}
// 无向图
let graph = {
A: { B: null, C: null },
B: { A: null, C: null },
C: { A: null, B: null },
}
// 带权有向图
let graph = {
A: { B: 20, C: 20 },
B: { C: 40 },
C: {},
}
// 带权无向图
let graph = {
A: { B: 20, C: 30 },
B: { A: 20, C: 40 },
C: { A: 30, B: 40 },
}
面向对象方法封装邻接表
构造函数
class Graph {
length: number
vertices: { [key: string]: { [key: string]: null | number } }
isDirected: boolean
constructor(isDirected: boolean = false) {
this.length = 0
this.vertices = {}
this.isDirected = isDirected
}
}
增加顶点和边
顶点增加：利用传入key参数在顶点集合新建一个属性，值为一个空对象用于存储边。
addVertex(...vertices: string[]): Graph {
vertices.forEach((key: string) => {
this.vertices[key] = {}
this.length++
})
return this
}
边增加需要处理的三种情况：
- 顶点不存在：执行
addVertex增加顶点。 - 有向图：两个顶点间建立一条关联的边。
- 无向图：两个顶点间建立互相关联的两条边。
addEdge(v: string, edges: { [key: string]: null | number}): Graph {
if (!this.vertices[v]) { this.addVertex(v) }
for (const key in edges) {
if (!this.vertices[key]) { this.addVertex(key) }
this.vertices[v][key] = edges[key]
if (!this.isDirected) {
this.vertices[key][v] = edges[key]
}
}
return this
}
删除顶点和边
顶点删除：需要删除与这个顶点与其他顶点关联的边。
removeVertex(v: string): Graph {
delete this.vertices[v]
for (const key in this.vertices) {
if (!!this.vertices[key][v]) {
delete this.vertices[key][v]
}
}
this.length--
return this
}
边删除：有向图，删除一个顶点关联的边即可；无向图，删除两条顶点互相关联的边。
removeEdge(v: string, w: string): Graph {
delete this.vertices[v][w]
if (!this.isDirected) {
delete this.vertices[w][v]
}
return this
}
图的遍历
颜色标记
为图中的每一个顶点标记颜色，作为状态记录。三种颜色状态分别如下：
- 白色：未发现的顶点
- 灰色：被发现的顶点
- 黑色：已遍历过的顶点
// 初始化所有顶点颜色，作为初始的状态
const initColor = (vertices: { [key: string]: { [key: string]: null | number } })
: { [key: string]: 'white' | 'gray' | 'black' } => {
let color = {}
for (const key in vertices) {
color[key] = 'white'
}
return color
}
广度优先搜索（队列）
实现思路：
- 初始化所有的顶点状态为白色，选择一个初始顶点入队开始进行搜索。
- 当队列不为空，被选中的初始顶点出队。将这个顶点（通过边）关联的其他顶点入队，并为其标记为灰色。
- 当执行完第二步后，将初始顶点标记为黑色。然后第二步入队的顶点都会重复二、三步骤直到队列为空。
const breadthFirstSearch = (graph: Graph, startVertex: string): string[] => {
let result: string[] = []
let v: string = startVertex
const color = initColor(graph.vertices)
const queue = new Queue()
queue.enqueue(v)
while (!queue.isEmpty()) {
v = queue.dequeue()
for (const key in graph.vertices[v]) {
if (color[key] === 'white') {
queue.enqueue(key)
color[key] = 'gray'
}
}
color[v] = 'black'
result.push(v)
}
return result
}
深度优先搜索（栈）
实现思路：与广度优先搜索步骤相同，队列换为栈即可。需要注意的是深度优先搜索结果不唯一。
const depthFirstSearch = (graph: Graph, startVertex: string): string[] => {
let result: string[] = []
let v: string = startVertex
const color = initColor(graph.vertices)
const stack = new Stack()
stack.push(v)
while (!stack.isEmpty()) {
v = stack.pop()
for (const key in graph.vertices[v]) {
if (color[key] === 'white') {
stack.push(key)
color[key] = 'gray'
}
}
color[v] = 'black'
result.push(v)
}
return result
}
本文相关代码已放置我的Github仓库