本文主要是介绍北航数据结构与程序设计图部分选填题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、
抓两个关键信息：无向图，邻接表。无向图中，边（vi，vj）要在vi的链表中记录一次，再以（vj，vi）的形式在vj的链表中记录一次。
每个边都要记录两次，则邻接表中边数为2n。
二、
无向图、邻接矩阵。同上一题，同一条边，（vi，vj）和（vj，vi）都要记录一次。因此是对称矩阵。（注意不要和对角矩阵搞混）
三、
n个顶点的无向图，边数最多的时候成为完全图。即用排列组合的公式：n（n-1）/ 2 = 8*7/2=28
四、
同一条边（vi，vj）既要算在顶点vi的度数里，又要算在顶点vj的度数里，因此度数等于边数的两倍。
五、
先访问当前结点，然后按照编号大小依次访问与它直接连接的节点。
六、
无论是无向连通图还是有向连通图，最小生成树都不一定唯一。
七、
广度优先遍历类似于树的层序遍历，因此是用队列。基本思想是：“父节点进队——父节点出队——其子节点入队——直至栈空”
八、
这个要从代码的角度考虑，因为期末图不考编程题所以我们记住结论即可：
Prim算法的时间复杂度：O（n²），Kruskal算法的时间复杂度：O（eloge）。
九、
基本概念要记牢哦~
十、
有向图、邻接矩阵。对于有向图来说，第i列 的所有非0非无穷大的元素个数等于其入度。
对于无向图来说，第i行或第i列的所有非0非无穷大的元素个数等于其度数。
十一、
稀疏图选邻接表更节省空间。
十二、
蛮有意思，去掉任意一条边，都是生成树而且是最小生成树，一共有n条边，则有n个生成树。
十三、
①T={V1}，U={V2,V3,V4,V5,V6}，T中元素和U中元素的连线有9，10,16，最小边为9，因此v4加入T；
②T={V1,V4},U={V2,V3,V5,V6}，T和U连线中有2,10,16，最小边为2，V3加入T
③T={V1,V4,V3}，U={V2,V5,V6}，T和U中连线有16,11,14,18，最小边11，V2加入T
④T={V1,V4,V3,V2}，U={V5,V6}，T和U中连线有18,14，6,5，最小边5，V6加入T
⑤T={V1,V4,V3,V2,V6}，U={V5}，T和U中连线有1,6,14,18，最小边1，加入。
⑥至此T中包含了所有结点，因此最后一个加的边权值为1.
十四、
选1，选2，选5，选6不行，成环，选9，选10不行成环，选11，此时包含了所有顶点，因此最后一个为11.
十五、
注意注意：是非连通，最多28条。完全图顶点和边计算公式为n（n-1）/2，也是边数最多情况，但是，如果是8个顶点，28条边，就是完全图了，就连通了，所以至少有9个顶点才可以。
十六、
拓扑序列生成步骤：
- 在有向图中选一个没有前驱的顶点并输出
- 在图中删除该顶点和所有以它为尾的弧
- 重复上述步骤，直至全部顶点均已输出，或当图中不存在无前驱的顶点为止。
我们发现只有V3没有前驱，则先输出V3，则<v3,v1>、<v3,v4>删除。
然后V1没有前驱，则输出V1，<v1,v2>、<v1,v4>删除。
接下来V4没有前驱，输出V4，<v4,v5>删除
V5无前驱，V5输出，<v5,v2>,<v5,v6>删除
V2无前驱，V2输出，<V2,V6>删除
最后剩了一个节点V6，v6输出。
这篇关于北航数据结构与程序设计图部分选填题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
