Shulou(Shulou.com)05/31 Report--

What this article shares with you is the application case analysis of bfs and dfs. The editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Breadth-first search application example: calculating network hops

The graph structure plays an important role in solving many network-related problems.

For example, it is used to determine the best path from one node to another (the gateway from one network to another) in the Internet. One modeling method is to use undirected graph, in which vertices represent network nodes and edges represent connections between nodes. Using this model, breadth-first search can be used to help determine the minimum number of hops between nodes.

As shown in figure 1, the figure represents six network nodes in Internet. With node1 as a starting point, there is more than one path to node4. They are all feasible paths. Breadth-first search can determine the shortest path choice, that is, a total of only two hops.

We use bfs as the name of the breadth-first search function (see examples 1 and 2). This function is used to determine the minimum number of hops between two nodes in the Internet. This function takes three parameters: graph is a graph, which in this case represents the entire network; start represents the starting vertex; and hops is the list of hops returned. The function bfs modifies the graph graph, so create a copy of the diagram before calling the function if necessary. In addition, a pointer to the actual vertex in the graph is returned in the hops, so the caller must ensure that it remains valid as long as the storage space in the hops,graph is accessed.

Each vertex in graph is a BfsVertex-type structure (see example 1), which has three members: data is a data domain pointer to vertices in the graph, color maintains the color of vertices during search, and hops maintains hop count from the starting vertex to the target vertex.

The match function is passed to graph_init as an argument by the caller when initializing the graph. The match function should only compare data members in the BfsVertex structure.

The bfs function will be calculated in the breadth-first search manner described earlier. To record the minimum number of hops to reach each vertex, set the hop count for each vertex to add 1 to the hop count of the vertices adjacent to that vertex. This is done for each vertex found and painted gray. The color and hop count information of each vertex is maintained by BfsVertex in the adjacency list structure linked list. Finally, all vertices in the hops whose hop count is not marked as-1 are loaded. These are the vertices that can be reached from the starting vertex.

The time complexity of bfs is O (Variety E), where V represents the number of vertices in the graph and E is the number of edges. This is because the running time of O (V) is required to initialize the color attribute of the vertex and to ensure the existence of the starting vertex, the complexity of the loop in the breadth-first search is O (Vitere), and the time to load the hops statistical linked list is O (V).

Example 1: breadth-first search header file

/ * bfs.h*/#ifndef BFS_H#define BFS_H#include "graph.h" # include "list.h" / * define vertex data structures in breadth-first search * / typedef struct BfsVertex_ {void * data; VertexColor color; int hops;} BfsVertex;/* function interface definition * / int bfs (Graph * graph, BfsVertex * start, List * hops); # endif / / BFS_H

Example 2: implementation of breadth-first search

/ * bfs.c*/#include # include "bfs.h" # include "graph.h" # include "list.h" # include "queue.h" / * bfs * / int bfs (Graph * graph, BfsVertex * start, List * hops) {Queue queue; AdjList * adjlist, * clr_adjlist; BfsVertex * clr_vertex, * adj_vertex; ListElmt * element, * member / * initialize all nodes in the graph as breadth-first nodes * / for (element = list_head (& graph_adjlists (graph)); element! = NULL; element = list_next (element)) {clr_vertex = ((AdjList *) list_data (element))-> vertex If (graph- > match (clr_vertex,start)) {/ * initialize start vertices * / clr_vertex- > color = gray; clr_vertex- > hops = 0;} else {/ * initialize non-start vertices * / clr_vertex- > color = white; clr_vertex- > hops =-1 }} / * initialize the queue and queue the adjacency table of the starting vertex * / queue_init (& queue,NULL); / * return the adjacency table of the starting vertex and store it in clr_adjlist*/ if (graph_adjlist (graph,start,&clr_adjlist)! = 0) {queue_destroy (& queue); return-1 } / * queue vertex adjacency table to queue * / if (queue_enqueue (& queue,clr_adjlist)! = 0) {queue_destroy (& queue); return-1;} / * perform breadth first exploration * / while (queue_size (& queue) > 0) {adjlist = queue_peek (& queue) / * iterate through every vertex in the adjacency table * / for (member = list_head (& adjlist- > adjacent); member! = NULL; member = list_next (member)) {adj_vertex = list_data (member) / * determine the color of the next adjacent point * / if (graph_adjlist (graph,adj_vertex,&clr_adjlist)! = 0) {queue_destroy (& queue); return-1;} clr_vertex = clr_adjlist- > vertex / * Mark the white vertex gray and queue its adjacent vertices * / if (clr_vertex- > color = = white) {clr_vertex- > color = gray; clr_vertex- > hops = ((BfsVertex *) adjlist- > vertex)-> hops + 1 If (queue_enqueue (& queue,clr_adjlist)! = 0) {queue_destroy (& queue); return-1 } / * remove the current vertex adjacency table from the queue and paint it black * / if (queue_dequeue (& queue, (void * *) & adjlist) = = 0) {((BfsVertex *) adjlist- > vertex)-> color = black;} else {queue_destroy (& queue) Return-1;}} queue_destroy (& queue); / * returns the hop count of each vertex in a linked list * / list_init (hops,NULL); for (element = list_head (& graph_adjlists (graph)); element! = NULL Element = list_next (element) {/ * skip those nodes that are not accessed (hops =-1) * / clr_vertex = ((AdjList *) list_data (element))-> vertex If (clr_vertex- > color! =-1) {if (list_ins_next (hops,list_tail (hops), clr_vertex)! = 0) {list_destroy (hops); return-1;} return 0;} depth-first search examples: topological sorting

