資料結構
網路
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+ 瀏覽次數
廣告