国家电网考试备考计算机之数据结构与算法(14)

　　重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

　　十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

　　而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

　　这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。

　　二、图的遍历

　　图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。

　　对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。

　　2.1 深度优先遍历

　　深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。

　　它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

　　我们用邻接矩阵的方式，则代码如下所示。

　　——推荐阅读——

　　——推荐阅读——

招考公告——新疆社会招聘考试公告

　　试题资料——2022新疆社会工作相关考题

　　考试技巧——新疆社会工作笔试备考技巧

　　社会工作备考——新疆社区招聘考试《公基+社区知识+综合写作》乐享班

　　社会工作报考——新疆社会工作者报考条件

　以上为本文的全部内容，由新疆公务员考试网提供，希望对考生有所帮助！更多新疆公务员招考信息，请加新疆公务员考试交流群，及关注新疆公务员考试招考资讯/新疆人事考试网。