1.8.非线性表之图

  1. 图(graph): 由顶点(V集-vertex)和连接顶点的边(E集-edge)构成的离散结构，即：G = (V,E)。
  2. 顶点可以具有零个或多个相邻缘故，两个结点之间的连接为边。
  3. 详情：blog ==> https://blog.csdn.net/zhaozigu123/article/details/79283616
  5. 图的相关概念：
  6. 1、顶点
  7. 2、边
  8. 3、路径：依次遍历顶点序列之间的边所形成的轨迹。注意，依次就意味着有序，先1后2和先2后1不一样
  9. 4、图的分类
  11. 图的分类：
  12. 1、无向图，边(v,e)对称,当任意两个顶点间都有边，则称为无向完全图
  13. 2、有向图，存在顶点的入度(in-degree)和出度(out-degree)
  14. 3、无权图，加了权重概念
  15. 4、加权图，又称为网(network)
  16. 5、无环图
  17. 6、有向无环图
  19. 图的两个重要关系：
  20. 1、邻接(adjacency)：邻接是两个顶点之间的一种关系。
  21. 2、关联(incidence)：关联是边和顶点之间的关系。
  22. 图的遍历方法：
  23. 详情：cnblogs ==> https://www.cnblogs.com/lisen10/p/10872253.html
  24. 1、深度优先搜索遍历（DFS）: 是一个递归的过程
  25. 从初始访问结点除法，初始访问结点可能有多个邻接结点，再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。
  26. 1-1、首先访问顶点i，并将其访问标记置为访问过，即visited[i] =1；
  27.          1-2、然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；
  28.          1-3、若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。
  29. 2、广度优先搜索遍历（BFS）: 借助队列先进先出的特点以保持访问过的结点的顺序，之后按照这个顺序来访问这些结点的邻接结点。
  30. 2-1、首先访问顶点i，并将其访问标志置为已被访问，即visited[i]=1；
  31.         2-2、接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt；
  32.         2-3、然后再按顺序访问与W1，W2，…，Wt有边相连又未曾访问过的顶点；
  33.         2-4、依此类推，直到图中所有顶点都被访问完为止 。