数据结构
网络
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
更新日期： 16-6-2020
3K+ 浏览次数
广告