Sometimes we have to determine an acceptable order of execution based on the dependencies between various things. For example, a course in a university that must meet certain prerequisites before it can be taken, or a complex project in which a particular phase must be completed before other stages begin. To model this kind of problem, we can use priority graph, which adopts the idea of directed graph. In the priority graph, vertices represent tasks, while edges represent dependencies between tasks. Start with a task that must be completed first and end with other tasks that depend on this task. Draw an edge.

As shown in the following figure, it represents a course schedule of seven courses and their prerequisites: S100 has no prerequisites, S200 requires S100Magi S300 needs S200 and M100Magi M100 has no prerequisites, M200 needs M100 and M300 requires S300 and M200, and S150 has no prerequisites and is not a prerequisite.

By performing topological sorting on these courses, depth-first search helps to determine the acceptable order in No. 1 Middle School.

Topological sorting arranges vertices into a directed acyclic graph, so all edges are oriented from left to right. Formally, the topological sort of a directed acyclic graph G = (VMague E) is a linear sort of its vertices, so that if there is an edge in G, then u appears before v in the linear order, and in many cases, there are multiple orders that satisfy this condition.

The following code example implements the function dfs, a depth-first search. This function is used here to sort tasks topologically. Dfs has two parameters: graph represents the graph, which in this case represents the tasks that need to be sorted, and the parameter ordered is the linked list of vertices returned after the topological sort is completed. Calling this function modifies the figure graph, so if necessary, create a copy of the graph before calling it. In addition, the pointer to the vertices in the graph graph is stored in the linked list ordered after the function returns, so the caller must ensure that the storage space in the graph remains valid once the elements in the ordered are accessed. Each vertex in graph is a DfsVertex structure, which has two members: data is a pointer to the vertex data domain, and color is responsible for maintaining vertex color information during the search. The match function, which is passed to graph_init by arguments when the caller initializes the graph, should only compare data members in the DfsVertex structure.

Dfs searches in a depth first manner. Dfs_main is the function that actually performs the search. The last loop in dfs ensures that all unconnected elements in the diagram are retrieved. Complete the search for vertices one by one in dfs_main and blacken them, then insert the head of the linked list ordered. Finally, the ordered contains the vertices sorted by the complete topology.

The time complexity of dfs is O (vault E), V represents the number of vertices in the graph, and E represents the number of edges. This is because it takes O (V) time to initialize the color information of vertices, while the time complexity of dfs_main is O (video).

Example 3: header file for depth-first search

/ * dfs.h*/#ifndef DFS_H#define DFS_H#include "graph.h" # include "list.h" / * define a structure for all nodes in the depth-first search * / typedef struct DfsVertex_ {void * data; VertexColor color;} DfsVertex;/* Common Interface * / int dfs (Graph * graph,List * ordered); # endif / / DFS_H

Example 4: function implementation of depth-first search

/ * dfs.c*/#include # include "dfs.h" # include "graph.h" # include "list.h" / * dfs_main*/static int dfs_main (Graph * graph, AdjList * adjlist, List * ordered) {AdjList * clr_adjlist; DfsVertex * clr_vertex, * adj_vertex; ListElmt * member / * first, paint the starting vertex gray and traverse its adjacent vertex set * / ((DfsVertex *) adjlist- > vertex)-> color = gray; for (member = list_head (& adjlist- > adjacent); member! = NULL; member = list_next (member)) {/ * determine the color of the next set vertex * / adj_vertex = list_data (member) If (graph_adjlist (graph,adj_vertex,&clr_adjlist)! = 0) {return-1;} clr_vertex = clr_adjlist- > vertex / * if the current vertex is white, recursively search its adjacency * / if (clr_vertex- > color = = white) {if (dfs_main (graph,clr_adjlist,ordered)! = 0) return-1 Paint the current vertex "black" and add it to the header of the linked list * / (DfsVertex *) adjlist- > vertex)-> color = black; if (list_ins_next (ordered, NULL, (DfsVertex *) adjlist- > vertex)! = 0) return-1; return 0;} / * dfs*/int dfs (Graph * graph, List * ordered) {DfsVertex * vertex; ListElmt * element / * initialize all vertices in the graph * / for (element = list_head (& graph_adjlists (graph)); element! = NULL; element = list_next (element)) {vertex = ((AdjList *) list_data (element))-> vertex; vertex- > color = white;} / * perform breadth-first search * / list_init (ordered,NULL) For (element = list_head (& graph_adjlists (graph)); element! = NULL; element = list_next (element)) {/ * ensure that every vertex in the graph can be retrieved * / vertex = ((AdjList *) list_data (element))-> vertex If (vertex- > color = = white) {if (dfs_main (graph, (AdjList *) list_data (element), ordered)! = 0) {list_destroy (ordered); return-1;}} return 0 } the above is the application example analysis of bfs and dfs. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.