图论

一.什么是图？

1.图：表示“多对多”的关系

        包含一组顶点V（Vertex）

       一组边E（Edge），（边是顶点对）

2.图的分类

    有向图 无向图 网络（带权值的图）

二.图的表示

1.邻接矩阵

   

    直接连通表示1，没有直接连通表示0

    我们可以发现，对于无向图的存储，邻接矩阵是对称的，这样相当于有一般的存储空间是被浪费的，所以我们可以只存一般的元素（下三角或上三角）

2.邻接表

三.图的遍历

1.深度优先搜索（DFS）

遍历策略是：首先访问出发点V，然后访问一个与V邻接且未被访问过的顶点W，再从W开始进行深度优先搜索，当某个点的所有邻接点都被访问过，则开始回退到尚有邻接点未曾被访问过的顶点u，并从u开始进行深度优先搜索，直到所有顶点都被访问到

    若有N个顶点，E条边，时间复杂度是

        （1）用邻接表存储图，有O（N+E）

        （2）用邻接矩阵存储图，有O（N的平方）

2.广度优先搜索（BFS）

和树的层序遍历算法类似，以顶点V为起始点，由近至远，依次访问和V有相同路径且路径长度为1，2..的顶点

    若有N个顶点,E条边，时间复杂度是

        （1）用邻接表存储，有O（N+E）

        （2）用邻接矩阵存储，有O（N的平方）

四.图不连通怎么办？

1.对于无向图

连通图：图中任意两点均连通

连通分量：无向图的极大连通子图

2.对于有向图

强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的

强连通图：图中任意两点均强连通

强连通分量：有向图的极大强连通子图

弱连通图：去掉方向后是连通图