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

Today, the editor will share with you the relevant knowledge about what the C++ adjacency list is. The content is detailed and the logic is clear. I believe most people still know too much about this, so share this article for your reference. I hope you can get something after reading this article. Let's take a look at it.

Figure

Graph structure is a kind of nonlinear structure which is more complex than tree structure. In the tree structure, there is a branch hierarchical relationship between nodes, and the nodes on each layer can only be related to at most one node in the upper layer, but may be related to multiple nodes in the next layer. In the graph structure, any two nodes may be related, that is, the adjacency relationship between nodes can be arbitrary. Therefore, graph is a more general and complex nonlinear structure than tree. it is often used to describe a variety of complex data objects and is widely used in many fields, such as natural science, social science, humanities and so on.

Section 1 basic concepts

1.1 Definitions and terminology

(1) attribute:

A graph (Graph) consists of a set of non-empty vertices and a set of edges (or arcs) that describe the relationship between vertices. It is formally defined as: G = (VMagne E), V = {v1 | v1 contains data object}, E = {(v1jjjvj) | (vi,vj contains V ^ P (vj,vj). Where G denotes a graph, V is the set of vertices in G, E is the set of edges in G, and P (vi,vj) in the set E indicates that there is a direct connection between vertex vi and vertex vj, that is, an even pair (V1memvj) denotes an edge. For example: G2 = (V2MagneE2), V2 = {v1recoveryv3recoverv4}, E2= {,}.

(2) terminology:

1. Undirected graph: in a graph, if the vi,vj of any two vertices including E is unordered, that is, the connection between vertices is undirected, then the graph is called an undirected graph.

2. A directed graph: in a graph, a graph is called a directed graph if the even pair consisting of any two vertices contains E is ordered (ordered pairs are often represented by angle brackets), that is, the lines between vertices are directed.

3. Vertex, edge, arc, arc head, arc tail: in the graph, the data element vi is called vertex (Vertex); (vj,vj) indicates that there is a direct connection between vertex vi and vertex vj. If it is in an undirected graph, it is called an edge; if it is in a directed graph, it is generally called an arc. The edge is represented by the unordered pair (vi,vj) of the vertex, the vertex vi and vj are adjacent to each other, and the edge is attached to the vertex vi and the vertex vj; arc is represented by the ordered pair of vertices. The first node vi of the ordered pair is called the starting point (or arc tail), which is the end without arrowheads in the graph; the second node vj of the ordered pair is called the end (or arc head), which is the end with arrows in the graph.

4. Undirected complete graph: in an undirected graph, if any two vertices are connected by a direct edge, the graph is called undirected complete graph. It can be proved that there are n (n Mel 1) / 2 edges in an undirected complete graph with n vertices.

5. A directed complete graph: in a directed graph, if two arcs with opposite directions are connected between any two vertices, the graph is called a directed complete graph. In a complete digraph with n vertices, there are n (n Mel 1) edges.

6. The degree of a vertex: the degree of a vertex (Degree) refers to the number of edges attached to a vertex v, usually marked as TD (v). The entrance degree of vertex v refers to the number of arcs with vertex v as the end point, marked as ID (V), and the exit degree refers to the number of arcs with vertex v as the starting point, marked as OD (V). There is TD (V) = ID (v) + OD (v).

7. Weight: the data information related to the edge is called weight (weight). In practical application, weights can have some meaning. For example, in a diagram that reflects a city's traffic line, the weight on the edge can indicate the length or grade of the line; for an electronic circuit diagram, the weight on the edge can represent the resistance, current or voltage between the two endpoints; for a diagram that reflects the progress of a project, the weight on the edge can indicate the time or other costs required from the previous project to the next project. The weighted graph on the edge is called network or network (network).

8. Path, path length: the path between vertex vp and vertex vq (path) refers to the vertex sequence vp, vi1, vi2, vim, vq. Where (vp,vi1), (vi1,vi2) and (vim,vq) are the edges in the graph, respectively. The number of edges on a path is called the path length.

9. Simple path, loop, simple loop: the path in which the vertices do not repeat in the sequence is called the simple path. The path where the first vertex in the path is the same as the last vertex is called a loop or Cycle. With the exception of the first vertex and the last vertex, the loop in which the other vertices do not repeat is called a simple loop, or a simple ring.

10. Subgraph: for a graph G = (VJO E), G is called a subgraph of G if there exists that V'is a subset of V and E'is a subset of E.

11. Connected, connected graph, connected component: in an undirected graph, if there is a path from one vertex vi to another vertex vj, then vertex vi and vj are said to be connected. A graph is called a connected graph if any two vertices in the graph are connected. The maximal connected subgraph of an undirected graph is called connected component, which means that it contains all the vertices and edges of the original graph under the condition of ensuring connectivity and subgraph. As shown below:

12. Strongly connected graph, strongly connected component: for a directed graph, a digraph is called a strongly connected graph if any pair of vertices vi and vj in the graph have paths from one vertex vi to another vertex vj and from vj to vi. The maximal strongly connected subgraph of a digraph is called a strongly connected component, and the meaning of the maximal strongly connected subgraph is the same as above.

13. Spanning tree: the spanning tree of a connected graph G is a minimal connected subgraph of G that contains all its n vertices. The so-called minimal connected subgraph contains as few edges in the original graph as possible on the premise of containing all vertices and ensuring connectivity. The spanning tree must contain only one edge of a connected graph G. Adding any edge that belongs to the original graph to the spanning tree must produce a loop because the newly added edge creates a second path between the two vertices to which it is attached. If any edge is reduced in the spanning tree, it is bound to become disconnected.

14. Spanning forest: in an unconnected graph, a minimal connected subgraph, that is, a spanning tree, can be obtained from each connected component. The spanning trees of these connected components form a spanning forest of disconnected graphs.

1.2 basic operation

1. GreatGraph (G): input vertices and edges of graph G to establish the storage of graph G.

2. DestroyGraph (G): release the storage space occupied by figure G.

3. GetVex (Ggramev): find vertex v in graph G and return information about vertex v.

4. PutVex: find vertex v in graph G and assign value value to vertex v.

5. InsertVex (Ggramev): add a new vertex v to the graph G.

6. DeleteVex (Ggravev): in graph G, delete vertex v and all edges or arcs related to vertex v.

7. InsertArc: add an edge or arc from vertex v to vertex w in graph G.

8. DeleteArc: delete an edge or arc from vertex v to vertex w in graph G.

9. DFSTraverse (Ggravev): in graph G, the depth optimization traverses graph G from vertex v.

10. BFSTtaverse (Ggramev): in graph G, the breadth-first traversal of graph G is based on vertex v.

By the same token, for all the adjacent points of a vertex, the I adjacent point of the vertex is used to represent the storage order of a vertex adjacent to the vertex. In this sense, the graph also has the following basic operations.

11. LocateVex (GForce u): find the vertex u in the graph G and return the position of the vertex in the graph.

12. FirstAdjVex (Ggramev): in graph G, return the first adjacency point of v. If the vertex does not have an adjacent vertex in G, it returns "empty".

13. NextAdjVex (GMagnevMagnew): in a graph G, return the next adjacent vertex of v (relative to w). If w is the last adjacency point of v, empty is returned.

Section 2 Storage structure

Graph is a kind of data structure with complex structure, which is shown in that not only the degrees of each vertex can vary greatly, but also the logical relationship between vertices is complicated. From the definition of a graph, the information of a graph consists of two parts, namely, the information of vertices in the graph and the information describing the relationship between vertices-edges or arcs. Therefore, no matter what method is used to establish the storage structure of the graph, the information of these two aspects should be reflected completely and accurately.

2.1 adjacency matrix

The storage structure of the so-called adjacency matrix (Adjacency Matrix) is to use an one-dimensional array to store the vertex information in the graph and use the matrix to represent the adjacency relationship between the vertices in the graph. Suppose that the graph G = (VGraue E) has n definite vertices, that is, V = {v0 vn-1 v1, V0}, then the matrix of the adjacent relations of each vertex in G is an n × n matrix, and the elements of the matrix are:

A [I] [j] = {1, if (vi,vj) or an edge in E (G); 2, if (vi,vj) or not an edge in E (G).

If G is a net, then the adjacency matrix can be defined as:

A [I] [j] = {wij, if (vi,vj) or an edge in E (G); 0 or &, if (vi,vj) or not an edge in E (G).

Where wij represents the weight on the edge (Vi,vj) or; represents the number allowed by a computer that is greater than all the weights on the edge.

(1) the adjacency matrix of an undirected graph must be a symmetric matrix. Therefore, it is only necessary to store the elements of the upper or lower triangular matrix when storing the adjacency matrix.

(2) for an undirected graph, the number of row I or column I non-zero elements or non-& elements of the adjacency matrix is exactly the degree TD (vi) of the I th vertex.

(3) for a directed graph, the number of non-zero elements or non-& elements of row I and column I of the adjacency matrix is exactly the degree OD (vi) or degree ID (vi) of the first vertex.

(4) using the adjacency matrix method to store the graph, it is easy to determine whether there are edges connected between any two vertices in the graph; however, to determine how many edges there are in the graph, each element must be detected by row and column, which takes a lot of time. This is the limitation of using adjacency matrix to store graphs.

Therefore, its form can be described as follows:

# define MaxVertexNum 100 typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs [MaxVertexNum]; / / vertex table EdgeType edges [MaxVertexNum] [MaxVertexNum]; / / adjacent matrix, that is, the edge table int nlemagement / number of vertices and edges} MGraph

2.2 adjacency table

Adjacency list (Adjacency List) is a storage method of sequential storage and chain storage of graphs. The adjacency table representation is similar to the child linked list representation of a tree. For each vertex vi in graph G, all vertex vj adjacent to vi is linked into a single linked list, which is called the adjacency list of vertex vi, and then the adjacency table headers of all vertices are put into the array to form the graph adjacency table.

There are two kinds of node structures in the adjacency table representation: one is the node structure of the vertex table, which is composed of the vertex domain (vertex) and the pointer domain (firstedge) pointing to the first adjacent edge. The other is the edge table, that is, the adjacency table node, which is composed of the adjacency point domain (adjvex) and the pointer domain (next) pointing to the next adjacent edge. For the edge table of the graph, it is necessary to add a field (info) to store the edge information (such as weights, etc.). The form is as follows:

# define MaxVerNutypedef struct node {int adjvex; struct node*next;} EdgeNode; typedef struct vnode {VertexType vertex; EdgeNode * firstedge;} VertexNode; typedef VertexNode AdjList [MaxVertexNum]; typedef struct {AdjList adjlist; int n, e;} ALGraph

If there are n vertices and e edges in an undirected graph, then its adjacency table needs n head nodes and 2e table nodes. Obviously, sparse (eadjlist [I]. Firstedge; / / take the header pointer while (p) {if (! visible [p-> adjvex]) DFSAL (adjvex); p = p-> next;}} of the edge table

3.2 breadth-first search (Breadth First Search,BFS)

Similar to the hierarchical traversal of a tree. Suppose, starting from a vertex v in the graph, visit the unvisited adjacency points of v in turn after visiting v, and then visit their adjacency points from these adjacency points in turn, and make "the adjacency points of the vertices visited first" precede the adjacency points of the vertices visited later "until all the visited adjacency points in the graph are accessed. If there are no vertices in the graph at this time, select another vertex in the graph that has not been accessed as the starting point, and repeat the above process until all the vertices are accessed. In other words, the breadth-first search process of the traversal graph is to visit the vertices that are connected with v and the path length is 1 and 2 from near to far.

Such as c in the figure above, first visit the adjacency points v2 and v3 of v1 and v1, then visit the adjacency points v4 and v5 of v2 and the adjacency points v6 and v7 of v3, and finally visit the adjacency point v8 of v4. The access sequence is: v1 → v2 → v3 → v4 → v5 → v6 → v7 → v8. Similar to depth-first search, an array of access flags is required during traversal. And in order to access vertices with a path length of 1Magne2 and 3 sequentially, a queue is needed to store the vertices that have been accessed with a path length of 1Magne2. Starting from a certain point v of the graph, the process algorithm for non-recursive breadth-first traversal is as follows:

VoidBFSTraverse (Grapg Visit status (* Visit) (int v)) {/ / non-recursive traversal graph G by breadth first, using auxiliary queue Q and access flag array visied for (v = 0; v = G.vexnum; + + v) visited [v] = FALSE; / / empty queue Q Init_Queue (Q); / / v has not been accessed if (! visited [v]) {In_Queue (QQuery v) / / v queued while (! QueueEmpty (Q)) {Out_Queue (QMagol u); visited [u] = TURE; visit (u); for (w = FirstAdjVex (GMague u); w; w = NextAdjVex (GMagazo w)) if (! visited [w] In_Queue (QMagol W);}

The following algorithm gives the C language description of the breadth-first search of graph G with adjacency matrix as its storage structure. Breadth first search algorithm:

/ * breadth-first traversal of the graph G*/void BFSTraverseAL (MGraph * G) {int i; for (ionom0; in; iTunes +) visited [I] = FALSE; / * flag vector initialization * / for (irid0; in; iota +) if (! visited [I]) BFSM (G, I) / * vi has not been visited, starting from vi, BFS search * /} / * BFSTraverseAL*/void BFSM (Mgraph * G, int k) / * take vk as the starting point, BFS search for graph G * / {int I, j; C_Queue Q; Init_Queue (& Q); printf ("visit vertex:V%c\ n", G-> vexs [k]) / * access the origin vk*/ visited [k] = TRUE; In_Queue (& Q, k); / * the origin vk is queued * / while (! QueueEmpty (& Q)) {i=Out_Queue (& Q); / * vi dequeue * / for (jack0; jn) Vj*/ if (G-> edges [I] [j] = = 1 & &! visited [j]) / * if vj does not visit * / {printf ("visit vertex:V%c\ n", G-> vexs [j]); / * visit vj*/ visited [j] = TRUE; In_Queue (& Q, j) / * queued vj visited * /} / * BFSM*/

After analyzing the above algorithms, each vertex is queued at most once. The process of traversing a graph is essentially a process of finding adjacent points through edges or arcs, so the time complexity of breadth-first search traversal graph is the same as depth-first search traversal, and the only difference between them lies in the order of visiting vertices.

Section 4 Application of graphs

4.1 minimum spanning tree

(1) basic concept: because of the definition of spanning tree, the spanning tree of undirected connected graph is not unique. The set of edges passed by a traversal of a connected graph and the set of all vertices in the graph constitute a spanning tree of the graph. For different traverses of a connected graph, different spanning trees may be obtained. For an undirected connected graph with n vertices, there is and only one edge in all spanning trees, regardless of the shape of the spanning tree.

If an undirected connected graph is a network, then one of its spanning trees must have the least total weight of the edges of the spanning tree. Such a spanning tree is called the minimum cost spanning tree (Minimum Cost Spanning Tree), or the minimum spanning tree (MST). The cost of a spanning tree is the sum of the costs of all the edges in the tree.

The concept of minimum spanning tree can be applied to many practical problems. For example, build a communication network between cities at the lowest possible total price, linking ten cities together. In these ten cities, communication lines can be built between any two cities. the cost of communication lines varies according to the distance between cities. a communication line cost network can be constructed, in which each vertex represents the city. the edge between vertices indicates that a communication line can be constructed between cities, and the weight of each edge represents the cost of the communication line. In fact, it is to find the minimum spanning tree of the network.

There are many methods to construct the minimum spanning tree, most of which make use of the MST property. The properties of MST are described as follows:

Let G = (VGraine E) be a connected network, where V is the set of all vertices in the network, E is the set of all weighted edges in the network, and the set U is used to store the vertices of the minimum spanning tree of G. If an edge in G is an edge with one end in U and the other end having the least weight in Vmuru, then there is a minimum spanning tree containing the edge (upowerv). For proof of the nature of MST, please refer to the relevant books, which are omitted here.

(2) Prim algorithm and Kruskal algorithm

Let G = (VQuery E) be a connected network, where V is the set of all vertices in the network and E is the set of all weighted edges in the network. Set two new sets U and T, where the set U is used to store the vertices in the minimum spanning tree of G, and the set T stores the edges in the minimum spanning tree of G. Let the initial value of the set U be U = {U1} (assuming that the minimum spanning tree is constructed from the vertex U1), and the initial value of the set T is T = {}. The idea of Prim algorithm is to select the edge with minimum weight from all the edges with minimum weight, add vertex v to set U and edge to set T, and repeat until the minimum spanning tree is constructed, when the set T contains all edges of the minimum spanning tree.

The Prim algorithm can be described by the following process, in which wuv is used to represent the weights on the edges of vertex u and vertex v.

1. U = {U1}, T = {}; 2. While (Usquire V) do (UMagi v) = min {wun;u v contains VML U} T = T + {(uppie v)} U + {V} 3, end

The schematic diagram of the process of constructing the minimum spanning tree by Prim algorithm is as follows:

In order to realize the Prim algorithm, it is necessary to set two auxiliary one-dimensional arrays lowcost and closevertex, in which lowcost is used to save the weight of the edge with the minimum weight in the edge composed of each vertex in the set Vmuru and the vertex in the set U, and the array closevertex is used to save the vertices in the set U attached to the edge. Suppose that when initializing the state, U = {U1 (starting vertex)}, then there is lowcost [0] = 0, which means that vertex U1 has been added to the set, and the values of other components of the array lowcost are the weights of the direct edges formed by vertex U1 to the rest of the vertices. Then the smallest edge (ui,uk) is selected continuously (u contains U _ is set to 0, indicating that the vertex uk has been added to the set U. Since the vertex uk enters the set U from the set Vmuru, the contents of these two sets have changed, so it is necessary to update the contents of some components in the array lowcost and closevertex according to the specific conditions.

When the undirected network uses the adjacency matrix stored in a two-dimensional array, the Prim algorithm is as follows:

Void Prim (int gm [] [MAXNODE], int npenint closevertex []) {/ / starting from the vertex with the sequence number 0, the minimum spanning tree established is stored in the array closevertex, int lowcost, mincost; int iMagint k; for.

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.