北航数据结构与程序设计图部分选填题

一、
抓两个关键信息：无向图，邻接表。无向图中，边（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个顶点才可以。

---

十六、
拓扑序列生成步骤：

1. 在有向图中选一个没有前驱的顶点并输出
2. 在图中删除该顶点和所有以它为尾的弧
3. 重复上述步骤，直至全部顶点均已输出，或当图中不存在无前驱的顶点为止。

我们发现只有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输出。