China
Africa
Explore chapters and articles related to this topic
Big Graph Analytics: Techniques, Tools, Challenges, and Applications
Published in Mohiuddin Ahmed, Al-Sakib Khan Pathan, Data Analytics, 2018
Dhananjay Kumar Singh, Pijush Kanti Dutta Pramanik, Prasenjit Choudhury
A graph is basically a collection of nodes where each node might point to the other nodes. The graphs can be directed like one-way streets or can be undirected like two-way streets in the city. Suppose we want to go through this graph, and specifically suppose we want to do something, like figure out if there is a path from one node to another. There are two common ways of doing this: Breadth-first search (BFS): The BFS is a level-by-level graph traversal algorithm that performs searching on unweighted, undirected graph from the given start vertex and assigns the distance to each vertex.Depth-first search (DFS): The DFS is typically a recursive graph traversal algorithm that explores as deeply as possible using one neighbor before backtracking to other neighbors. DFS does not go through all the edges. The vertices and edges, which depth first search has visited, form a tree (graph spanning tree).
Artificial Intelligence
Published in Naveen Chilamkurti, T. Poongodi, Balamurugan Balusamy, Blockchain, Internet of Things, and Artificial Intelligence, 2021
Ishita Singh, Joy Gupta, K. P. Arjun
Breadth-first search (BFS) is used to traverse trees and graphs [7]. It is the most common search algorithm. This uses its algorithm to search breadth wise in trees or graphs. This algorithm begins the process of searching from the root node of the tree and then spreads to the next node on the ongoing level. Then after completing its search on the first level, it moves to nodes of the next level. It is implemented using the FIFO queue data structure. Figure 3.4 shows the work of breadth-first search with an example.
Paths and Walks
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
The breadth-first search (BFS) algorithm is a fundamental algorithm in graph theory. It appears in various guises wherever shortest paths are useful (e.g., network flows, matching theory, coset enumeration, etc.). Figure 2.4 shows the result of applying a BFS to the Petersen graph, where the vertices are numbered according to the order in which they were visited by the algorithm, and shaded according to their distance from vertex 1. The thicker edges show the shortest paths found by the algorithm.
Inverse reinforcement learning-based time-dependent A* planner for human-aware robot navigation with local vision
Published in Advanced Robotics, 2020
Shiying Sun, Xiaoguang Zhao, Qianzhong Li, Min Tan
The A* algorithm integrates the characteristics of the best-first search (BFS) algorithm and Dijkstra algorithm [26] to use a graph search method to search for an optimal path. The evaluation function of the A* algorithm is given by: where denotes the cost function of the robot from initial state to current state s, represents the estimated distance (heuristic function) from current state s to the target position.
RMRL: improved regret minimisation techniques using learning automata
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2019
Safiye Ghasemi, Mohammad Reza Meybodi, Mehdi Dehghan Takht-Fooladi, Amir Masoud Rahmani
However, in many real applications, the use of direct Euclidean distance is not possible as the existence of obstacles. Therefore, the grid is modelled as a graph. Then, BFS algorithm is used to find the shortest path between nodes A and B; dis(A,B) is the number of nodes which are traversed to reach B from A.