Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3fb8ecc

Browse files
committed
feat:added dfs algorithm
1 parent00c7ee0 commit3fb8ecc

File tree

3 files changed

+179
-0
lines changed

3 files changed

+179
-0
lines changed

‎src/data_structures/dfs_algorithm.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
#Depth-First Search (DFS) Algorithm
2+
3+
Depth-First Search (DFS) is a graph traversal algorithm that explores vertices and their edges by going as deep as possible before backtracking. It is used to visit all the vertices of a graph in a systematic manner.
4+
5+
##Algorithm Overview
6+
7+
1. Start from a source vertex.
8+
2. Visit the source vertex and mark it as visited.
9+
3. Explore an unvisited neighbor of the current vertex.
10+
4. If an unvisited neighbor is found, repeat steps 2-3 for that neighbor.
11+
5. If no unvisited neighbor is found, backtrack to the previous vertex.
12+
6. Repeat steps 2-5 until all vertices are visited.
13+
14+
##Recursive DFS
15+
16+
The recursive version of DFS is implemented using a function that calls itself for each unvisited neighbor.
17+
18+
```
19+
void dfs_recursive(const std::vector<std::vector<int>>& graph, int current, std::vector<bool>& visited) {
20+
// Mark the current vertex as visited
21+
visited[current] = true;
22+
std::cout << current << " ";
23+
24+
// Explore all unvisited neighbors
25+
for (int neighbor : graph[current]) {
26+
if (!visited[neighbor]) {
27+
dfs_recursive(graph, neighbor, visited);
28+
}
29+
}
30+
}
31+
32+
int main() {
33+
// Example graph represented as an adjacency list
34+
std::vector<std::vector<int>> graph = {
35+
{1, 2},
36+
{3},
37+
{4},
38+
{},
39+
{}
40+
};
41+
42+
// Initialize visited array
43+
std::vector<bool> visited(graph.size(), false);
44+
45+
// Example usage
46+
std::cout << "Recursive DFS starting from vertex 0:\n";
47+
dfs_recursive(graph, 0, visited);
48+
std::cout << "\n";
49+
50+
return 0;
51+
}
52+
```

‎test/test_dfs_algorithm.cpp

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
#include<iostream>
2+
#include<vector>
3+
#include<stack>
4+
#include<cassert>
5+
6+
usingnamespacestd;
7+
8+
/**
9+
* @brief This class represents a simple undirected graph and provides a Depth-First Search (DFS) algorithm.
10+
*
11+
* The problem involves traversing an undirected graph using the Depth-First Search algorithm. Given a graph with
12+
* a certain number of vertices and edges, the DFS algorithm explores the vertices in a way that prioritizes
13+
* visiting unexplored neighbors, backtracking only when necessary.
14+
*
15+
* @details The Depth-First Search (DFS) algorithm is a recursive or iterative algorithm used to explore a graph's
16+
* vertices and edges. Starting from a specific vertex, the algorithm visits the vertex and then recursively explores
17+
* its unvisited neighbors, backtracking only when no further unexplored neighbors are present. This process ensures
18+
* that all vertices connected to the starting vertex are visited.
19+
*/
20+
classGraph {
21+
public:
22+
int vertices;
23+
vector<vector<int>> adjList;
24+
25+
/**
26+
* @brief Construct a new Graph object with the given number of vertices.
27+
*
28+
* @param v Number of vertices in the graph.
29+
*/
30+
Graph(int v) : vertices(v), adjList(v) {}
31+
32+
/**
33+
* @brief Add an edge between two vertices in the graph.
34+
*
35+
* @param v The first vertex.
36+
* @param w The second vertex.
37+
*/
38+
voidaddEdge(int v,int w) {
39+
adjList[v].push_back(w);
40+
}
41+
42+
/**
43+
* @brief Perform Depth-First Search (DFS) starting from the given vertex.
44+
*
45+
* @param start The starting vertex for DFS.
46+
*
47+
* @details The DFS algorithm starts from the specified vertex, explores each connected vertex, and recursively
48+
* traverses the unvisited neighbors. The algorithm maintains a stack to keep track of the vertices to visit,
49+
* ensuring a systematic exploration of the graph.
50+
*/
51+
voidDFS(int start) {
52+
// Check the validity of the starting vertex
53+
if (start <0 || start >= vertices) {
54+
cerr <<"Invalid starting vertex" << endl;
55+
return;
56+
}
57+
58+
vector<bool>visited(vertices,false);
59+
stack<int> s;
60+
61+
s.push(start);
62+
63+
while (!s.empty()) {
64+
int current = s.top();
65+
s.pop();
66+
67+
if (!visited[current]) {
68+
cout << current <<"";
69+
visited[current] =true;
70+
}
71+
72+
for (int neighbor : adjList[current]) {
73+
if (!visited[neighbor]) {
74+
s.push(neighbor);
75+
}
76+
}
77+
}
78+
}
79+
};
80+
81+
/**
82+
* @brief Test cases for the DFS algorithm on an undirected graph.
83+
*
84+
* @details The testDFS function contains sample graph instances and tests the DFS algorithm's behavior in different scenarios,
85+
* including valid graph traversals and handling invalid starting vertices.
86+
*/
87+
voidtestDFS() {
88+
Graphg1(5);
89+
g1.addEdge(0,1);
90+
g1.addEdge(0,2);
91+
g1.addEdge(1,3);
92+
g1.addEdge(2,4);
93+
94+
cout <<"Test Case 1: Depth-First Traversal starting from vertex 0:\n";
95+
g1.DFS(0);
96+
Graphg2(3);
97+
g2.addEdge(0,1);
98+
g2.addEdge(1,2);
99+
100+
cout <<"\nTest Case 2: Invalid starting vertex (expect error message):\n";
101+
g2.DFS(5);
102+
Graphg3(0);
103+
104+
cout <<"\nTest Case 3: Depth-First Traversal on an empty graph (expect no output):\n";
105+
g3.DFS(0);
106+
Graphg4(1);
107+
108+
cout <<"\nTest Case 4: Depth-First Traversal on a graph with a single vertex:\n";
109+
g4.DFS(0);
110+
111+
Graphg5(7);
112+
g5.addEdge(0,1);
113+
g5.addEdge(0,2);
114+
g5.addEdge(1,3);
115+
g5.addEdge(2,4);
116+
g5.addEdge(5,6);
117+
118+
cout <<"\nTest Case 5: Depth-First Traversal on a graph with disconnected components starting from vertex 0:\n";
119+
g5.DFS(0);
120+
}
121+
122+
intmain() {
123+
testDFS();
124+
125+
return0;
126+
}
127+

‎test/test_dfs_algorithm.exe

121 KB
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp