图——常考题型、存储结构、遍历、应用

  • 图的基本性质(常考题型)

      1. 在一个图中,所有顶点的度数之和等于边数的 2
      2. 广度优先遍历通常借助队列来实现算法,深度优先遍历通常借助来实现算法。
      3. 广度优先遍历类似于二叉树的层次遍历深度优先遍历类似于二叉树的先序遍历
      4. n个顶点的强连通图至少有n条边,形状是树状
      5. n个顶点的连通图邻接矩阵表示时,该矩阵至少有2(n-1)个非零元素
    1. 有向图

      1. 具有 n 个顶点的有向图最多有 n(n-1) 条边。
      2. 拓扑排序可以判断出一个有向图是否有
    2. 无向图

      1. 具有 n 个顶点的无向图最多有 n(n-1)/2 条边。

      2. 设有 n 个结点的无向图,该图至少应有 n-1 条边,就能确保是一个连通图

      3. G是一个非连通无向图,共有s条边,求至少有多少个顶点?

        ​ 利用点边公式求出n后 结果+1(构成非连通无向图

      4. 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点,则该图一定是连通图

  • 图的存储结构

    常用的存储结构有两种:邻接矩阵法、邻接表法。

    邻接矩阵

    1. 特点
    • 无向图的邻接矩阵一定是个对称矩阵。
    • 有向图的邻接矩阵是无规律矩阵。

    邻接表

    1. 特点
    • 图的邻接表不唯一。
    • 对于稀疏图,邻接表能极大节省存储空间。
    • 在有向图的邻接表表示中,求一个顶点的出度只需计算结点个数。
    • n个结点,e条边的无向图邻接表中,有n个头结点和2e个表结点。
  • 图的遍历

    图的遍历算法主要有两种:广度优先搜索和深度优先搜索。

    广度优先

    类似二叉树当中的层次遍历,注意按照顺序依次遍历。

    深度优先

    类似二叉树当中的先序遍历,可以理解成一头倔牛,一直深入搜索到最底层,没路了就原路返回接着找之前的另一个出口倔出来,直到所有顶点均被访问过为止。

  • 图的应用

    1. 最小生成树

2.最短路径

3.关键路径(AOE)

推荐这些技术文章:

数据结构-图的遍历——BFS广度优先搜索

题目链接:https://www.dotcpp.com/oj/problem1703.html?sid=7509237&lang=1#editor
板子题,需要注意的是利用邻接矩阵存图,但是这样就变成了纯bfs模板,只要判断是否是走过并且这个点是否能走就可以了,
而对于图来说,尤其是利用邻接矩阵存图,0代表的是这条边不是图的边,1代表这条边是图的边,
而对于网图来讲,Gij代表的是这个图...

广度优先搜索遍历(无向图)

全局变量

int visited[MAXVEX] = { 0 };/*访问标志数组*/

BFSTraverse函数

1 /***************************************************
2 * Name: BFSTraverse
3 * Called By: main
4 * Parameter: G 邻接表
5 * Descriptio...

js—深度优先遍历(DFS)和广度优先遍历(BFS)

<div id="root">
<ul>
<li>
<a href="">
<img src="" alt="">
</a>
</li>
<li>
...

文章标题:图——常考题型、存储结构、遍历、应用
文章链接:https://www.dianjilingqu.com/4081.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>