数据结构——图、极大小连通子图、图的存储结构、图的遍历
图的基本概念:
极大连通子图就是连通分量。
极大连通子图与连通分量在无向图(undirected graph)这个前提下是等同的概念。
极小连通子图: 减去任何一条边就不再连通。
不管树还是二叉树:n个节点,n-1条边。
有n-1条边的连通图,一定是生成树。
连通图边数一定大于n-1条。去掉一些边,剩下n-1条边,而且是连通的,那就是连通图的生成树。
数据结构笔记—极大连通子图(连通分量) 极小连通子图与生成树、生成森林
https://blog.csdn.net/ITcainiao_/article/details/102847833
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
图的存储结构:
1、邻接矩阵
2、邻接表:
(对于有向图,只能算每个节点的出度,不方便算入度)
(对于无向图,重复存储边)
3、十字链表:有向图的链式存储,每个节点的出入都能表示。
4、邻接多重表:无向图的链式存储,不需要重复存储。
网:在图的基础上加上边的权值。
上面 因为权值可能为0
对于头结点,用一维数组的表示方法。后面表结点用链式存储,存储弧(边)的信息。
有向图的逆邻接表:以头节点为头的单链表。
之前的是以头节点为尾的单链表。
一个以头结点为头的单链表,一个以这个节点为尾的单链表。
无向图的邻接表重复存储信息。
邻接多重表:不需要重复存储。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
图的遍历:
找V1的所有没有被访问过的邻接点v2、v3。
再找v2和v3的所有没有被访问过的邻接点4 5 6 7
再依次往下走。。。。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
7.4图的连通性问题:
Kruskal算法,找不是同一个集合的连线。
上图,右边为左边的化简形式。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
有向无环图的一个有用的操作就是拓扑排序,不是唯一的。
拓扑排序可以用来判断一个有向图是否存在回路。即判断是否为有向无环图。
上面一页没有细说。
下面最短路径也没有特别明白。