Breadth-first and depth-first are two common traversal methods for graphs in C++ data structures. My understanding and rough code implementation are posted below

Breadth First (BFS)

The principle of

BFS traverses each node along the width of the graph (tree), starting at the root, layer by layer.

Specific steps:

• 1. Set all nodes to unmarked
• 2. Select a node as the starting point, join the team, and mark it as visited (visited is gray in the figure)
• 3. Check whether the queue is empty. If yes, go to 4
• 4. Remove the starting point from the queue, find the adjacent nodes of the starting point that have not been visited, insert them successively into the queue, and mark these nodes as visited
• 5. Repeat 3

Here is:

Code implementation

#include <iostream>
#include <queue>
#define N 5
using namespace std;

/ / build figure
int G[N][N] = {
    { 0.1.1.0.0 },
    { 0.0.1.1.0 },
    { 0.1.0.1.0 },
    { 1.0.0.0.0 },
    { 0.0.1.1.0}};// Marks whether the node is accessed
int visited[N] = { 0 };

/ / BFS algorithm
void BFS(int start)
{
    queue<int> Q;// Store the adjacency
    Q.push(start);
    visited[start] = 1;// Access set to 1

    while(! Q.empty())// Adjacency exists
    {
        int front = Q.front(a);//cout << front << " "; // Fetch the accessed node
        Q.pop(a);// Push out the visited node in Q

        for (int i = 0; i < N; i++)
        {
            // Node I is not accessed and node I is the neighbor of node front
            if(! visited[i] && G[front][i] ==1)   
            {
                visited[i] = 1;// Mark node I as visited
                Q.push(i);// add node I to Q}}}}int main(a)
{
    // Start at node 0
    for (int i = 0; i < N; i++)
    {
        // Already traversed, skip this node, traversed next node
        if (visited[i] == 1)    
            continue;
        BFS(i); // Iterate over node I
    }
    return 0;
}
Copy the code