1.dfs深度优先搜索算法

算法导论中是通过三种标记颜色来介绍dfs的,white代表还没被搜过,grey代表被搜了一些,还没结束,white表示已经搜索完成的状态。

c/c++复现dfs代码

#include<iostream>#include<vector>#include<stdio.h>#include<set>#define WHITE -1#define GREY 0#define BLACK 1using namespace std;struct vertex{int color;int parent;int final_time;int first_time;};vector<int> v[101];//存储边的邻接表vertex points[101];set<int> s;//记录所有顶点编号int time = 0;void dfs_visit(int u,vertex& p){cout<<u<<endl;//最终dfs遍历输出顺序time++;p.first_time = time;p.color = GREY;for(int i=0;i<v[u].size();i++){int te = v[u][i];if(points[te].color == WHITE){points[te].parent = u;dfs_visit(te,points[te]);}}p.color = BLACK;time = time + 1;p.final_time = time;}void dfs(){set<int>::iterator it = s.begin();for(it=s.begin();it!=s.end();it++){points[*it].color = WHITE;points[*it].parent = -1;}for(it=s.begin();it!=s.end();it++){int t = *it;if(points[t].color == WHITE){dfs_visit(t,points[t]);}}}//author：GUET_diadestinyint main(){int head,tail,n;//freopen("next.txt","r",stdin);cin>>n;//n表示边数while(n--){cin>>head>>tail;v[head].push_back(tail);s.insert(head);s.insert(tail);}dfs();for(set<int>::iterator it=s.begin();it!=s.end();it++){int t = *it;cout<<points[t].color<<" "<<t<<" "<<points[t].parent<<" "<<points[t].first_time<<" "<<points[t].final_time<<endl;}return 0;}//输入有向图数据,(i,j)表示存在从i指向到j的边://7//4 3//4 6//3 6//3 2//6 5//6 1//1 2

2.基于dfs的拓扑排序算法

c/c++ 复现基于dfs的拓扑排序算法

/**dfs(G):for each vertex u in V:u.c <- whiteu.p <- NILtime <- 0for each vertex u in V:if u.c == while thendfs-visit(G,u)DFS-visit(G,u):time <- time + 1u.d <- timeu.c <- grayfor each edge(u,v) in E:if v.c == white thenv.p <-udfs-visit(G,v)u.c <- blacktime <- time + 1u.f <- timetopological-sort(G):call DFS(G) to compute finishing times v.f for each vertex vas each vertex is finished,insert it onto the front of a linked listreturn the linked list of vertexs**/#include<iostream>#include<vector>#include<stdio.h>#include<set>#include <stdlib.h>#define WHITE -1#define GREY 0#define BLACK 1using namespace std;struct Node{int data;struct Node * next;};struct vertex{int color;int parent;int final_time;int first_time;};vector<int> v[101];//存储边的邻接表vertex points[101];set<int> s;//记录所有顶点编号int time = 0;Node* headlink = NULL;//as each vetex is finished, insert it onto the front of a linked list//头插法//author:GUET_diadestinyvoid head_insert(int t){Node * tp = (Node*)malloc(sizeof(Node));tp->data = t;tp->next = headlink->next;headlink->next = tp;}void print_link(){Node *ph = headlink->next;while(ph){cout<<ph->data<<" ";ph = ph->next;}cout<<endl;}void dfs_visit(int u,vertex& p){time++;p.first_time = time;p.color = GREY;for(int i=0;i<v[u].size();i++){int te = v[u][i];if(points[te].color == WHITE){points[te].parent = u;dfs_visit(te,points[te]);}}p.color = BLACK;time = time + 1;p.final_time = time;head_insert(u);}void dfs(){set<int>::iterator it = s.begin();for(it=s.begin();it!=s.end();it++){points[*it].color = WHITE;points[*it].parent = -1;}for(it=s.begin();it!=s.end();it++){int t = *it;if(points[t].color == WHITE){dfs_visit(t,points[t]);}}}int main(){int head,tail,n;headlink = (Node*)malloc(sizeof(Node));headlink->next = NULL;//freopen("next1.txt","r",stdin);cin>>n;//n表示边数while(n--){cin>>head>>tail;v[head].push_back(tail);s.insert(head);s.insert(tail);}dfs();for(set<int>::iterator it=s.begin();it!=s.end();it++){int t = *it;cout<<points[t].color<<" "<<t<<" "<<points[t].parent<<" "<<points[t].first_time<<" "<<points[t].final_time<<endl;}print_link(); //输出一个拓扑排序序列return 0;}//输入有向无环图测试数据(源于算法导论P355)//10//1 2//1 4//2 3//4 3//7 4//6 7//7 8//9 8//6 8//5 5

3. bfs宽度优先搜索算法

c/c++ 复现bfs宽度优先搜索算法

/**BFS(G,s):for each vertex u in V-{s}:u.color<-white,u.d<-oo,u.p<-NILs.color<-gray,s.d<-0,s.p<-NILQ <- emptyEnqueue (Q,s):while Q is !empty:u <- Dequeue(Q)for each (u,v) in E:if v.color == while:v.color <- grayv.d <- u.d + 1v.p <- uEnqueue(Q,v)u.color <- black当存储结构为链接表,BFS算法的时间复杂度(|V|+|E|)**/#include<iostream>#include<vector>#include<stdio.h>#include<set>#include<queue>#define WHITE -1#define GREY 0#define BLACK 1using namespace std;struct vertex{int color;int parent;int d;int val;};const int MAX = 0xffff;vector<int> vs[101];//存储边的邻接表vertex points[101];set<int> se;//记录所有顶点编号int time = 0;queue<vertex> que;void bfs(){for(set<int>::iterator it=se.begin();it!=se.end();it++){int t = *it;if(t == 1){points[t].color = GREY;points[t].parent = -1;points[t].d = 0;}else{points[t].color = WHITE;points[t].parent = -1;points[t].d = MAX;}points[t].val = t;}que.push(points[1]);while(!que.empty()){vertex tp = que.front();que.pop();for(int i=0;i<vs[tp.val].size();i++){int v = vs[tp.val][i];if(points[v].color == WHITE){points[v].color = GREY;points[v].d = points[tp.val].d+1;points[v].parent = tp.val;que.push(points[v]);}}points[tp.val].color = BLACK;}}int main(){int head,tail,n;//freopen("next.txt","r",stdin);cin>>n;//n表示边数while(n--){cin>>head>>tail;vs[head].push_back(tail);vs[tail].push_back(head);se.insert(head);se.insert(tail);}bfs();for(set<int>::iterator it=se.begin();it!=se.end();it++){int t = *it;cout<<points[t].color<<" "<<t<<" "<<points[t].parent<<endl;}return 0;}//输入有向图数据,(i,j)表示存在从i指向到j的边://7//4 3//4 6//3 6//3 2//6 5//6 1//1 2

如果觉得《算法导论：dfs深度优先搜索算法及基于dfs的拓扑排序以及宽度优先搜索算法bfs》对你有帮助，请点赞、收藏，并留下你的观点哦！