1图的基本概念7
2图的存储结构7
3图的遍历7
4最小生成树7
5一点到其他点最短路径问题7
6拓扑排序7
7关键路径第七章图7
1图的基本概念�图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y∈V}或E={|x,y∈V&&Path(x,y)}�有向图与无向图是有序的
边就称为弧，x为弧尾，y为弧头
(x,y)是无序的
�完全图�若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图
�有n个顶点的有向图有n(n-1)条边,则此图为完全有向图
00001111222265433�邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点
�子图设有两个图G＝(V,E)和G‘＝(V’,E‘)
若V’⊆V且E‘⊆E,则称图G’是图G的子图
�权某些图的边具有与它相关的数,称之为权
这种带权图叫做网络
�稠密图和稀疏图若边或弧的个数e∉∈vex=k;//建立边结点,vex域赋为kp->next=Adj[i]
head;Adj[i]
head=p;//头插入建链�2
有向图的邻接表和逆邻接表ABCdataheadABC012Vexnext∧邻接表(出边表)dataheadABC012Vexnext逆邻接表(入边表)102∧∧∧∧∧011�3
网络(带权图)的邻接表BBAACCDD69528dataheadABCD0123Vexweightnext∧∧∧∧1536283219((出边表出边表))((顶点表顶点表))�邻接表的特征：�在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定
�求某个顶点的度（入度或出度）比较方便；�设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点
