数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究图的深度优先搜索或 DFS
深度优先搜索 (DFS) 是一种图遍历算法。在这个算法中，指定了一个起始顶点，当找到相邻顶点时，它会首先移动到该相邻顶点，并尝试以相同的方式遍历。
它尽可能遍历整个深度，然后回溯到以前的顶点以找到新路径。
为了使用迭代方式实现 DFS，我们需要使用栈数据结构。如果我们想要以递归的方式进行，则不需要外部栈，它可以对递归调用使用内部栈。
输入：图的邻接矩阵。
A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0
输出：DFS 遍历：C F E B D A
算法
dfs(顶点，开始)
输入 - 所有顶点的列表和开始节点。
输出 - 遍历图中的所有节点。
Begin initially make the state to unvisited for all nodes push start into the stack while stack is not empty, do pop element from stack and set to u display the node u if u is not visited, then mark u as visited for all nodes i connected to u, do if ith vertex is unvisited, then push ith vertex into the stack mark ith vertex as visited done done End
示例
#include<iostream>
#include<stack>
using namespace std;
#define NODE 6
typedef struct node{
int val;
int state; //status
}node;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void dfs(node *vertex, node start){
node u;
stack<node> myStack;
for(int i = 0; i<NODE; i++){
vertex[i].state = 0;//not visited
}
myStack.push(start);
while(!myStack.empty()){
//pop and print node
u = myStack.top();
myStack.pop();
cout << char(u.val+'A') << " ";
if(u.state != 1){
//update vertex status to visited
u.state = 1;
vertex[u.val].state = 1;
for(int i = 0; i<NODE; i++){
if(graph[i][u.val]){
if(vertex[i].state == 0){
myStack.push(vertex[i]);
vertex[i].state = 1;
}
}
}
}
}
}
int main(){
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++){
vertices[i].val = i;
}
s = 'C';//starting vertex C
start.val = s-'A';
cout << "DFS Traversal: ";
dfs(vertices, start);
cout << endl;
}输出
DFS Traversal: C F E B D A
更新于： 05-Aug-2019
908 次浏览
广告