图/树的搜索/存储/拓扑排序
发布时间 2023-08-02 19:19:56作者: MoiLip
-
深度优先搜索
- 一条路走到黑
- 回溯/剪枝
- 每一个dfs都对应一个搜索树
- 解决全排列,搜索所有可能解
- 宽度优先搜索
搜索方式 |
数据结构 |
空间 |
特点 |
DFS |
stack |
O(h) |
不具有最短性 |
BFS |
queue |
O(2^h) |
最短路 |
-
树与图的存储
-
有向图/树
- 每条边建一次
add(a, b);
- 存储:
-
邻接矩阵:
-
邻接表:
- 单链表数组,有几个点就开几个单链表,每个单链表存储该点可以到的点
-
代码:
//h[i]存储以节点i为起点的单链表,单链表中的节点存的是节点i能够到达的所有节点
//以节点的编号代指结点,但是节点有两类,一类是图中的节点,一类是链表中的节点
//idx分配单链表中的节点的编号,而不是图中节点的编号,注意区分
//h[i]中的i是图中节点的编号,存的是单链表节点编号
//e[i]中的i是单链表中节点的编号,存的是图中节点的编号,e[i]表示i节点存储的图中的节点
//ne[i]中的i是单链表中节点的编号,存的是单链表点的编号,ne[i]表示i节点的下一个链表节点
//链表节点下标以1开始,0表示空节点
int h[N], e[N], ne[N], idx = 1;
void add(int a, int b){//插入节点a指向b的一条边
e[idx] = b;//单链表节点的值就是图中节点
ne[idx] = h[a];
h[a] = idx;
idx ++ ;
}
-
无向图/树
- 每条边建两次
add(a, b);
add(b, a);
-
树与图的深度优先遍历
-
树与图的宽度优先遍历
-
拓扑排序
- 拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件:
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
- 只要图中有环,那么该图不存在拓扑序列
- 拓扑序不唯一
- 代码:
//将所有入度为0的节点i优先入队
//删除以节点i为起点j为终点的所有边,同时更新j的入度
//再次将所有入度为0的节点j入队
//建图步骤省略
int q[N], hh, tt = -1;//队列
int d[N];//存储每个节点的入度
//初始化入度与图
cin >> a >> b;
add(a, b);
d[b] ++ ;
void topsort(){
for(int i = 1; i <= n; ++ i)//遍历所有节点
if(!d[i]) q[ ++ tt] = i;//将入度为0的节点优先入队
//BFS
while(hh <= tt){ //队列非空
int x = q[hh ++ ]; //队首出队
for(int i = h[x]; i; i = ne[i]){
int j = e[i];//遍历以x为起点的所有边的终点
d[j] -- ; //删边,更新入度
if(!d[j]) q[ ++ tt] = j; //将所有入度为0的点入队
}
}
if(tt == n - 1) //所有点都在q数组时,存在拓扑序
for(int i = 0; i < n; ++ i) cout << q[i];
else cout << -1;//不存在拓扑序
}