图
约 768 字大约 3 分钟
2019-06-08
受限于篇幅和作者个人水平，本篇仅粗略的介绍 图 的一些基本概念，有兴趣的读者可以自行了解更多的知识。
概述
图（Graph） 是一种表示多对多关系的非线性数据结构，由 顶点（Vertex） 和 边（Edge） 组成。
图的核心概念
顶点（Vertex）：图中的基本元素（节点）
边（Edge）：连接两个顶点的关系（可带权重）
类型：
无向图：边无方向（A-B 表示双向关系）
有向图：边有方向（A→B 表示单向关系）
术语：
度（Degree）：顶点连接的边数
路径（Path）：顶点序列通过边连接
环（Cycle）：起点=终点的路径
连通图：任意两顶点间存在路径
图的表示方法
邻接矩阵（Adjacency Matrix）
class GraphMatrix {
private matrix: number[][]
private vertices: string[]
constructor(vertices: string[]) {
this.vertices = vertices
this.matrix = Array.from({ length: vertices.length })
.fill(0)
.map(() => Array.from({ length: vertices.length }).fill(0))
}
// 添加边（无向图）
addEdge(v1: string, v2: string, weight: number = 1) {
const i = this.vertices.indexOf(v1)
const j = this.vertices.indexOf(v2)
this.matrix[i][j] = weight
this.matrix[j][i] = weight // 有向图时删除此行
}
// 打印矩阵
print() {
console.log(` ${this.vertices.join(' ')}`)
this.matrix.forEach((row, i) => {
console.log(`${this.vertices[i]} ${row.join(' ')}`)
})
}
}
// 使用示例
const graph = new GraphMatrix(['A', 'B', 'C'])
graph.addEdge('A', 'B', 3)
graph.addEdge('B', 'C', 2)
graph.print()
/* 输出：
A B C
A 0 3 0
B 3 0 2
C 0 2 0
*/邻接表（Adjacency List）
interface Edge { vertex: string, weight: number }
class GraphList {
private adjacencyList: Map<string, Edge[]> = new Map()
addVertex(vertex: string): void {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, [])
}
}
addEdge(v1: string, v2: string, weight: number = 1): void {
this.adjacencyList.get(v1)?.push({ vertex: v2, weight })
// 无向图需添加反向边（有向图时删除）
this.adjacencyList.get(v2)?.push({ vertex: v1, weight })
}
getNeighbors(vertex: string): Edge[] {
return this.adjacencyList.get(vertex) || []
}
print() {
this.adjacencyList.forEach((edges, vertex) => {
const edgeStr = edges.map(e => `${e.vertex}(${e.weight})`).join(', ')
console.log(`${vertex} -> ${edgeStr}`)
})
}
}
// 使用示例
const graph = new GraphList()
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addEdge('A', 'B', 3)
graph.addEdge('B', 'C', 2)
graph.print()
/* 输出：
A -> B(3)
B -> A(3), C(2)
C -> B(2)
*/图的应用场景
- 社交网络：好友关系（顶点=用户，边=关注）
- 路径规划：地图导航（顶点=地点，边=道路权重）
- 依赖分析：编译顺序（有向无环图拓扑排序）
- 推荐系统：用户-商品二部图