Sunday 26 February 2023
here's an example implementation of Depth-First Search (DFS) algorithm in Python:
# define the graph as a dictionary of vertices and their adjacent vertices
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': [],
'E': ['F'],
'F': [],
'G': []
}
# define the DFS function
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# call the DFS function with the starting vertex
dfs(graph, 'A')
In this example, we define a graph as a dictionary of vertices and their adjacent vertices. We then define the DFS function using an iterative approach. The function initializes a visited set and a stack with the starting vertex.
The function then loops while there are still vertices in the stack. It pops the last vertex from the stack and checks if it has already been visited. If it hasn't, it adds it to the visited set and prints it. It then extends the stack with the unvisited neighbors of the current vertex.
Finally, we call the DFS function with the starting vertex 'A' to begin the search. The output will be the order in which the vertices were visited during the DFS traversal.
here's an example implementation of Depth-First Search (DFS) algorithm in Java:
import java.util.*;
public class DepthFirstSearch {
private Map<Integer, List<Integer>> graph;
public DepthFirstSearch(Map<Integer, List<Integer>> graph) {
this.graph = graph;
}
public void dfs(int start) {
Set<Integer> visited = new HashSet<>();
dfsHelper(start, visited);
}
private void dfsHelper(int vertex, Set<Integer> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
List<Integer> neighbors = graph.get(vertex);
if (neighbors != null) {
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited);
}
}
}
}
public static void main(String[] args) {
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(4, 5));
graph.put(3, Arrays.asList(6, 7));
graph.put(4, Collections.emptyList());
graph.put(5, Arrays.asList(6));
graph.put(6, Collections.emptyList());
graph.put(7, Collections.emptyList());
DepthFirstSearch dfs = new DepthFirstSearch(graph);
dfs.dfs(1);
}
}
In this example, we define a DepthFirstSearch class that takes a graph as input and provides a dfs method to perform the DFS traversal. The dfs method initializes a visited set and calls a helper method to perform the DFS traversal starting from the given vertex.
The helper method adds the current vertex to the visited set and prints it. It then recursively calls itself on all of its unvisited neighbors.
Finally, we create a sample graph as a Map<Integer, List<Integer>> and call the dfs method on the starting vertex '1' to begin the search. The output will be the order in which the vertices were visited during the DFS traversal.
here's an example implementation of Depth-First Search (DFS) algorithm in PHP:
<?php
class Graph {
private $graph;
public function __construct($graph) {
$this->graph = $graph;
}
public function dfs($start) {
$visited = [];
$this->dfsHelper($start, $visited);
}
private function dfsHelper($vertex, &$visited) {
$visited[$vertex] = true;
echo $vertex . " ";
$neighbors = $this->graph[$vertex];
if ($neighbors !== null) {
foreach ($neighbors as $neighbor) {
if (!isset($visited[$neighbor])) {
$this->dfsHelper($neighbor, $visited);
}
}
}
}
}
$graph = [
1 => [2, 3],
2 => [4, 5],
3 => [6, 7],
4 => [],
5 => [6],
6 => [],
7 => []
];
$dfs = new Graph($graph);
$dfs->dfs(1);
?>
In this example, we define a Graph class that takes a graph as input and provides a dfs method to perform the DFS traversal. The dfs method initializes a visited array and calls a helper method to perform the DFS traversal starting from the given vertex.
The helper method adds the current vertex to the visited array and prints it. It then recursively calls itself on all of its unvisited neighbors.
Finally, we create a sample graph as an associative array and call the dfs method on the starting vertex '1' to begin the search. The output will be the order in which the vertices were visited during the DFS traversal.
here's an example implementation of Depth-First Search (DFS) algorithm in Android using Java:
import java.util.*;
public class Graph {
private Map<Integer, List<Integer>> graph;
public Graph(Map<Integer, List<Integer>> graph) {
this.graph = graph;
}
public void dfs(int start) {
Set<Integer> visited = new HashSet<>();
dfsHelper(start, visited);
}
private void dfsHelper(int vertex, Set<Integer> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
List<Integer> neighbors = graph.get(vertex);
if (neighbors != null) {
for (int neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited);
}
}
}
}
}
In this example, we define a Graph class that takes a graph as input and provides a dfs method to perform the DFS traversal. The dfs method initializes a visited set and calls a helper method to perform the DFS traversal starting from the given vertex.
The helper method adds the current vertex to the visited set and prints it. It then recursively calls itself on all of its unvisited neighbors.
You can call the dfs method on a Graph object to perform the DFS traversal. You'll need to create a Map<Integer, List<Integer>> object to represent the graph and populate it with the appropriate vertices and edges.
here's an example implementation of Depth-First Search (DFS) algorithm in C++:
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
vector<vector<int>> graph;
public:
Graph(vector<vector<int>> graph) {
this->graph = graph;
}
void dfs(int start) {
vector<bool> visited(graph.size(), false);
dfsHelper(start, visited);
}
private:
void dfsHelper(int vertex, vector<bool>& visited) {
visited[vertex] = true;
cout << vertex << " ";
for (int neighbor : graph[vertex]) {
if (!visited[neighbor]) {
dfsHelper(neighbor, visited);
}
}
}
};
int main() {
vector<vector<int>> graph = {{1, 2}, {2, 4, 5}, {6, 7}, {}, {6}, {}, {}, {}};
Graph g(graph);
g.dfs(0);
return 0;
}
In this example, we define a Graph class that takes a graph as input and provides a dfs method to perform the DFS traversal. The dfs method initializes a visited vector and calls a helper method to perform the DFS traversal starting from the given vertex.
The helper method adds the current vertex to the visited vector and prints it. It then recursively calls itself on all of its unvisited neighbors.
Finally, we create a sample graph as a vector of vectors and call the dfs method on the starting vertex '0' to begin the search. The output will be the order in which the vertices were visited during the DFS traversal.