非线性结构（下）
非线性结构¶
考点七 并查集的基本操作¶
考点八 图的概念和性质¶
- 定义中的“极大”，意思是在保证内部所有节点都能互相可达的前提下，尽可能多地圈进节点和边。若一个顶点只有出边或入边则该顶点必定单独构成一个连通分量。
保证连通：让n - 1个顶点实现一个完全图，最后一个顶点连上就行了。
考点九 邻接矩阵和邻接表¶
考点十 十字链表和邻接多重表¶
十字链表就按照BOK老师讲的，先填非指针域，并且画表格，按坐标画会很简单，行就代表出，列就代表入。十字链表代表着有向图的存储。
邻接多重表画法有些诡异，ivex是多少弧结点就放在哪一行，当然，ivex和jvex是可以互换的。下图右下角的2, 4是为了图美观才那么放的。连线时从0 - n，自顶点开始找自己序号连线。
DFS和BFS¶
考点十二 拓扑排序¶
考点十三 最小生成树¶
考点十四 最短路径¶
- dijkstra不能解决负权路径。
- floyd不能解决负权回路。
考点十五 关键路径¶
\(v\) 代表 Vertex（顶点，也就是图中的节点/事件）。
\(e\) 代表 Earliest（最早的）。
\(l\) 代表 Latest（最迟的/最晚的）。