This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Breadth-first traversal algorithm (BFS)

The steps of the breadth-first algorithm are as follows: starting from A, a accesses a’s unvisited leading-edge contacts B and C, then b’s unvisited leading-edge contacts D and C, then C’s unvisited leading-edge contacts F and g, and finally h’s unvisited leading-edge contacts are not abcdefgh. This is actually a binary tree traversal.

So, based on that, let’s think about it, breadth first traversal, hierarchically, every node that he goes through he checks the nodes that are next to him, right? For example, after b and C access, how do we know to start access from the lead node of B and C (i.e. D, E, F, g)? And because queues are fifO we can do that with a queue. Let’s look at the data structure of the code diagram from the previous article

Some basic operations for graphs:

FirstNeighbor(G,x) : find the FirstNeighbor of vertex x in graph G, if there is, return the index index of the FirstNeighbor, if x has no neighbor or there is no vertex x in graph, return -1

NextNeighbor(G,x,y) : Assuming vertex y in graph G is an adjacency of vertex x, returns the index index of the next adjacency of vertex x except y, or -1 if y is the last adjacency of x

bool visited[MaxVertex]; Void BFSTraverse(Grapha G){for(I =0; i<G.vertexNum; i++){ visited[i] = false; // Initialize access array} InitQueue(Q); // Initialize the secondary queue for(I =0; i<G.vertexNum; i++){ if(! visited[i]){ BFS(G,i); } } } void BFS(Graph G,int v){ visit(v); V visited[v] = true; Enqueue(Q,v); // queue the node while(! IsEmpty (Q)){// the loop knows that the queue isEmpty. V for(w=FirstNeighbor(G,v); w>=0; NextNeighbor(G,v,w) {NextNeighbor(G,v,w) {NextNeighbor(G,v,w); visited[w]){ visit(w); visited[w] = true; Enqueue(Q,w); }}}}Copy the code

Performance analysis: Time complexity

Using led by matrix storage: O (2) | | V

Using led by table stores: O (+ | E | | V |)

Space complexity:

O (| V |) (with the help of a auxiliary queue Q)