文档介绍：第10章图图(graph)是一种比线性表、树更为复杂的数据结构。在线性表中,数据元素之间呈线性关系,即每个元素只有一个直接前驱和一个直接后继。图的应用领域十分广泛,如化学分析、工程设计、遗传学、人工智能等。本章主要介绍图的定义、图的存储结构、图的遍历、最小生成树、关键路径和最短路径。本章重点:1、图的定义及性质2、图的邻接矩阵和邻接表表示3、图的各种遍历4、最小生成树5、关键路径6、。在图中,数据元素通常称为顶点(Vertex)。其中,顶点集合V不能为空,边表示顶点之间的关系。若<x,y>∈E,则<x,y>表示从顶点x到顶点y存在一条弧(Arc),x称为弧尾(tail)或起始点(initialnode),y称为弧头(head)或终端点(terminalnode)。这样的图被称为有向图(digraph)。如果<x,y>∈E且有<y,x>∈E,即E是对称的,则用无序对(x,y)代替有序对<x,y>和<y,x>,表示x与y之间存在一条边(edge),这样的图称为无向图(undigraph)。。:G=(V,E),其中,V={x|x∈数据元素集合},E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示<x,y>的意义或信息。,有向图G1可以表示为G1=(V1,E1),其中,顶点的集合为V1={a,b,c,d},边的集合为E1={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>}。无向图G2可以表示为G2=(V2,E2),其中,顶点的集合为V2={a,b,c,d},边的集合为E2={(a,b),(a,c),(a,d),(b,c),(c,d)}。=(V,E),若边(vi,vj)∈E,则称vi和vj互为邻接点(adjacent),即vi和vj相邻接。边(vi,vj)依附于顶点vi和vj,或者说(vi,vj)与顶点vi、vj相关联。对于有向图G=(V,A),若弧<vi,vj>∈A,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi。弧<vi,vj>和顶点vi、vj相关联。无向图G2的边的集合为E={(a,b),(a,c),(a,d),(b,c),(c,d)},顶点a和b互为邻接点,边(a,b)依附于顶点a和b。顶点c和d互为邻接点,边(c,d)依附于顶点c和d。有向图G1的弧的集合为A={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>},顶点a邻接到顶点b,弧<a,b>与顶点a和b相关联。顶点c邻接自顶点d,弧<d,c>与顶点d和c相关联。,顶点v的度是指与v相关联的边的数目,记作TD(v)。对于有向图,以顶点v为弧头的数目称为顶点v的入度(indegree),记作ID(v)。以顶点v为弧尾的数目称为v的出度(outdegree),记作OD(v)。顶点v的度(degree)为TD(v)=ID(v)+OD(v)。无向图G2中顶点a的度为3,顶点b的度为2,顶点c的度为3,顶点d的度为2。有向图G1的弧的集合为A={<a,b>,<a,d>,<b,c>,<c,a>,<c,b>,<d,c>},顶点a、b、c和d的入度分别为1、2、2和1,顶点a、b、c和d的出度分别为2、1、2和1,顶点a、b、c和d的度分别为3、3、4和2。若图的顶点的个数为n,边数或弧数为e,顶点vi的度记作TD(vi),则顶点的度与弧或者边数满足关系:e=,从顶点v到顶点v’的路径(path)是从v出发,经过一系列的顶点序列到达顶点v’。如果G是有向图,则路径也是有向的,路径的长度是路径上弧或边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外,其他顶点不重复出