Definitions and basic terms of drawings
Figure: G=(V, E) Grapg = (Vertex, Edge)
V: finite non empty set of vertices (data elements);
E: finite set of edges
Undirected graph: each edge is undirected
Directed graph: each edge has a direction
Complete graph: any two points have an edge connected
Sparse graph: a graph with few edges or arcs (e < nlogn)
Dense graph: a graph with many edges or arcs
Net: edge / arc weighted graph
Adjacency: the relationship between two vertices connected by edges / arcs
exists (vi, vj), then vi and vj are called adjacent points to each other;
if there is < vi, vj >, it is said that vi is adjacent to vj, and vj is adjacent to vi
Association (attachment): relationship between edge / arc and vertex
Degree of vertex: the number of edges associated with the vertex, recorded as TD(v)
In a directed graph, the degree of a vertex is equal to the sum of the in and out degrees of the vertex
The penetration of vertex v is the number of directed edges focusing on V, which is recorded as ID(v)
The outgoing degree of vertex v is the number of directed edges with V as the starting point, which is recorded as OD(v)
Path: a sequence of vertices formed by successive edges
Path length: the sum of the number / weight of edges or arcs on the path
Loop (loop): the first vertex and the last vertex are the same path
Simple path: a path with different vertices except for the same starting point and ending point of the path
Connected graph (strongly connected graph)
in the directed graph G = (v, {E}), if there is a path from v to u for any two vertices v and u, then G is a connected graph (strongly connected graph)
Rights and networks:
the correlation number of edges or arcs in a graph is called weight, which indicates the distance or cost from one vertex to another; A weighted graph is called a net
Subgraph:
let g = (V, {e}) and G1 = (V1, {E1}). If V1 ⊆ V and E1 ⊆ e, G1 is said to be a subgraph of G
Connected component (strong connected component)

The polar connected subgraph of undirected graph G is called the connected component of G
Polar Dalian connected subgraph means that the subgraph is a gconnected subgraph. By adding any vertex of G that is not in the subgraph, the subgraph is no longer connected

The maximal strongly connected subgraph of a directed graph G is called the strongly connected component of G
Maximal strongly connected subgraph means that the subgraph is a strongly connected subgraph of G. by adding any vertex of D that is not in the subgraph, the subgraph is no longer strongly connected
Minimal connected subgraph: the subgraph is a connected subgraph of G. if any edge is deleted from the subgraph, the subgraph is no longer connected
Spanning tree: a minimal connected graph containing all vertices of undirected graph G
Spanning forest: for a non connected graph, a set of spanning trees composed of each connected component
Type definition of graph
The abstract data type of the diagram is defined as follows:
ADT Graph{
data object V: a collection of data elements with the same characteristics, which is called vertex set
data relation R: R = {VR}
VR = {<v,w><v,w> v,w∈V ^ p(v,w)，
< v, w > represents the arc from v to W, and p(v,w) defines the information of arc < v, w >
}
CreateGraph(&G, V, VR)
initial condition: V is the vertex set of the graph, and VR is the set of arcs in the graph
operation result: construct diagram G according to the definition of V and VR
DFSTraverse(G)
initial condition: figure G exists
operation result: depth first traversal according to the figure
BFSTraverse(G)
initial condition: figure G exists
operation result: breadth first traversal of the graph
}ADT Graph
Storage structure of graph
Logical structure of graph: many to many
Array (adjacency matrix representation)
 Establish a vertex table (recording the information of each vertex) and an adjacency matrix (representing the relationship between each vertex)
 Let graph A = (V,E) have n vertices, then
 The adjacency matrix of the graph is a twodimensional array A.arcs[n][n], which is defined as:
 Let graph A = (V,E) have n vertices, then
Analysis 1: the adjacency matrix of undirected graph is symmetric
Analysis 2: degree of vertex i = number of 1 in row I (column)
In particular: in the adjacency matrix of a complete graph, the diagonal elements are 0 and the rest are 1
Note: in the adjacency matrix of a directed graph,
meaning of line I: arc with node vi as tail (i.e. outgoing edge)
meaning of column I: arc with node vi as the head (i.e. in degree edge)
Analysis 1: the adjacency matrix of a directed graph may be asymmetric
Analysis 2: vertex exit = sum of elements in line i
penetration of vertex = sum of elements in column i
degree of vertex = sum of elements in row i + sum of elements in column i
Adjacency matrix representation of weighted graph
Storage representation of adjacency matrix: two arrays are used to store vertex table and adjacency matrix respectively
#define MaxInt 32767 // Represents the maximum value, i.e. ∞ #define MVNum 100 // max vertex typedef char VerTexType; //Set the data type of vertex to character type typedef int ArcType; //It is assumed that the weight type of the edge is integer typedef struct{ VerTexType vexs[MVNum]; //Vertex table ArcType arcs[MVNum][MVNum]; //adjacency matrix int vexnum, arcnum; //Current number of points and edges of a graph }AMGraph; // Adjacency Matrix Graph
Using adjacency matrix representation to create undirected network
Algorithm idea:
 Enter the total number of vertices and edges
 Input the information of points in turn and store it in the vertex table
 Initialize the adjacency matrix so that each weight is initialized to a maximum value
 Construct adjacency matrix
