数据结构---图

图的定义和术语

• 有向图（Directed graph）
• 无向图（Undirected graph）

图的边和弧的关系

完全图

顶点的度

路径

路径Path(eG) from v_pto v_q :{Vp Vn, Vp…, Vin Vq],其中(Vp, V_i1) (V_i1, V_i2),…, ( V_in,V_q)或者<V_p,V_i1>,…,< V_in,V_q>属于E（G）或A(G)。

• 路径长度(Length of a path):路径上边或孤的数目
• 简单路径(Simple path):路径中不含相同顶点的路径,就是没有回路。
• 回路或环(Cycle):首尾顶点相同的路径,称为回路或环。即:(v=v_i0, v_i1. ..., vim=v'=v)
• 简单回路(Simple cycle):除首尾顶点外，路径中不含相同顶点的回路

连通

• 顶点连通:若顶点v到顶点v'有路径,则称顶点v与v’是连通的
• 无向连通图:若无向图中任意两个顶点vi,vj都是连通的,则称该图是连通图(vi vj)
• 有向连通图:若有向图中任意两个项点vivj，都存在从vi到vj和从vj到vi的路径,则称该图为强连通图(vivj)
• 无向图连通分量:无向图中极大连通子图,称为连通分量
• 有向图强连通分量:有向图中极大强连通子图,称为强连通分量

生成树

生成树:没无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点,且只有n-1条边的连通子图

图的存储结构

图的邻接矩阵

网的邻接矩阵

邻接表

将矩阵中每一行转换为一个链表。

无向图邻接表

对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域:

• 邻接点域(adjvex)：记载与顶点Vi邻接的顶点信息;
• 键域(nextarc)：指向下一个与顶点Vi邻接的链表p结点。

每个链表附设一个头结点,头结点结构为:

• vexdata：存放顶点信息（姓名、编号等)
• fristarc：指向链表的第一个结点。

有向图邻接表

与无向图的邻接表结构一样。只是在第i条链表上的结点是以y为孤尾的各个弧头顶点。

有向图逆邻接表

与有向图的邻接表结构一样。只是在第i条链表上的结点是以V为弧头的各个弧尾顶点。

图的遍历

从图中某个顶点出发,沿路径使图中每个顶点被访问且仅被访问一次的过程,称为遍历图。

深度优先搜索（depth-first-search)~(stack)

访问指定的某顶点V,将V作为当前顶点
访问当前顶点的下一未被访问过的邻接点,并以该邻接点作为当前顶点
重复2，直到所有和当前顶点有路径相通的顶点都被访问到
沿搜索路径回很，很到尚有邻接点未被访问过的某结点
将该结点作为当前结点,重复以上步骤，直到所有顶点被访问过的为止

广度优先搜索（level-order traversal)~(queue)

首先访问指定顶点v，将v作为当前顶点
访问当前顶点的所有未访问过的邻接点，并
依次将访问的这些邻接点作为当前顶点
重复2，直到所有顶点被访问为止

最小生成树

生成树——是无向连通图G的某个连通子图
生成树的三大要素：
① n个顶点 ② n-1条边 ③ 连通(不能有回路)

生成树代价

对图中每条边赋于一个权值(代价）,则构成一个网,网的生成树G’=(V.{T})的代价是T中各边的权值之和。
最小生成树就是网上所有可能的生成树中,代价最小的一类生成树。
最小生成树也不一定唯一。