Shulou(Shulou.com)06/01 Report--

This article mainly explains "C language how to find the shortest path between two points of undirected graph". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn "C language how to find the shortest path between two points of undirected graph"!

1. Brief introduction

Undirected graph is a kind of graph structure. This program uses the adjacency table to achieve undirected graph, and through breadth-first traversal to find the shortest path between the two points.

two。 Breadth first traversal

Breadth-first traversal (BFS) and depth-first traversal (DFS) are the most commonly used traversal methods in graph structures. Among them, breadth-first traversal combined with the queue can find the shortest path between two points, and can also solve some other problems (such as finding the shortest escape route of the maze). The breadth-first traversal to find the shortest path between two points is divided into the following steps:

1)。 First define the start point and end point src and dst. Then an array distance [] is defined to store the distance from each point to src. The distance from each point to src during initialization is INF (which means positive infinity. You can define it here to indicate that the distance from the node to src has not yet been obtained, and distance [src] = 0. Then put the src in the queue.

2)。 The first node of the fetch queue (there is only src in the queue at the beginning, here is the src), and put it in the variable top.

3)。 Get all the adjacency nodes of the node, and determine whether each adjacency node in the distance [] array is INF. If it means that the node has not been accessed, set the corresponding location of distance [] to distance [top] + 1. If it is not INF, it means that it has been accessed before, so it is skipped.

4)。 Repeat steps 2-3 until the top variable equals dst. Or until the queue is empty, which means there is no path between the two points.

To sum up, nodes are placed in the queue sequentially starting with src, and nodes that have already been placed in the queue are identified, so they are not repeatedly placed in the queue until dst is found. The path obtained by this method is the shortest when the path is constant.

3. Output shortest path

Using breadth-first traversal above, the length of the shortest path between two points is found and stored in distance[ DST], and there are different ways to output this shortest path. The method I use here is to push dst into the stack first, and then press it into the stack by traversing which of the adjacency nodes of dst has a value of distance [DST]-1 in the distance array. Then continue to look for the previous node and press it into the stack as well. Loop the operation and finally find the src, and then pop the elements in the stack in turn. Because of the first-in-and-out nature of the stack, the path can be obtained.

4. Code implementation

The specific code is as follows

# ifndef _ GRAPH_H#define _ GRAPH_H# include # define ERROR-1#define V_E_INFO 1#define FIND 1#define PATH 2#define MAX 100 using namespace std; class ArcNode {private: int value; ArcNode * next; public: ArcNode (int, ArcNode * = nullptr); void set_next (ArcNode *); ArcNode * get_next () const; int get_value () const; void set_value (int);} Class List {private: int value; ArcNode * firstnode; public: List (int = 0MagneArcNode * = nullptr); ~ List (); ArcNode * Pop (); void Push (int); int get_value () const; int is_exist (int) const; ArcNode * get_firstnode () const; void set_value (int); void dfs_find_path () const; void set_firstnode (ArcNode *); void print () const }; class Graph {private: List list [MAX]; int vertices_num; int edge_num; public: Graph (int,int,int []); ~ Graph (); int get_vertices_num () const; int get_edge_num () const; List * get_list (int); void print () const; void dfs_print_path (int,int) const Void dfs_find_path (int,int,int [], stack &, int &) const; void dfs (int src,int visited [], int & count) const; void dfs_print (int) const; void dfs_non_recursive () const; int find_shortest_path (int,int) const; void dfs (int,int []) const;}; # endif

BFS looks for the shortest path code:

Int Graph::find_shortest_path (int src,int dst) const {queue myQ; int values [vertices _ num]; / the distance used to store each point to src int head = 0; int output [10]; for (int I = 0 int I < vertices_num;i++) {value [I] =-1 Tran Lane 1 indicates that the node} value [src] = 0; myQ.push (src) has not been visited yet While (myQ.size ()) {head = myQ.front (); myQ.pop (); if (head = = dst) {int find = dst; stack myS; myS.push (dst); while (find! = src) {for (int j = 0; j < vertices_num) Break; +) {if ((list [j]. Is _ exist (find) = = 1) & & (value [find] = = value [j] + 1)) {myS.push (j); find = j; break;} int count = myS.size (); for (int j = 0 int count j < count) Cout get_next +) {if (j = = count-1) cout get_next ();}} cout

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.