//The adjacency matrix representation is used to create undirected network G Status CreateUDN(AMGraph &G){ cin >> G.vexnum >> G.arcnum; //Enter the total number of vertices and edges for(i = 0; i < G.vexnum; ++i) cin >> G.vexs[i]; //Enter the information of the points in turn for(i = 0; i < G.vexnum; ++i) //Initialize adjacency matrix for(j = 0; j < G.vexnum; ++j) G.arcs[i][j] = MaxLnt; //The weights of the edges are set to the maximum //Construct adjacency matrix for(k = 0; k < G.arcnum; ++k){ cin >> v1 >> v2 >> w; //Enter the vertex to which an edge is attached and the weight of the edge i = LocateVex(G, v1); j = LocateVex(G ,v2); //Determine the position of v1 and v2 in G G.arcs[i][j] = w; //The weight of edge < V1, V2 > is set to w G.arcs[j][i] = G.arcs[i][j]; //Set the weight of the symmetrical edge < V2, V1 > of < V1, V2 > to w } return OK; }//CreateUDN
Supplementary algorithm: find vertices in the graph
//Find the vertex u in graph G, and return the subscript in the vertex table if it exists; Otherwise  1 is returned int LocateVex(AMGraph G, VertexType u){ int i; for(i = 0; i < G.vexnum; ++i) if(u == G.vexs[i]) return i; return 1; }
Adjacency table
Adjacency list representation (chain)
 Vertex: stores vertex data in a onedimensional array in numbered order
 Edges associated with the same vertex (arc with vertex as tail): stored in a linear linked list
Undirected graph
characteristic:
 Adjacency table is not unique
 If there are n vertices and e edges in an undirected graph, the adjacency table needs n head nodes and 2e table nodes. Suitable for storing sparse graphs
 The degree of vertex vi in undirected graph is the number of nodes in the ith single linked list
Directed graph
characteristic:
 The ith vertex of vi is the number of vertices in the list
 The penetration of vertex vi is the number of nodes in the whole single linked list whose adjacent point field value is i  1 (the whole linked list needs to be traversed)
characteristic:
 The penetration of vertex vi is the number of nodes in the ith single linked list
 The outgoing degree of vertex vi is the number of nodes in the whole single linked list whose adjacent point field value is i  1 (the whole linked list needs to be traversed)
Adjacency table storage representation of graph
typedef struct VNode{ VerTexType data; //Vertex information ArcNode * firstarc; //Pointer to the first edge attached to the vertex }VNode, AdjList[MVNum] //AdjList indicates the adjacency table type
Description: for example, AdjList v; equivalent to: VNode v[MVNum];
#define MVNum 100 // max vertex typedef struct ArcNode{ //Edge node int adjvex; //The position of the vertex that the edge points to struct ArcNode * nextarc; //Pointer to the next edge OtherInfo info; //Information domain; Store edge related information }ArcNode;
Structure definition of drawing:
typedef struct{ AdjList vertices; //Vertices  the plural of vertex int vexnum, arcnum; //Current vertex number and arc number of graph }ALGraph;
Using adjacency table representation to create undirected network
Algorithm idea:
 Enter the total number of vertices and edges
 Create vertex table
Input the information of points in turn and store it in the vertex table
Initialize the pointer field of each header node to NULL  Create adjacency table
Enter the two vertices to which each edge is attached in turn
Determine the sequence numbers i and j of the two vertices and establish the edge node
Insert this edge node into the head of the two edge linked lists corresponding to vi and vj respectively
//Using adjacency table representation, undirected graph G is created Status CreateUDG(ALGraph &G){ cin >> G.vexnum >> G.arcnum; //Enter the total number of vertices and edges for(i = 0; i < G.vexnum; ++i){ //Input each point to construct the header node table cin >> G.vertices[i].data; //Enter vertex value G.vertices[i].firstarc = NULL; //Initializes the pointer field of the header node }//for for(k = 0; k < G.arcnum; ++k){ //Input each edge to construct the adjacency table cin >> v1 >> v2; //Enter the two vertices to which an edge is attached i = LocateVex(G, v1); j = LocateVex(G, v2); p1 = new ArcNode; //Generate a new edge node * p1 p1 > adjvex = j; //The serial number of adjacent points is j p1 > nextarc = G.vertices[i].firstarc; G.vertices[i]firstarc = p1; //Insert the new node * p1 into the edge table header of vertex vi p2 = new ArcNode; //Generate another symmetrical new edge node * p2 p2 > adjvex = i; //The number of adjacent points is i p2 > nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2; //Insert the new node * p2 into the edge table header of vertex vj }//for return OK; }
Relationship between adjacency matrix and adjacency table representation
 Connection: each linked list of adjacency list corresponds to a row in the adjacency matrix. The number of nodes in the linked list is equal to the number of nonzero elements in a row
 difference:
① For any definite undirected graph, the adjacency matrix is unique (the row and column number is consistent with the vertex number), but the adjacency table is not unique (the link order is independent of the vertex number)
② The spatial complexity of adjacency matrix is O(n2), while the spatial complexity of adjacency table is O(n+e)  Usage: adjacency matrix is mostly used for dense graphs; Adjacency tables are mostly used in sparse graphs
Cross linked list  for directed graphs
orthogonal list is another linked storage structure of directed graph, which can be regarded as a linked list formed by the combination of adjacent list and inverse adjacent list of directed graph
each arc in a directed graph corresponds to an arc node in the cross linked list, and each vertex in a directed graph corresponds to a node in the cross linked list, which is called a vertex node
Adjacency multiple list (another chain storage structure of undirected graph)
Advantages of adjacency table: it is easy to obtain the information of vertices and edges
disadvantages: some operations are inconvenient (for example, to delete an edge, you need to find two nodes representing the edge)
Adjacency multiple table: