图算法图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,R)其中，VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称w为弧头，v为弧尾。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。若<v,w>VR必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边。假设图中有n个顶点，e条边，则假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，顶点的出度:以顶点v为弧尾的弧的数目；假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。设有6个结点的无向图，该图至少应有_____条边才能确保是一个连通图。在一个无向图中，所有顶点度数之和等于图的边数的_______倍。具有N个顶点的有向图最多有_____条边。ABCDEF有向图的邻接矩阵为非对称矩阵typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义VertexType//顶点信息vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;0A141B0452C353D254E015F123有向图的邻接表typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];三、有向图的十字链表存储表示结构的建立和销毁图的遍历V(连通网的)最小生成树MST(minimumspanningtree)构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。a在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。Prim算法过程a具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。aKruskal算法过程普里姆算法贪心准则下面看一个例子：Agri-NetDescriptionFarmerJohnhasbeenelectedmayorofhistown!Oneofhiscampaignpromiseswastobringinternetconnectivitytoallfarmsinthearea.Heneedsyourhelp,ofcourse.FarmerJohnorderedahighspeedconnectionforhisfarmandisgoingtosharehisconnectivitywiththeotherfarmers.Tominimizecost,hewantstolaytheminimumamountofopticalfibertoconnecthisfarmtoalltheotherfarms.Givenalistofhowmuchfiberittakestoconnecteachpairoffarms,youmustfindtheminimumamountoffiberneededtoconnectthemalltogether.Eachfarmmustconnecttosomeotherfarmsuchthatapacketcanflowfromanyonefarmtoanyotherfarm.Thedistancebetweenanytwofarmswillnotexc