Data structure learning (C ++) - Figure [2] (DFS and BFS)

For nonlinear structures, traversal will first become a problem. Like the traversal of the binary tree, there are also depth priority search (DFS) and breadth priority search (BFS). Different, each vertex in the figure does not have the relationship between ancestors and descendants, so preface, order, and rear sequences no longer meaningful. It is easy to complete DFS and BFS, just to pay attention to the path in the picture, so you must mark the vertices accessed.

The most basic

#ifndef graph_h

#define graph_h

#include

#include

Using namespace std;

#include "graphmem.h"

Template

Class network

{

PUBLIC:

NetWork () {}

NetWork (dist MAXDIST) {data.noedge = maxdist;

~ NetWork () {}

Bool INSERTV (Name V) {Return Data.insertv (V);

Bool Inserte (Name V1, Name V2, Dist Cost) {Return Data.inserte (V1, V2, COST);

Name & GetV (INT N) {Return Data.Getv (n);

INT NEXTV (INT M, INT N = -1) {Return Data.nextv (M, N);}

INT VNUM () {Return Data.vnum;}

INT enum () {return data.enum;}

protected:

Bool * visited;

Static void print (name v) {cout << v;

Private:

MEM DATA;

}

#ENDIF

You can see that this is a layer of housing that is added over the DATA stored in MEM. In the figure, there is a logical, no trend, right, no right; there is an adjacent matrix and adjacent tables on the storage structure. That is to say, there are 8 classes separately. In order to maximize multiplexing code, inheritance relationship is very complicated. However, multiple inheritance is a very annoying thing, what is covered, what is virtual inheritance, I don't want to spend a lot of space speech characteristics. So, I will save the way as the third template parameter, so that I save the virtual inheritance, just this way of this NetWork is very troublesome, but this can be solved by typedf or shell class. Not written. Anyway, just to let everyone understand that when you really need to use, it is best to write a special class, such as no needless neighbor matrix map, don't engage in inheritance relationships.

DFS and BFS implementation

PUBLIC:

Void DFS (Void (* V) (Name V) = Print)

{

Visited = new bool [vnum ()];

For (int i = 0; i

DFS (0, Visit);

DELETE [] Visited;

}

protected:

Void DFS (INT I, VOID (* V) (Name V) = Print

{

Visit (Getv (i)); Visited [i] = true;

For (int n = nextv (i); n! = -1; n = nextv (i, n)) IF (! Visited [n]) DFS (N, VISIT);

}

PUBLIC:

Void BFS (int i = 0, void (* visit) (Name V) = Print) // N no critical inspection

{

Visited = new bool [vnum ()]; queue a; int N;

For (n = 0; n

Visited [I] = true;

While (i! = -1) // This judgment may be useless

{

Visit (Getv (i));

FOR (n = nextv (i); n! = -1; n = nextv (i, n)))

IF (! Visited [n]) {a.push (n); visited [n] = true;

IF (a.empty ()) BREAK;

i = a.front (); a.POP ();

}

DELETE [] Visited;

}

The DFS and BFS functions are difficult to write like the traversal method of the tree, which will be seen later, although we use DFS and BFS ideas, but the above functions cannot be used directly. Because the information of the tree is mainly on the node, there is information on the edge of the figure.

test program

#include

Using namespace std;

#include "graph.h"

int main ()

{

Network >

A.Nsertv ('a'); a.insertv ('b');

A.Nsertv ('c'); a.insertv ('d');

A.NSERTE ('a', 'b', 1); a.inserte ('A', 'C', 2);

A.NSERTE ('B', 'D', 3);

COUT << "DFS:"; a.dfs (); cout << endl;

COUT << "BFS:"; A.BFS (); cout << Endl;

Return 0;

}

Honestly, this class is really not very convenient. However, you can explain the problem.