图的基本概念
- 定义：
树是N（N≥0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。
* 图G由顶点集V和边集E组成，记为G=(V，E)
* V(G)表示图G中顶点的有限非空集。用|V|表示图G中顶点的个数，也称为图G的阶
* E(G)表示图G中顶点之间的关系（边）集合。用|E|表示图G中边的条数。
分类
有向图
有向边（弧）的有限集合
- 弧是顶点的有序对
- <v,w>
- v是弧尾，w是弧头
- v邻接到w或w邻接自v
无向图
无向边的有限集合
- 边是顶点的无序对
- （v,w）
- （v,w）=(w,v)
- w，v互为邻接点
简单图
- 1.不存在顶点到自身的边
- 2.同一条边不重复出现
多重图
- 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联
完全图
无向完全图
- 如果任意两个顶点之间都存在边
有向完全图
- 如果任意两个顶点之间都存在方向相反的两条弧
- 子图
- 连通图：图中任意两个顶点都是连通的
连通分量：无向图中的极大连通子图
连通
- 顶点A到顶点B有路径
极大
- 1.顶点足够多
- 2.极大连通子图包含这些依附这些顶点的所有边
- 结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
- 概要: 找连通分量的方法：
从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的顶点和边直到所有相连的顶点都加入该子图
- 强连通：顶点V到顶点W和顶点W到顶点V都有路径
- 强连通图：图中任一对顶点都是强连通的
连通图的生成树：包含图中全部n个顶点，但是只有n-1条边的极小连通子图
- 结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。
度：以该顶点为一个端点的边数目
- 无向图中顶点V的度是指依附于该顶点的边的条数，记为TD(v)
有向图中顶点V的度分为出度和入度
- 入度（ID）是以顶点v为终点的有向边的数目
- 出度（OD）是以顶点V为起点的有向边的数目
- 简单路径和简单回路：顶点不重复出现的路径称为简单路径。对于回路，除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路
- 权和网：图中每条边考研赋予一定意义的数值，这个数值叫做这条边的权，有权值得图称为带权图，也叫做网
- 路径和路径长度：顶点p到q之间的路径是指顶点序列怕保存的，p,a,b,c,d,……q。路径上边的数目就是路径长度
- 回路（环）：第一个和最后一个顶点相同的路径称为回路或者环
- 距离：从顶点u到v的最短路径长度。不存在路径则为无穷
图的存储结构
- 邻接矩阵（顺序存储）
邻接表（链式存储）
- 十字链表（有向图）
- 邻接多重表（无向图）
图的遍历
深度优先遍历
深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法
- 空间复杂度：由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)
- 时间复杂度：1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度为O(|V|+|E|)
2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|2)
广度优先遍历
广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法
- 空间复杂度：BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。
- 时间复杂度：
1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂度为O(|V|+|E|)
2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|2)
