深度优先搜索属于图算法的一种,是一个针对图和树的遍历算法,英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_SIZE 100
int graph[MAX_SIZE][MAX_SIZE];
bool visted[MAX_SIZE];
void dfs(int s, int n){//递归实现
cout << s << " ";
visted[s] = true;
for(int i = 1; i <= n; i++){
if((graph[s][i] != 0) && (!visted[i]))
dfs(i, n);
}
}
int main(){
int n, m, s;
cin >> n >> m >> s;
for(int i = 0; i < MAX_SIZE; i++){//矩阵初始化
for(int j = 0; j < MAX_SIZE; j++)
graph[i][j] = 0;
}
for(int i = 0; i < m; i++){//更新顶点间关系
int x = rand() % n;
int y = rand() % n;
while(x == 0 || y == 0){//为了便于理解,二维矩阵下标0废弃
x = rand() % n;
y = rand() % n;
}
graph[x][y] = 1;
}
dfs(s, n);
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_SIZE 100
bool visted[MAX_SIZE];
typedef struct Enode{
int index;
Enode *next;
}*Edge;
struct Vnode{
int data;
Enode *next;
};
void init_v_node(Vnode *apex, int n){
for(int i = 0; i <= n; i++){
apex[i].data = 0;
apex[i].next = NULL;
}
}
void create_list(Vnode *apex, int m, int n){
for(int i = 0; i < m; i++){//更新图的连通情况
int x = rand() % n, y = rand() % n;
while(x == 0 || y == 0){
x = rand() % n;
y = rand() % n;
}
apex[x].data = x;
Edge t = new Enode;
t->index = y;
t->next = apex[x].next;
apex[x].next = t;
}
}
void dfs(Vnode *apex, int s){
cout << s << " ";
visted[s] = true;
Edge p = apex[s].next;
while(p != NULL){
int t = p->index;
if(!visted[t])
dfs(apex, t);
p = p->next;
}
}
int main(){
int n, m;
cin >> n >> m;
Vnode apex[n+1];//顺序表存储顶点
init_v_node(apex, n);
create_list(apex, m, n);
dfs(apex, 1);
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- esig.cn 版权所有 湘ICP备2023023988号-3
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务