概念
1:简单图,不存在重边和自环(有向图必须是两条同一方向的边)
2:简单路径:路径中不包含重复的点和边
2;完全图:每两个顶点之间都有一条边(无向图)共n(n-1)/2个边,有向完全图每两个顶点之间都有两个有向边一共n(n-1)
图的储存
1:邻接矩阵 无向有向 空间复杂度O(n2) 不能存重边 (只有这个存稠密图)
2: 邻接表 无向有向 O(n+m) 可存重边
3: 邻接多重表: 只适用于无向图不容易找反向边,所以研究出来这个 O(n+m),直接在储存的时候两个点存到一个节点
可以存重边
node
{
int val1; n * next1;
int val2; n * next2;
}head[];
4:十字链表:有向 O(n+m) 对邻接矩阵进行优化 不能存重边 ---------------复习
5:三元组表:无向有向 bell和kruscal , O(m) 可以存重边
搜索
dfs序就是指一棵树被dfs时所经过的节点的顺序,在回溯位置输出就是拓扑排序的逆序(原因)
拓扑排序
dfs实现:因为一个点要回溯就代表,他的所有节点已经遍历过了,就是在序列里面他只能指向他前面的节点,所以是拓扑排序的逆序
存在拓扑排序等价于无环 -----------------------------------重要
dfs时一定要遍历一遍每一个点,以防图不联通
dfs判断环时 st=0表示没遍历,st=1表示正在遍历,st=2表示遍历完成