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 .
     Insert picture description here

  • 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 .

 Insert picture description here

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 .
     Insert picture description here

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 .
     Insert picture description here

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 .

 Insert picture description here

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
     Insert picture description here

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

 Insert picture description here

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 
}VNode,AdjList[MaxVertexNum];
typedef struct{

AdjList vertices; // Adjacency list 
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

 Insert picture description here

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)
     Insert picture description here
     Insert picture description here

版权声明:本文为[Uncle GUI]所创,转载请带上原文链接,感谢。 https://javamana.com/2021/12/202112122255024831.html