图

图的定义

图也是一种非线性结构，图中任意2个顶点之间都有可能有直接的关系。

flowchart TB 1((1)) 2((2)) 3((3)) 4((4)) 5((5)) 1 --- 2 1 --- 5 2 --- 3 3 --- 4 4 --- 5 4 --- 1

有向边和无向边：带箭头的单通道为有相边，不带箭头双通道为无向边。
无向图：图中任意顶点之间均为无向边
有向图：图中任意顶点之间均为有向边
完全图：
1. 无向完全图中两两顶点之间均有连线，n个顶点的完全无向图有n*(n-1)/2条边
2. 有向完全图中两两顶点之间均有连线，n个顶点的完全有向图有n*(n-1)条边
度，出度和入度：进出某个顶点的边的数目。进入该顶点的边数称为入度,从该顶点出去的边数称为出度, 在无向图中不分入度和出度，在有向图中顶点的度为出度和入度之和
路径：存在一条通路，可以从一个顶点到达另外一个顶点，有向图的路径是有方向的
连通图和连通分量：在无向图中，任意两个顶点之间都是有路径连通的称为连通图，无向图的极大连通子图称为其连通分量
强连通图和强连通分量：在有向图中，任意两个顶点之间都相互存在路径称为强连通图，有向图的极大连通子图称为其强连通分量
生成树：一个连通图的生成树就是该图的连通性不变，单没有环路的子图。一个有n个顶点的生成树有且仅有n-1条边
网：边带有权值的图称为网

图的存储主要有两种，邻接矩阵和邻接表

邻接矩阵：n个顶点的图可以用n*n的邻接矩阵来表示，如果顶点i到顶点j存在边，则矩阵元素A[i][j]的位置为1，否则为0，有向图中矩阵中节点对因横向之和是该图的出度，纵向之和是该图的入度
邻接表：是一种链式存储结构，用一个一维数组存储所有的顶点，对数组中的每个顶点生成一个链表，链表中每个顶点(表节点)，包括顶点号，顶点信息(如边的权值)以及指向下一个顶点(出度)的指针

从图的任意顶点出发，对图中所有顶点仅访问一次，分为深度优先搜索和广度优先搜索

深度优先搜索：类似于树的先根遍历
1. 访问一个顶点 V
2. 一次性搜索顶点 V 的所有邻接顶点
3. 若邻接顶点未被访问，则深度优先搜索邻接顶点，若已被访问，则跳到顶点 V 的下一个邻接顶点
广度优先搜索：类似于树的层次遍历，深度越小越优先被访问
1. 访问一个顶点 V
2. 依次访问顶点 V 所有未被访问的邻接顶点
3. 分别访问这些邻接点未被访问的所有邻接点

两种优先搜索的时间复杂度：使用邻接矩阵存储均为O(n^2), 使用邻接表存储均为O(n+e),n为顶点个数，e为边的个数