首页 > 代码库 > 图算法（一）——基本图算法（BFS，DFS及其应用）（2）
图算法（一）——基本图算法（BFS，DFS及其应用）（2）
2）DFS
深度优先搜索总是对最近发现的节点v的出发边进行搜索，直到该节点的所有出发边都被发现
一旦节点v的所有出发边都被发现，搜索回溯到v的前驱结点进行
实现细节：时间戳
每一个结点有一个发现时间和完成时间
DFS后原图的前驱子图构成一个深度优先森林
1 #include<iostream> 2 using namespace std; 3 #define NIL -1 4 int g[1000][1000]; 5 int n; 6 struct Node 7 { 8 int color; 9 int d;10 int f;11 int pi;12 }t[1000];13 int time;14 15 void DFS();16 void DFS_VISIT(int u);17 18 void DFS()19 {20 for (int i=0;i<n;i++)21 {22 t[i].color = 0;23 t[i].pi = NIL;24 }25 time=1;26 for (int i=0;i<n;i++)27 {28 if (t[i].color == 0)29 DFS_VISIT(i);30 }31 }32 void DFS_VISIT(int u)33 {34 t[u].d = time++;35 t[u].color = 1; /*****/36 for (int v=0;v<n;v++)37 {38 if ((g[u][v] == 1)&&(t[v].color == 0))39 {40 t[v].pi = u;41 DFS_VISIT(v);42 }43 }44 t[u].f = time++;45 }46 /*47 int main()48 {49 while (cin>>n)50 {51 for (int i=0;i<n;i++)52 {53 for (int j=0;j<n;j++)54 {55 cin>>g[i][j];56 }57 }58 DFS();59 for (int i=0;i<n;i++)60 cout<<i<<" "<<t[i].d<<" "<<t[i].f<<" "<<endl;61 }62 return 0;63 }64 */
图算法（一）——基本图算法（BFS，DFS及其应用）（2）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。