文档介绍：()§、比线性和树型结构更复杂的非线性数据结构,可广泛用于描述自然界各种关系。右图所示即为一图型结构:ABCEFDGraph=(V,R)其中:V={ai|ai∈D0,i=1,2,…,n,n≥0}R={E}E={<x,y>|P(x,y)∧(x,y∈V)}其中D0为某一数据对象,V为顶点集,E为边集。图的一些基本术语:顶点(vertex)数据元素所构成的结点通常称为顶点。弧(arc)若两个顶点间有关系<x,y>∈E,则称<x,y>为一条弧。弧头(head--又称终端点terminalnode)若<x,y>为一条弧,则顶点y称为弧头。弧尾(tail--又称初始点initialnode)若<x,y>为一条弧,则顶点x称为弧尾。有向图(directedgraph)若<x,y>∈E,并不总有<y,x>∈E,则称此图为有向图。无向图(undirectedgraph)若<x,y>∈E,总有<y,x>∈E,则称此图为无向图。边(edge)无向图中两条弧<x,y>和<y,x>可用一条边(x,y)来表示。pletedgraph)具有n*(n-1)/2条边的无向图称为完全图。pleteddirectedgraph)具有n*(n-1)条弧的有向图称为有向完全图。稀疏图(sparsegraph)边数很少的图称为稀疏图。权(weight)有些图的边或弧具有一定的大小,称之为权。work)带权值的图又称为网或网络。子图(subgraph)由图的部分顶点和边组成的新图称为原图的子图。生成子图(spanningsubgraph)由图的全部顶点和部分边组成的子图称为原图的生成子图。稠密图(densegraph)边数很多的图称为稠密图。邻接点(adjacent)若边(vi,vj)∈E,则vi与vj互为邻接点。依附(incident)若边(vi,vj)∈E,则称边(vi,vj)依附于顶点vi和vj。相关联(correlative)若边(vi,vj)∈E,又称边(vi,vj)与顶点vi和vj相关联。顶点的度(degree)与顶点相关联的边数称为该顶点的度,又分为入度和出度。顶点的入度(indegree)以顶点为头的弧数称为该顶点的入度。顶点的出度(outdegree)以顶点为尾的弧数称为该顶点的出度。路径(path)由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。回路(loop--又称环cycle)起点和终点为同一顶点的路径称为回路。连通(connected)无向图中顶点vi到vj间有路径存在,则称vi和vj是连通的。连通图(connectedgraph)无向图中任意两顶点间均存在路径,则称该图为连通图。连通分量(ponent)无向图中的极大连通子图称为原图的连通分量。强连通图(stronglyconnectedgraph)有向图中任意两顶点间均存在路径,则称该图为强连通图。强连通分量(ponent)有向图中的极大强连通子图称为原图的强连通分量。生成树(spanningtree)连通图的极小连通生成子图称为原图的生成树。有向树(directedtree)恰有一个顶点入度为0,其余顶点入度均为1的有向图。生成森林(spanningforest)由多棵有向树构成的有向图的生成子图称为生成森林。最小代价生成树(minimumcostspanningtree)连通网中由最小权值的边构成的生成树。图的基本操作:InitiateGetvertexFirstadjNextadjInsvertexTraverseInsarcDelvertexDelarc§:ABCEFD1、邻接矩阵(adjacencymatrix)ABCDEF0000011010000001000000100**********ABCDEFAij={0(vi,vj)∈E1(vi,vj)∈E√#definemaxvtxnumuser_supplytypedefintadjmatrix[maxvtxnum][maxvtxnum];typedefstruct{adjmatrixarcs;intvtxnum,um;}graph;2、关联矩阵(correlatedmatrix)Bij={1vi是ej的弧头0vi与ej不相关联-1vi是ej的弧尾ABCEFDe1e2e3e4e5e6e7e1e2e3e4e5e6e7100000-1-1-10010001-10000001-10000001-11000000-11ABCDEF#definemaxvtxnumuser_supply#definemaxedgenumuser_supplytypedefintcormatrix[maxvtxnum][maxedgen