02331数据结构-06图

《02331数据结构-06图》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第六章图基础知识和算法的有关概念图，顶点，弧，弧头，弧尾;有向图（顶点集+弧集），0

2、点分成两组，一组有n-1个顶点，另一组只有1个顶点。首先在第一组中添加边，直到n-1个顶点构成企连通子图，共（n-l）（n-2）/2条边，此后若再在阁屮任意添加一条边将必定连通两组顶点，从而构成连通阁。思考：对有向图有何结论。2.图的存储结构（1）图的存储结构常见图的存储结构有：邻接矩阵，邻接表，逆邻接表，十字链表，邻接多重表。邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。例：画出图的邻接矩阵、邻接表、逆邻接表和十字链表。（2）邻接矩阵简言之，“数组（顶点）+二维数组（弧）+个数”、constintMAX_VERTEX=最大顶点个数；typede

3、fstructGraph{//图VertexTypevexs[MAX_VERTEX];//顶点向量ArcTypearcs[MAXVERTEX][MAXVERTEX];//邻接矩阵intvcxnum,arcnum;//顶点和弧的个数}Graph;图：有边（弧）为1;否则为0。网：有边（弧）为权值；否则为oo。存储空间个数为n2,与边的数目无关。无向图的邻接矩阵是对称的。A01100B00110C00010D10000E10010不准确的说法，只为便于理解和记忆，不驳在正式场☆引用。（3）邻接表简言之，“数组（弧尾顶点）+链表（邻接点）+个数”2。typedefstru

4、ctArcNode{//弧结点intadjvex;structArcNode*ncxtarc;//邻接点//下一个邻接点}ArcNode;typedefstructVexNode{//顶点结点VertexTypeArcNode*firstarc;}VexNode;data;//顶点信息//第一个邻接点constintMAX_VERTEX=最大顶点个数;typedefstructGraph{//图VexNodevcxs[MAX_VERTEX];intvexnum，arenum;}Graph;//顶点向釐//顶点和弧的个数边（弧）多则需要存储空间多。0A->12八/B-

5、>23A2C->3A3D0A4E->03A（4）逆邻接表简言之，“数组（弧头顶点）+链表（逆邻结点）+个数”3。类型定义类似邻接表。0A->31B02C03D->1EA4A八1A->2♦4八（5）十字链表简言之，“数组（顶点）+弧结点（含头和尾）+个数”4。边可以看作两条弧。typedefstructArcNode{//弧结点intvtail,vhead;//弧尾和弧头顶点编号structArcNode*nexttail,*nexthead;//指叫同弧尾和同弧头的弧结点}ArcNode;2不准确的说法，只为便于理解和记忆，不嬰在正式场合引用。3不准确的说法，只为便

6、于理解和记忆，不嬰在正式场合引用。4不准确的说法，只为便于理解和记忆，不姐在正式场介引用。技巧：把弧结点按行排整齐，然后画链表。(6)邻接多重表简言之，“数组(顶点)+边结点”5。typedefstructEdgeNode{//边结点intvexi,vexj;structEdgeNode*nexti,*nextj;}EdgeNode;typedefstructVexNode{//顶点结点VertexTypeEdgeNode*firstedge;}VexNode;constintMAX_VERTEX=最大顶点个数;typedefstructGraph{//图VexNo

7、devexs[MAX_VERTEX];intvexnum,edgenum;}Graph;只适合存储无向图，不能存储有向图。data;//顶点信息//指叫第一条入弧和第一条出弧//顶点向釐//顶点和弧的个数0A/B2C3D>30AL>01A―>02八♦v>12A—>13A」士>23AEA—>40A>43八八同弧尾的弧组成链表，同弧失的弧组成链表。//边的两个顶点//两个顶点所依附的下一条边data;//顶点信息//指向第一条边//顶点向量//顶点和边的个数typedefstructVexNode{//顶点错点VertexTypeArcNode*firstin，*f