前言：
唉！昨天学了一天的并查集，但是觉得自己并没有搞的特别明白，就算写笔记意义也不大，先跳过了，过一段时间之后再来学习并查集，但是这个图还算是可以。
介绍：
图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E)；
G表示一个图，V是顶点集，E是边集；
顶点集V有穷且非空；
任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的
image.png
应用场景：
image.pngimage.png
社交网络，地图等。。。

图的种类

有向图

有向图的边是有明确方向的
image.png
有向无环图（Directed Acyclic Graph，简称 DAG） 如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图

image.png

出度、入度

出度、入度适用于有向图
出度（Out-degree） 一个顶点的出度为 x，是指有 x 条边以该顶点为起点 顶点11的出度是3
入度（In-degree） 一个顶点的入度为 x，是指有 x 条边以该顶点为终点 顶点11的入度是2
image.png

无向图

无向图的边是无方向的
image.png
效果类似于下面的有向图
image.png

混合图

image.png

简单图、多重图

平行边
在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边 在有向图中，关联一对顶点的有向边如果多于1条，并且它们的的方向相同，则称这些边为平行边
多重图（Multigraph） 有平行边或者有自环的图； 简单图（Simple Graph） 既没有平行边也不没有自环的图
image.png

无向完全图

无向完全图的任意两个顶点之间都存在边
n 个顶点的无向完全图有 n(n − 1)/2 条边 n − 1 + n − 2 + n − 3 + ⋯ + 3 + 2 + 1
image.png

有向完全图　　

有向完全图的任意两个顶点之间都存在方向相反的两条边
n 个顶点的有向完全图有 n(n − 1) 条边
image.png
稠密图（Dense Graph）：边数接近于或等于完全图
稀疏图（Sparse Graph）：边数远远少于完全图

有权图

image.png

连通图

如果顶点 x 和 y 之间存在可相互抵达的路径（直接或间接的路径），则称 x 和 y 是连通的
如果无向图 G 中任意2个顶点都是连通的，则称G为连通图
image.png

连通分量

连通分量：无向图的极大连通子图
连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量
下面的无向图有3个连通分量
image.png

强连通图

如果有向图 G 中任意2个顶点都是连通的，则称G为强连通图 ,并不是说要直接相连,是相连就可以
image.png

强连通分量

有向图的极大强连通子图 强连通图只有一个强连通分量，即其自身；非强连通的有向图有多个强连通分量
image.png

图的实现

邻接矩阵

邻接矩阵的存储方式
一维数组存放顶点信息
二维数组存放边信息
image.png
邻接矩阵比较适合稠密图 不然会比较浪费内存

image.png

邻接表

image.png
image.png

遍历

图的遍历
从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次
图有2种常见的遍历方式（有向图、无向图都适用）
广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索
深度优先搜索（Depth First Search，DFS） 发明“深度优先搜索”算法的2位科学家在1986年共同获得计算机领域的最高奖：图灵奖

广度优先搜索

二叉树层序遍历就是一种广度优先搜索
image.png
image.png
image.png

深度优先搜索

二叉树前序遍历就是一种深度优先搜索
image.png
image.png
图的知识还有许多,因为都是理论,学的不是很透彻,等着下会做题的时候一起写