北理工大数据结构作业4

《北理工大数据结构作业4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用标准第七章作业1、已知有向图，请给出该图的（1）每个顶点的入/出度；顶点入度出度130222312413521623（2）邻接矩阵；000000100100010001001011100000110010（3）邻接表；∧11∧1422∧2633∧35644155精彩文档实用标准∧12566（1）逆邻接表。∧25611∧3622∧433∧244∧4655∧34661524632、请对下列无向带权图进行操作：（1）写出它的邻接矩阵，并按普里姆算法求最小生成树；abcdfgeh43555559476623邻接矩

2、阵：精彩文档实用标准abcdefgha∞43∞∞∞∞∞b4∞559∞∞∞c35∞5∞∞∞5d∞55∞7654e∞9∞7∞3∞∞f∞∞∞63∞2∞g∞∞∞5∞2∞6h∞∞54∞∞6∞普里姆算法求最小生成树：aac3abc43abcd435abcdh4354精彩文档实用标准abcdgh43554abcdfgh435542abcdfgeh4355423（1）写出它的邻接表，并按克鲁斯卡尔算法求最小生成树；邻接表：∧231a∧13452b∧12483c∧2356784d精彩文档实用标准∧2465e∧4576f∧468

3、7g∧3478habcdfgeh43555559476623克鲁斯卡尔算法求最小生成树：abcdfgeh2abcdfgeh23精彩文档实用标准abcdfgeh323abcdfgeh4323abcdfgeh43423abcdfgeh435423精彩文档实用标准abcdfgeh43554231、请设计算法，由依次输入的顶点数目、弧数目、各顶点的信息和各条弧的信息建立有向图的邻接表。#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode

4、*nextarc;InfoType*info;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;StatusCreateAdjList(ALGraph&G){inti,j,k;ArcNodep;VertexTypev1,v2;InfoTypex;精彩文档

5、实用标准scanf(&G.vexnum,&G.arcnum)；//输入顶点数、边数for(i=0;i

6、malloc(sizeof(ArcNode))p->adjvex=j;p->info=x;p->nextarc=G.vertices[i].firstarc;//将p逆向插入链表G.vertices[i]G.vertices[i].firstarc=p;}returnOK;}//CreateAdjList精彩文档