Shared 函数库

Appearance

Graph ​

图数据结构，支持有向图和无向图，提供 BFS、DFS、拓扑排序等算法。

函数签名 ​

typescript
function createGraph(directed?: boolean): Graph

interface Graph {
  addVertex(vertex: string): void
  addEdge(from: string, to: string, weight?: number): void
  removeVertex(vertex: string): void
  removeEdge(from: string, to: string): void
  getVertices(): string[]
  getNeighbors(vertex: string): Array<{ vertex: string; weight: number }>
  bfs(start: string): string[]
  dfs(start: string): string[]
  topologicalSort(): string[] | null
  hasCycle(): boolean
  vertexCount(): number
  edgeCount(): number
  clear(): void
}

API 说明 ​

addEdge(from, to, weight?) ​

添加边，自动创建不存在的顶点。

时间复杂度：O(1)

bfs(start): string[] ​

广度优先搜索。

时间复杂度：O(V + E)

dfs(start): string[] ​

深度优先搜索。

时间复杂度：O(V + E)

topologicalSort(): string[] | null ​

拓扑排序（仅有向无环图）。

时间复杂度：O(V + E)

使用示例 ​

typescript
import { createGraph } from '@shared/functions/data-structures/Graph'

const graph = createGraph(true)  // 有向图

graph.addEdge('A', 'B')
graph.addEdge('B', 'C')
graph.addEdge('A', 'C')

console.log(graph.bfs('A'))  // ['A', 'B', 'C']
console.log(graph.topologicalSort())  // ['A', 'B', 'C']

应用场景 ​

  1. 社交网络：好友关系图
  2. 路径规划：导航系统
  3. 任务调度：项目依赖关系
  4. 网页爬虫：链接遍历

Copyright © 2023-present