This article includes the basic knowledge of data structure and algorithm summary, need to understand the data structure and algorithm linked list, binary tree and other related knowledge of the students welcome to view.

A graph refers to the logical structure of data relations in a computer. Data in a computer can only be stored in a computer by two storage structures, namely sequential storage and chain storage.

First, the basic knowledge of graphs

1. The blue numbered points in the figure above are called vertices;

2. The connections between vertices are called edges.

1. Definition of graph

A Graph is a finite non-empty set of vertices and a set of edges between vertices. It is usually expressed as G(V,E), where G represents the graph, V represents the set of vertices, and E represents the set of edges between vertices.

2. Classification of graphs

1. Directed and undirected graphs

1. Divide according to the relation of edges between vertices;

2. The edge between any two verticesNo direction. Figure is called aUndirected graph, an edge is called an undirected edge;

3. The edge between any two verticesHave a directionCan only point from one vertex to another. Figure is called aDirected graph, an edge is called a directed edge.

2. Undirected complete graph and directed complete graph

There are connections between any vertex in the graph and other vertices.

3. The network diagram

The edges connected between vertices in a graph are weighted, and each edge may have different weights. This kind of graph with edge weights between vertices is called a net graph.

4. Connected and disconnected graphs

1. A graph in which there is no edge connection between some vertices and other vertices, and no indirect connection can be made by edges between verticesA connected graph, as shown in Figure 1;

2. All vertices in a graph can be connected by finite edges, that is, all vertices are connected. This graph is called a graphConnected graph, as shown in Figure 2.

5. Subgraph

A graph composed of any set of vertices and connected edges is called a subgraph of the graph.

Second, diagram storage

Take the kuaishou interview as an example:

A. the B. the C. the D. the

1. Design a data structure to store the above image in the computer memory.

2. The picture above is oneDirected graph;

3. In figureVertex data[v0 v1 v2 v3 v4],Edge data[1(v3->v4) 2(v2->v0) 3(v1->v2) 5(v2->v3) 6(v0->v4) 9(v1->v0)];

Think: how can I store vertices and edges in memory and satisfy the relationships between vertices in the graph?

(1) sequential storage – adjacency matrix

1. Adjacency matrix

(1) Graph is an undirected graph and edges have no weight

1. Use aA one-dimensional arraystorageThe verticesInformation;

2. Use a2 d arrayStore between verticesedgeInformation, the connection between vertices is represented by 1, the connection between vertices is represented by 0;

The two-dimensional array matrix storing edge information in the figure above has the following characteristics:

1. The position of row I and column J stores edge information for vertices Vi and Vj, if Vi and VjHave a connectionRelation, then row I and row jRemember to 1, the corresponding location of the two-dimensional array stores 1, otherwiseRemember to 0;

2. The matrixThe diagonalData stored on0, that is, there is no connection between any vertex and itself.

3. The data in the matrix is diagonalsymmetry, i.e.,Undirected graphBetween Vi and Vj and between Vj and ViEdge is equal.

(2) A graph is a directed graph, and an edge has no weight

The difference between this case and (1) is that the graph is a directed graph, and the edges between Vi and Vj in a two-dimensional array matrix are not equal to the edges between Vj and Vi, that is, Vi points to Vj, but Vj does not necessarily point to Vi.

(3) The graph is a directed graph and has weights

The difference between this situation and (2) is thatWith the weight, so the data stored in a two-dimensional array is the weight value of edges;

2. Since the weight value may be 1, if there is no edge information between vertices, the value stored in the corresponding two-dimensional array can be an abnormal data, such asinfinity.

Based on the above analysis, the adjacency matrix is the two-dimensional array matrix that stores the relation between vertices in the graph.

2. Code implementation

Define some state values and data types

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXVEX 100 #define INFINITYC 0 typedef int Status; //Status is the type of the function whose value is the result of the function Status code, such as OK. // typedef int EdgeType; // The weight type on the edgeCopy the code

2. Storage structure design

