数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究深度优先搜索（DFS）算法
深度优先搜索（DFS）是一种图遍历算法。在此算法中，给出一个起始顶点，当找到一个邻接顶点时，它首先移动到该邻接顶点，并尝试以相同的方式遍历。
它遍历整个深度，尽可能深入，之后它回溯到先前的顶点以找到新的路径。
要以迭代方式实现 DFS，我们需要使用堆栈数据结构。如果想以递归方式进行，则不需要外部堆栈，可以使用内部堆栈进行递归调用。
输入和输出
Input: The Adjacency matrix of a graph. 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 1 0 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0 Output: DFS Traversal: C F E B D A
算法
dfs(vertices, start)
输入：所有顶点的列表和起始节点。
输出：遍历图中的所有节点。
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
更新于：2020 年 6 月 16 日
3 千次浏览
广告