图的基础知识梳理

图的定义

图是由顶点集合和顶点之间的边组成的数学结构,图的阶是图中顶点的个数,下图是几种不同的图
有向图

无向图

零图

图的分类

图的分类是以边的不同来分为7类

有向图

有向图指图中每边都是有方向的边的图叫有向图

无向图

无向图指图中每一边都是没有方向的边的图叫无向图

完全图

完全图指图中每一个顶点都与剩下的每个结点相连，这样的图叫完全图

很美丽的图案呢！

稀疏图

稀疏图指图中边的数量少（边数远小于n(n-1)/2或小于nlog(n)(n为边数)）的图称为稀疏图

稠密图

稠密图与稀疏图相对，指的是边的数量多（几乎接近完全图）的图成为稠密图

平凡图

平凡图指图中的阶数为1的图是平凡图，阶数大于1的为非平凡图，阶数为0的是空图
平凡图

非平凡图

空图（没错要相信自己的眼睛）

零图

零图指只有顶点没有边的图叫零图

顶点的度

顶点的度的定义：一个顶点与其相连的边的条数叫做这个顶点的度

上图中顶点5的度为

孤立点

highlighter- code-theme-dark

孤立点：度为0的顶点如上图中的1

叶节点

highlighter- code-theme-dark

叶节点：度为1的顶点如上图中的4

偶点

highlighter- code-theme-dark

偶点：度为偶数的顶点如上图中的2

奇点

highlighter- code-theme-dark

奇点：度为奇数的顶点如上图中的6

图的路径

图的路径是指从一个顶点到另一个顶点所经过的顶点序列
一条路径中，顶点不重复出现的路径叫简单路径
除了起点和终点相同，其余不相同的称为回路或环

图的连通性

无向图

在无向图中，如果一个顶点u到另一个顶点v（u不等于v）存在路径，则称顶点u和顶点v是连通的
若图中任意两个顶点都是连通的，那么称该图为连通图

有向图

在有向图中，如果图中任意两个顶点u和v（u不等于v）存在路径（按其概念），那么称该图为强连通图
若将其转化为无向图后，图中任意两个顶点都是连通的，那么称该图为弱连通图

带权图

在上文讲的基础上，在边上加上有关边的数据（权值），形成带权图

图的储存

图的储存主要分为2种，邻接矩阵、邻接表

邻接矩阵

思路

邻接矩阵是用一个二维数组adj来存储i和j的关系
adj初始化为0

无向图

在无向图中如果i，j连通那么adj[i][j]=adj[j][i]=1，否则adj[i][j]=adj[j][i]=0

上图用邻接矩阵来存为：

下标	1	2	3	4	5
1	0	1	0	0	1
2	1	0	0	0	1
3	0	0	0	1	1
4	0	0	1	0	1
5	1	1	1	1	0

代码

highlighter- code-theme-dark Java

void join (int u,int v) {//u和v相通 adj[u][v] = 1; adj[v][u] = 1; }

有向图

在有向图中如果i指向j那么adj[i][j]=1，如果n指向i那么adj[j][i]=1，否则adj[i][j]=adj[j][i]=0

上图用邻接矩阵来存为：

下标	2	3	4	5
1	1	0	0	1
2	0	0	0	1
3	0	0	1	0
4	0	0	0	1
5	0	1	0	0

代码

highlighter- code-theme-dark Java

void join (int u,int v) {//从u指向v adj[u][v] = 1; }

时间、空间复杂度

查询是否存在某条边：O(1)
遍历一个点的所有出边：O(n)
遍历整张图：O(n^2)
空间复杂度：O(n^2)

优点

最显著的优点是可以 O(1) 查询一条边是否存在。

邻接表

思路

v1	2	5
v2	5	null
v3	4	null
v4	5	null
v5	3	null

代码

highlighter- code-theme-dark Java

struct num {//from 起点，to终点，val权值，next就是指向下一个边 int from,to,val,next; }; num _v[maxm]; int head[maxn],cnt;// head数组和cnt就是记录与一个头结点相连的结点的个数 void add (int u,int v,int w) { num e; e.from = u; e.to = v; e.val = w; e.to = head[u]; _v[cnt] = e; head[u] = cnt++; }