数据结构-非线性结构-图
概念
有向图
- 弧:
- 出度:
- 入度:
- 度:
- 关系式:
- 路径:
- 子图:
- 强连通图:
- 强连通分量(极大子图):
- 网:
- 有向树
- 有向完全图:
单源点最短路径
无向图
- 边:
- 度:
- 路径:
- 子图:
- 连通图:
- 连通分量:
- 网:
- 无向完全图:
存储结构
邻接矩阵
邻接链表
type VNode={data:char;firstarc:ArcNode};
type ArcNode={nextarc:ArcNode;weight:number};
type Graph={Vnum:number; AdjList:Vnode[]};
推广
生成树
最小生成树
- Prim
- 对于连通网N,依次遍历顶点,把其权值最小的边和该点并入T,直到V(N)=V(T),T为N的最小生成树
- Kruskal
- 对于连通网N,建立非连通图T.使V(N)=V(T),查找N中权最小的边,归入T,直到T连通,T为N的最小生成树
AOV网
- 在工程领域,通常把大工程划分为多个子工程,子工程有先后关系,所有子工程完成后,整个工程就完成了。
- 大工程:AOV
- 子工程:V
- 优先级:E
- AOV=(V,E)
- AOV 网中存在回路称为DAG,工程必不能完成。
- 在AOV网中找到ID(v)=0,从网中移除v,AOV中不存在入度=0的点为止,如果成立,则该AOV网是DAG。
AOE网
- 使用边记录活动,顶点记录事件(活动结束/开始),权记录活动信息
- 源点,入度为0
- 汇点,出度为0
- 最早发生时间
- 最晚结束时间
单源点最短路径
- 求从源点开始到各点的最短路径
每对点最短路径
- 以每个点为源点,计算每对顶点的最短路径