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

This article introduces the knowledge of "what is the undirected graph of C++". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Undirected graph

If you draw casually on paper, or just give an exemplary description of the graph, most people will choose undirected graph. However, in the computer, the undirected graph is stored according to the method of directed graph-two directed edges. In fact, when we talk about non-directionality, we just ignore the direction-draw a line on the paper, is it possible that the line "whoosh" appears, not from one end to the other? Undirected graph has several unique concepts, such as connected components, link nodes, and minimum spanning tree. Before that, the basic operation of the undirected graph class is completed.

Undirected graph class

Template class Graph: public Network {public: Graph () {} Graph (dist maxdist): Network (maxdist) {} bool insertE (name v1, name v2, dist cost) {if (Network::insertE (v1, v2, cost)) return Network::insertE (v2, v1, cost); return false;}}

Just add an edge, and then add a reverse edge, it is very simple.

Connected component

This is unique to the undirected graph, and the directed graph is much more complex (strong, simple, and weakly connected). The reason is that the edge of the undirected graph can go any way, and the edge of the digraph seems to fall into the bottomless abyss and never climb up again. With DFS, the algorithm for finding connected components becomes very simple-just call DFS for each vertex that is not accessed.

Void components () {visited = new bool [vNum ()]; int I, j = 0; for (I = 0; I < vNum (); visited +) visited [I] = false; 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.