# 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 g-connected 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:

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

# Storage structure of graph

Logical structure of graph: many to many

• 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 two-dimensional array A.arcs[n][n], which is defined as:  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
int vexnum, arcnum;		//Current number of points and edges of a graph
```

Using adjacency matrix representation to create undirected network Algorithm idea:

1. Enter the total number of vertices and edges
2. Input the information of points in turn and store it in the vertex table
3. Initialize the adjacency matrix so that each weight is initialized to a maximum value
```//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

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;
}
```  • Vertex: stores vertex data in a one-dimensional 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 i-th 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
```

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:

1. Enter the total number of vertices and edges
2. 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
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;
}
```  1. 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 non-zero elements in a row
2. 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)
3. 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) 