# 11、 Notes on data structure of postgraduate entrance examination -- the basic concept of graph, the basic properties of graph and the storage structure of graph

Uncle GUI 2022-01-15 03:09:32 阅读数:881

notes data structure postgraduate entrance

# One 、 The basic concept of graph

## 1.1 Basic drawing terminology

• Directed graph ： The edge of a graph is a directed edge . Write it down as <v,w>： Directed edge from vertex v And vertex w Arc of . Express v Arctail ,w For the arc head .

• Undirected graph ： The edge of a graph is an undirected edge . Write it down as (v,w)： Undirected edges start from vertices v And vertex w Arc of .v,w Both represent vertices . • Simple picture ：① There are no duplicate edges There is no vertex to its own edge

• Complete graph Undirected graph in , There must be an edge between every two vertices . Directed graph in , There are two arcs in opposite directions in every two vertices

• Subgraphs ： Is part of a whole picture , But the subgraph must also be a graph . And that is, edges and vertices need to appear together . ## 1.2 On the properties of degree

• Undirected graph A few sides are just a few degrees （ The sum of the degrees of all vertices is equal to twice the number of edges ）d=2e
• Directed graph The degree of a vertex = Out of degree + Degrees （ Degrees of all vertices = All vertices are out of degrees + The degree of ）

## 1.3 About path and distance

• route ： A sequence of vertices from one vertex to another .（ The sequence of points passed ）
• The length of the path The number of edges on the path .
• loop / Ring ： The same path from the first vertex to the last vertex .
• distance ： from If there is a shortest path from one vertex to another , The path length is called distance .
• Simple path Path where vertices do not appear repeatedly .
• Simple circuit A loop that does not recur .

## 1.4 On connected graphs and connected components

This concept is for undirected graphs

• connected ： From the top v To the top w There is a path , be v and w It's connected
• Connected graph ： chart G in , Any two vertices are connected , It is called a connected graph . The number of sides is greater than or equal to n-1.
• Connected component ： In an undirected graph, a polar connected subgraph becomes a connected component .
• The picture of Tongzi in polar Dalian ： Is the connected component . Subgraphs contain as many vertices and edges as possible .
• Minimal connected subgraph ： The least number of sides , Graph and connected subgraph .
• Unconnected graph ： The picture shows n vertices , The number of sides is less than n-1, Then it is a non connected graph . ## 1.5 On strongly connected graphs and strongly connected components

This concept is for directed graphs

• Strong connectivity ： From the top v To the top w And from vertex w To the top v There are paths between .
• Strongly connected graph ： Any vertex in a graph is strongly connected .
• Strong connected components ： Maximal strongly connected subgraphs in digraphs . ## 1.6 Make trees , Make forests

• The spanning tree of a connected graph is a minimal connected subgraph containing all vertices in the graph .
• If the number of vertices of a graph is n, Then its spanning tree contains n-1 side .
• If this tree Cut off an edge , Become a non connected graph ; This tree Adding an edge becomes a loop .
• In a non connected graph , The spanning tree of connected components becomes the spanning forest of unconnected graphs . ## 1.7 Classic example

• Be sure to remember the two formulas of the number of edges of a complete graph of a directed graph and an undirected graph # Two 、 Figure of the storage

## 2.1 adjacency matrix

• Concept
• use A one-dimensional array stores vertex information in a graph . A two-dimensional array stores information about edges （ The adjacency relationship between vertices ）
``````#define MaxVertexNum 100 // Maximum number of vertices
typedef char VertextType; // The data type of the vertex
typedef int EdgeType; // Weights and data types in weighted graphs
typedef struct{

VerTexTyoe Vex[MaxVertexNum]; // Vertex table
EdgeType Edge[MaxVertexNum][MaxVertexNum];// Adjacency matrix , Side table
int vexnum,arcnum;// The current vertex and arc number of a graph
}MGraph;
``````
• nature
• The space complexity of the adjacency matrix representation is O(n²),n For the top points }|V|
• Undirected graph In the adjacency matrix of Rows or columns represent the degrees of vertices
• Directed graph In the adjacency matrix of Lines indicate degrees , List penetration . The degree of a digraph is equal to the degree of a digraph by adding degrees
• The time complexity of adjacency matrix is related to the number of vertices .
• Dense graphs are suitable for adjacency matrices ,
• The relationship between calculation degree and edge finding must be traversed ## 2.2 Adjacency table method

• Concept
• It mainly consists of two parts , Vertex table and Side table .
• Side table ： A vertex to which a vertex is attached . Instant output
• Vertex table ： All vertices in a graph .
``````#define MaxVertexNum 100
typedef struct ArcNode{
// The maximum number of vertices in a graph
int adjvex; // Side table node
struct ArcNode *next;// The position of the vertex to which the arc points
}ArcNode;
typedef struct VNode{
// Vertex table node
VerTexTyoe data;// Vertex information
ArcNode *first; // Pointer to the first arc attached to the vertex
typedef struct{

int vexnum,arcnum;// The number of vertices and arcs of a graph
}ALGraph;
``````
• nature
• if Undirected graph , The storage space is O(V +2E); if Directed graph , The storage space is O(V+E). （ An undirected graph needs to store two edges ）
• Given a vertex in the adjacency table , It's easy to find , But the penetration is very complex . The time spent is O(n)
• The adjacency table representation of a graph is not unique , Because each vertex corresponds to a single linked list , The link order of each edge node can be arbitrary .
• Suitable for sparse graphs ## 2.3 Cross linked list method （ Less examination ）

• The cross linked list is A chain storage structure of a directed graph . For a directed graph, each arc has a node , For each vertex, there is a node .

## 2.4 Adjacency multiple tables （ Less examination ）

• Adjacency multiple tables are Undirected graph Another chain storage structure .

# 3、 ... and 、 The basic concept and storage of the chart, common test points

• contain n A vertex and e In the adjacency matrix of an undirected graph with edges , The number of zero elements is n²-2e

• A graph of Adjacency matrix represents unique , Adjacency tables represent not unique

• Adjacency list Yes Odd number of edge table nodes , Then the graph is a directed graph

• In the adjacency table storage structure of directed graph , The vertices v The number of occurrences in the edge table is vertex v The degree of

• n The adjacency table of an undirected graph with vertices has at most n(n-1) An edge table node . A vertex n individual n-1 Side table

• n vertices ,e A directed graph with edges is represented by an adjacency table , Delete a vertex v The complexity of all related edges is O(n+e)  