typedef struct { VertexType vexs[MAXVEX]; // EdgeType arc[MAXVEX][MAXVEX]; Int numNodes, numEdges; // The current number of vertices and edges in the graph}MGraph;Copy the code

3. Storage implementation

void CreateMGraph(MGraph *G){ int i,j,k,w; Printf (" Input number of vertices and edges :\n"); / / 1. Input vertex/number of edges the scanf (" % d, % d ", & G - > numNodes, & G - > numEdges); Printf (" vertices: % d, number of edges: % d \ n ", G - > numNodes, G - > numEdges); For (int I = 0; i< G->numNodes; i++) { getchar(); scanf("%c",&G->vexs[i]); } printf(" vertex data: \n"); for (i = 0; i<G->numNodes; i++) { printf("%c ",G->vexs[i]); } printf("\n"); //3. Initialize the adjacency matrix for(I = 0; i < G->numNodes; i++) for(j = 0; j < G->numNodes; j++) G->arc[i][j] = INFINITYC; //4. Input side table information for(k = 0; k < G->numEdges; K++){printf(" subscript I, subscript j, weight w\n" on input edge (vi,vj)); scanf("%d,%d,%d",&i,&j,&w); G->arc[i][j] = w; // If there is no digraph, the matrix is symmetric; G->arc[j][i] = G->arc[i][j]; } //5. Print the adjacency matrix for (int I = 0; i < G->numNodes; i++) { printf("\n"); for (int j = 0; j < G->numNodes; j++) { printf("%d ",G->arc[i][j]); } } printf("\n"); }Copy the code

4. The debugging

5. Disadvantages of adjacency matrix

1. In the figure above, there are 5 vertices but only one edge information;

2. In sequential storage, 5×5 two-dimensional array matrix space is required to store this edge information;

3. This leads to a large number ofWaste of space.

(2) chain storage – adjacency list

1. The adjacency list

1. Create oneOne dimensional vertex arrayStore vertex information;

2.Vertex arrayThe surviving element is oneThe node of vertex dataThe vertex has a pointer in its data structurePointing edge information.Edge informationIs aSingly linked list, this one-way linked list stores all vertices that are connected to verticesEdge information;

3. The one-way linked list of edge information stores the edge data between one vertex and other verticesThere is no sequential relationship.

2. Code implementation

Take the above example to realize the chain storage under the adjacency list

Define some state values and data types

#define M 100

#define true 1

#define false 0

typedef char Element;

typedef int BOOL;
Copy the code

2. Define nodes and storage structures

// typedef struct Node{int adj_vex_index; // The edge information corresponds to the subscript Element data in the array; Struct Node * next; }EdgeNode; // typedef struct vNode{Element data; EdgeNode * firstedge; // Who is next at the vertex? }VertexNode, Adjlist[M]; Typedef struct Graph{Adjlist Adjlist; Int arc_num; Int node_num; // Number of vertices BOOL is_directed; }Graph, *GraphLink;Copy the code

3. Storage implementation

void creatGraph(GraphLink *g){ int i,j,k; EdgeNode *p; Printf (" Input the number of vertices, edges, and direction? : \ n "); scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed); Printf (" Input vertex information: \n"); for (i = 0; i < (*g)->node_num; i++) { getchar(); scanf("%c", &(*g)->adjlist[i].data); (*g)-> adjList [I]. Firstedge = null; Printf (" Input side information: \n"); for (k = 0; k < (*g)->arc_num; k++){ getchar(); scanf("%d %d", &i, &j); P = (EdgeNode *)malloc(sizeof(EdgeNode)); // (p-> adj_VEX_index = j; I p->next = (*g)-> adjList [I]. [I]. Firstedge = p (*g)-> AdjList [I]. Firstedge = p; if(! (* g) - > is_directed) {/ / j -- -- -- -- -- > I / / (1) to create a new node p = (EdgeNode *) malloc (sizeof (EdgeNode)); // ip_vex_index = 1; P ->next = (*g)->adjlist[j]. [I]. Firstedge = p -> adjList [j]. Firstedge = p; }}}Copy the code

1. The inputThe number of vertices,Number of edges,Is it a directed graphInformation such as;

2.The verticesdepositA one-dimensional arrayThe one-dimensional array stores a bandData fieldsandPointer to the domainThe structure of,Data fieldsstorageVertex data.Pointer to the domainPointing to the storeEdge informationUnidirectional linked list;

3. Enter edge information. I is the currentVertex indicesJ isConnect the verticesIn the vertices arrayThe subscript;

4. After the inputCreate a node, record weight value, vertex subscript j, pointer field pointing, etc.

5. Determine if it isDirected graph, if it is an undirected graph, it is necessary to determine the relationship between j and the vertex pointed to by I, and create the relationship between j and I, namelyInverse relationship.

4. Traverse print

void putGraph(GraphLink g){ int i; Printf (" Store information in adjacency list :\n"); For (I = 0; i < g->node_num; i++) { EdgeNode * p = g->adjlist[i].firstedge; while (p) { printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data); p = p->next; } printf("\n"); }}Copy the code

5. Debugging

/* How many vertices, edges, and directed are stored in an adjacency list? : 4 5 0 Input vertex information: 0 1 2 3 Input edge information: 0 1 0 2 0 3 2 1 2 3 Store information in the adjacency list: 0 - > 3 - > 2 - > 1 0 0 1 - > 2 - > 2 - > 2 - > 3 0 1 2 3-2-3 - > > 0 > 0 * / / * adjacency graph table storage input vertex number, number of edges and has to? : 4 5 1 Input vertex information: 0 1 2 3 Input edge information: 1 0 1 2 2 1 2 0 0 3 Store information in the adjacency list: 0->3 1->2 1->0 2->0 2->1 */ GraphLink g = (Graph *)malloc(sizeof(Graph)); creatGraph(&g); putGraph(g);Copy the code

Undirected graph storage

Directed graph storage

Four,

1. The graph is computer dataLogical structureOne of them can be usedSequential storage, can also be usedChain store;

2. Sequential storage of graphsAdjacency matrixImplementation;

3. Use of link trial storage of graphsAdjacency listThe implementation.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

10– Storage of graphs and graphs

First, the basic knowledge of graphs

1. Definition of graph

2. Classification of graphs

Second, diagram storage

(1) sequential storage – adjacency matrix

1. Adjacency matrix

2. Code implementation

(2) chain storage – adjacency list

1. The adjacency list

2. Code implementation

Four,

10– Storage of graphs and graphs

First, the basic knowledge of graphs

1. Definition of graph

2. Classification of graphs

Second, diagram storage

(1) sequential storage – adjacency matrix

1. Adjacency matrix

2. Code implementation

(2) chain storage – adjacency list

1. The adjacency list

2. Code implementation

Four,

Related Posts

Localide: Personalize the appropriate map kernel as a guide

Swift Multithreading: Use Thread to communicate among multiple threads and coordinate sub-thread tasks

IOS low-level – Load analysis of categories