网站后台对接表,网站建设好处zu97,江桥做网站,东莞常平汽车站时刻表第七章 图 Graph 7.1 图的定义和术语
顶点 Vertex V 是顶点的有穷非空集合#xff0c;顶点数 |V| n VR 两个顶点之间关系的集合#xff0c;边数 |VR| e
有向图 Digraph v, w Arc v Tail / Inital node w Head / Terminal node
无向图 Undigraph v, w 必…第七章 图 Graph 7.1 图的定义和术语
顶点 Vertex V 是顶点的有穷非空集合顶点数 |V| n VR 两个顶点之间关系的集合边数 |VR| e
有向图 Digraph v, w Arc v Tail / Inital node w Head / Terminal node
无向图 Undigraph v, w 必有 w, v Edge
完全图Completed graph有 n(n-1)/2 条边的无向图有向完全图有 n(n-1) 条弧的有向图稀疏图Sparse graph很少边或弧如 e nlogn稠密图Dense graph权Weight边或弧的相关数子图Subgraph邻接点Adjacent则称顶点 v 和 v 互为邻接点 则称顶点v邻接到顶点v顶点v邻接自顶点v依附Incident边依附于顶点 v 和 v或者说 相关联。度Degree顶点v相关联的边数记为入度InDegree以顶点v为头的弧数出度OutDegree以顶点v为尾的弧数
路径Path从顶点 v 到 v 的一个顶点序列环Cycle第一个顶点和最后一个顶点相同的路径简单路径序列中顶点不重复出现的路简单回路 / 简单环除第一个顶点和最后一个顶点之外其余顶点不重复出现的回路
连通在无向图G中如果顶点v 到顶点v 有路径则称v 和 v 连通连通图Connected Graph无向图中任意两个顶点有路径连通分量Connected Component无向图中的极大连通子图强连通图有向图G中任意两个顶点之间有路径强连通分量有向图中极大强连通子图
生成树连通图的一个极小连通子图包含全部顶点n-1条边 如果一个图有n个顶点小于n-1条边则是非连通图。 如果大于n-1条边一定有环。 有n-1条边的图不一定是生成树。
如果一个有向图恰有一个顶点入度为0其余顶点入度均为1则是一棵有向树。生成森林一个有向图的生成森林由若干棵有向树组成含图中全部顶点最少条边。
图中的顶点不存在全序关系即无法排成一个线性序列。 任何一个顶点都可以被看成是第一个顶点任一顶点的邻接点之间也不存在次序关系。 7.2 图的存储结构
邻接矩阵、邻接表、邻接多重表、十字链表
7.2.1 邻接矩阵 7.2.2 邻接表 总在表头插入结点所以邻接表的存储结构还与弧的输入顺序有关。
图的邻接表存储结构适合存储弧相对较少的稀疏图。 7.3 图的遍历
对图的搜索就是对图中顶点的遍历。
为了不重复访问顶点需要为顶点向量设立一个访问标志数组visit[]并将初值置为FALSE即未被访问。 遍历时在访问后将标志的值改为TRUE。
两种搜索原则
深度优先搜索广度优先搜索。
7.3.1 深度优先搜索
7.3.2 广度优先搜索
