5. Figure
5.1 Basic concepts of diagrams
Graph: A graph consists of a finite, nonempty set V and a set E of edges.
You can have no edges, but you need at least one vertex.
Mark of graph:
Undirected graph:
Concept: Each edge has no direction
The degree ofAnd:The verticesThe relevantOn the edge of a number 
Undirected complete graph: in the figureAny two verticesbetweenThere are side. namely
1. In an undirected graph, a path exists between any two vertices in the graph (connected).
The maximally connected subgraph of a graph (that is, the subgraph of G resulting from any addition of nodes or edges in G is no longer connected) is called the connected component.
Directed graph:
Concept: Each edge isHave a direction, indicated by 1 pointing to 2
The degree ofBy:That vertex emitstheOn the edge of a number
The degree of:Point to that vertextheOn the edge of a number
Directed complete graph: in the figureAny two verticesbetweenThere are two arcs in opposite directions. namely
3. In a directed graph, there are paths between any pair of vertices in the graph (strongly connected).
The extremely strongly connected subgraph is called the strongly connected component
Subgraph: Not all subsets of points and edges can form a subgraph.
Spanning tree: A minimal connected subgraph containing all the vertices of a graph.
A ring with n vertices has n spanning trees.
Path and path length: The length of the path is the number of edges on the path
Simple path: a path where vertices do not recur
Loop: a path in which the first vertex is the same as the last
Loop (loop) judgment mode: depth first traversal
A topological sort
Critical path (Prerequisite topology sort)
Dense graph: graph with many edges Sparse graph: graph with few edges
Properties of a graph with n vertices:
| The minimum number of edges with a ring | The number of edges of the ring | |
|---|---|---|
| Undirected graph | 3 | n |
| Directed graph | 2 | n |
| The minimum number of (strongly) connected edges | Number of edges that must be strongly connected | |
| Undirected graph | N – 1 (tree) |  |
| Directed graph | N (ring) | (n-1)(n-2)+1 |
5.2 Storage structure of figure
5.2.1 Adjacency matrix
The structural form of the adjacency matrix is defined as follows
typedef struct {
int no; // Vertex number
char info; // Vertex information
}VertexType; // Vertex type
typedef struct{
int edges[maxsize][maxsize]; // Adjacency matrix definition
int N,E; //N number of points E number of edges
VertexType vex[maxsize]; // Store node information
}MGraph;
Copy the codeUndirected graph:
The adjacency matrix is symmetric.
The first IlineThe number of non-zero elements equals the I ‘thcolumnElements and =
Directed graph:
The first IlinetheNon-zero elementThe number and =
The first IcolumntheNon-zero elementThe number and =
The adjacency matrix of an undirected graph is a symmetric matrix
Adjacency matrix means unique.
5.2.2 adjacency table
The structural type is defined as follows:
typedef struct ArcNode{
int adjvex; // The position of the node pointed to
struct ArcNode *nextArc; // The pointer to the next edge
int info; // Information about the edge
}ArcNode; // Edge definition
typedef struct{
char data; // Vertex information
ArcNode *firstarc; // The pointer to the first edge to which this vertex points
}VNode; / / the vertices
typedef struct{
VNode adjlist[maxsize];
int n,e;
}AGraph; // Graph definition
Copy the codeDirected graph:
Output: the number of nodes
Inbound: The adjacency list needs to be traversed
The adjacency list representation of a graph is not unique.
| Adjacency matrix | Adjacency matrix | Adjacency list | Adjacency list | |
|---|---|---|---|---|
| Undirected graph | Directed graph | Undirected graph | Directed graph | |
| features | Symmetric matrices | |||
| The degree of | I row (column) and | ilineand | Side table number | Side table number |
| The degree of | I row (column) and | icolumnand | Side table number | The edge table node is the sum of I |
| Number of edges | The number of ones over 2 | 1 the number of | Number of edges divided by 2 | Number of edge nodes |
| Edge is connected |  |
|
Side table | Side table |
| Spatial complexity | $O( | V | ^ 2) $ | $O( |
| apply | Dense figure | Dense figure | Thin figure | Thin figure |
5.3 Figure traversal calculation method operation
Graph traversal means that all vertices are visited once and only once, starting from one vertex in the graph (a non-connected graph may not have enough vertices to access all of them), according to some search method.
5.3.1 Breadth-first Traversal (BFS)
Breadth-first traversal is not a recursive algorithm
Methods:
1. Put the root node into the queue first
2. Remove the first node from the queue and verify that it is the target
* If the target is found, the search ends and the results are returned
* Otherwise, queue all of its immediate children that have not yet been verified
3. If the queue is empty, the entire table is checked
The algorithm using adjacency list as storage structure is as follows:
int visit[maxsize];
void BFS(AGraph *G,int v)
{
ArcNode *p;
int que[maxsize],front=0,rear=0;
int j;
visit[v] = 1;
Visit(v);
rear = (rear+1)%maxsize;
que[rear] = v; / / V team
while(front! =rear) { front = (front+1)%maxsize;
j = que[front]; // Get out of line
p = G->adjlist[j].firstarc;
while(p! =NULL)
{
if(visit[p->adjvex]==0)
{
visit[p->adjvex] = 1; // Adjacency vertex access joins the queue
Visit(p->adjvex);
rear = (rear+1)%maxsize; que[rear] = p->adjvex; } p=p->nextarc; }}}void bfs(AGraph *g)
{
int i;
for(i=0; i<g->n; i++)if(visit[i]==0)
BFS(g,i);
}
Copy the codeBFS algorithm can be used to solve the single source shortest path problem of graphs with equal weights.
Breadth-first spanning tree:
The breadth-first spanning tree of a graph represented by an adjacency matrix is unique.
The breadth-first spanning tree of a graph represented by an adjacency list is not unique.
5.3.2 Depth-first Traversal (DFS)
Depth-first search is a recursive algorithm
// The recursive algorithm is as follows:
int visit[maxsize];// Global variables mark arrays
void DFS(AGraph *G,int v) // traversal from node V
{
AGraph *p;
visit[v] = 1; // set the visited flag
Visit(v); // Access the node
p = G->adjlist[v].firstarc; // points to the first edge of vertex V
while(p! =NULL)
{
if(visit[p->adjvex]==0) // If it is not accessed, it is accessed recursively
DFS(G,p->adjvex);
p = p->nextarc; // Continue next}}// The recursive algorithm with the adjacency matrix as the storage structure is as follows:
int visit[maxsize];// Global variables mark arrays
void DFS(MGraph *G,int v) // traversal from node V
{
visit[v] = 1; // set the visited flag
Visit(v); // Access the node
int i;
for(i=0; i<G->n; i++) {if(G->adges[v][i]>0 && visit[i]==0) DFS(G,i); }}Copy the codeThe non-recursive algorithm with adjacency list as storage structure is as follows:
int visit[maxsize];
void DFS(AGraph *G,int v)
{
AGraph *p;
int j;
int stack[maxsize],top; // This stack is used to hold nodes temporarily
top = - 1;
stack[++top] = v; // Start node is pushed
while(top! =- 1)
{
j = stack[top--]; // Remove the top node
visit[j] = 1;
Visit(j);
p = G->adjlist[j].firstarc;
while(p! =NULL)
{
if(visit[p->adjvex]==0)
stack[++top] = p->adjvex; p = p->nextarc; }}}void dfs(AGraph *g)
{
int i;
for(i=0; i<g->n; i++)if(visit[i]==0)
DFS(g,i);
}
Copy the codeDFS is used to solve the problem of loop existence in the graph:
Undirected graph: there must be a loop in the process of DFS.
<<<<<<< HEAD
// The adjacency list is stored as follows:
int visit[maxsize];
void BFS(AGraph *G,int v)
{
ArcNode *p;
int que[maxsize],front=0,rear=0;
int j;
visit[v] = 1;
Visit(v);
rear = (rear+1)%maxsize;
que[rear] = v; / / V team
while(front! =rear) { front = (front+1)%maxsize;
j = que[front]; // Get out of line
p = G->adjlist[j].firstarc;
while(p! =NULL)
{
if(visit[p->adjvex]==0)
{
visit[p->adjvex] = 1; // Adjacency vertex access joins the queue
Visit(p->adjvex);
rear = (rear+1)%maxsize; que[rear] = p->adjvex; } p=p->nextarc; }}}void bfs(AGraph *g)
{
int i;
for(i=0; i<g->n; i++)if(visit[i]==0)
BFS(g,i);
}
// The adjacency matrix is stored as follows:
int visit[maxsize];
void BFS(MGraph *G,int v)
{
int que[maxsize],front=0,rear=0;
int j;
visit[v] = 1;
Visit(v);
rear = (rear+1)%maxsize;
que[rear] = v; / / V team
while(front! =rear) { front = (front+1)%maxsize;
j = que[front]; // Get out of line
for(int i=0; i<G->n; i++) {if(G->adges[j][i]>0&&visit[i]==0)
visit[i] = 1; // Adjacency vertex access joins the queue
Visit(i);
rear = (rear+1)%maxsize; que[rear] = i; }}}Copy the code======= digraph: A ring exists if the node is encountered before the end of a traversal starting at a node.
DFS iterates over an acyclic directed graph, printing its inverse topological ordered sequence when exiting recursion (exiting recursion is inverse because of its stack nature, otherwise not inverse)
Depth-first spanning tree:
The depth-first spanning tree of a graph represented by an adjacency matrix is unique.
The depth-first spanning tree of a graph represented by an adjacency list is not unique.
5.3.3 SUMMARY of DFS and BFS
| Corresponding to tree traversal | With the help of a structure | Time complexity | Spatial complexity | |
|---|---|---|---|---|
| Extensive search (BFS) | Level traversal | The queue | Adjacency matrix: $O( | V |
| Deep search (DFS) | The first sequence traversal | The stack | Adjacency matrix: $O( | V |
For the same graph, the DFS sequence and BFS sequence obtained by traversal based on adjacency matrix are unique, while the sequence obtained by traversal of adjacency list is not unique (the specific physical storage structure is unique).
Undirected graph: connected: Starting from any node, all nodes can be traversed only once.
Unconnected: a node traverses only the vertices of its connected components.
Directed graph: Strongly connected: any node can start traversing all nodes at once.
Non-strongly connected: any node cannot traverse its connected component at one time. (If it is a strongly connected component, the strongly connected component can be traversed)
Label method is used to determine whether the traversal sequence is valid.
Depth-first SPANNING tree height >= Breadth-first spanning tree height
5.4 Minimum cost spanning tree
(Prim’s algorithm and Koruska’s algorithm are both for undirected graphs.)
Minimum spanning tree:
A minimum spanning tree is a minimal connected subgraph (not connected component) of a graph, which contains all vertices in the graph and contains as few edges as possible. If one edge is cut, it becomes an unconnected graph. If an edge is added, a loop is formed.
Properties:
1. The minimum spanning tree is not unique. It is unique only when the weights of each edge are not equal.
Or they have equal edges, but the edges with equal weights are incorporated into the graph of the spanning tree during the construction of the minimum spanning tree
2. The sum of weights of the minimum spanning tree is always unique.
3. The minimum number of spanning tree edges is the number of vertices minus one.
4. If (u,v) is an edge with minimum weight, where
5.4.1 Prim algorithm (point method) :
Adjacency matrix is used as storage structure
void Prim(MGraph g,int v0,int &sum)
{
int lowcost[maxsize],vset[mexsize],v;
int i,j,k,min;
v = v0;
for(i=0; i<g.n; i++)// Initialize the lowcost array
{
lowcost[i] = g.edges[v0][i];
vset[i] = 0;
}
vset[v] = 1; // merge V0 into the tree
sum = 0; //sum is used to accumulate the weights of the tree
for(i=0; i<g.n- 1; i++) { min = INF;// Select the minimum value of the candidate edge
for(j=0; j<g.n; j++) {if(vset[j]==0&&lowcost[j]<min)
{
min = lowcost[j];
k = j;
}
}
v = k;
sum += min; // The minimum spanning tree weight is recorded
// Update candidate edges
for(j=0; j<g.n; j++) {if(vset[j]==0&&g.edges[v][j]<lowcost[j]) lowcost[j] = g.edges[v][j]; }}}Copy the code5.4.2 Koruska Algorithm (Edge method) :
Algorithm idea: select the edge with the lowest weight (and detect whether the edge’s incorporation will cause a loop) and merge the edge into the current spanning tree
Code implementation: (to use and look up the set)
It’s also done with the adjacency matrix
typedef struct
{
int a,b; // Two vertices attached to an edge
int w; // The weight of an edge
}Road; // Edge definition
Road road[maxsize];
int v[maxsize]; // declare and check the set number group
int getRoot(int a) // Find the function on the root node in the set
{
while(a! =v[a]) a = v[a];return a;
}
void Kruskal(MGraph g,int &sum,Road road[]) // The incoming road array already contains path information
{
int i;
int N,E,a,b;
N = g.n; E = g.e;
sum = 0; // Initialize zeroing
// Check the initialization of the set
for(i=0; i<N; i++) v[i] = i; sort(road,E);// Order E edges in road array from smallest to largest in weight
for(i=0; i<E; i++) { a = getRoot(road[i].a); b = getRoot(road[i].b);if(a! =b)// The incorporation of this edge does not result in a ring{ v[a] = b; sum+=road[i].w; }}}Copy the code5.5.3 summary
| Time complexity | Scope of application | |
|---|---|---|
| Prim | $O( | V |
| Kruskal | $O( | E |
5.5 Shortest Path
Equally weighted graphs or unauthorized graphs can be searched using breadth-first.
Weighted graphs can be solved in the following two ways.
The shortest path between two points also contains the shortest path between other vertices on the path. (Dynamic programming: Optimal substructure)
5.5.1 Dijkstra Algorithm (Single-source Shortest Path)
Algorithm idea: Two vertices S (has to find the shortest path of vertex) T (the shortest path of vertex) was not found in the initial S contains only the initial vertex where v0 then continuously from the selected from the set T to the shortest path length where v0 vertex Vu into S in S each into a new vertex to modify where v0 to set T of each vertex in the shortest path length value This process is repeated until T is empty
Algorithm implementation
Again, by the adjacency matrix
void Dijkstra(MGraph g,int v,int dist[],int path[])
{
int set[maxsize];
int min,i,j,u;
// Initialize each array
for(i=0; i<g.n; i++) { dist[i] = g.edges[v][i];set[i] = 0;
if(g.edges[v][i]<INF)
path[i] = v;
else
path[i] = - 1;
}
set[v] = 1; path[v] =- 1; // add V to the set array
for(i=0; i<g.n- 1; i++) { min = INF;// The path to this point is shortest among the remaining vertices
for(j=0; j<g.n; j++) {if(set[j]==0&&dist[i]<min) { u = j; min = dist[j]; }}set[u] = 1; // Add the shortest path
/ / update the dist
for(j=0; j<g.n; j++) {if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j]) { dist[j] = dist[u]+g.edges[u][j]; path[j] = u; }}}}// Prints the shortest path
void PrintPath(int path[],int a) // The shortest path from V to a
{
int stack[maxsize],top = - 1;
while(path[a]! =- 1)
{
stack[++top] = a;
a = path[a];
}
stack[++top] = a;
while(top! =- 1)
print(stack[top--]);
}
Copy the code5.5.2 Freudian algorithm
// The algorithm idea is as follows: using the adjacency matrix implementation
//1) set the adjacency matrix of the graph to A and set all elements in Path to -1
//2) select vertex K (K = 0~n-1) as intermediate vertex and modify all vertices in the graph as follows:
// if A[i][j]>A[i][k]+A[k][j]
// {
// A[i][j] = A[i][k]+A[k][j];path[i][j] = k
/ /}
// do nothing else;
void Floyd(MGraph h,int Path[][maxsize])
{
int i,j,k;
int A[maxsize][maxsize];
for(i=0; i<g.n; i++)/ / initialization
for(j=0; j<g.n; j++) { A[i][j] = g.edges[i][j]; Path[i][j] =- 1;
}
// check all vertex pairs with K as the intermediate node
for(k=0; k<g.n; k++)for(i=0; i<g.n; i++)for(j=0; j<g.n; j++)if(A[i][k]+A[k][j]<A[i][j]) { A[i][j] = A[i][k]+A[k][j]; Path[i][j] = k; }}// The path print algorithm
void PrintPath(int u,int v,int Path[][maxsize]) // Outputs the shortest path sequence from U to V
{
if(Path[u][v] == - 1) //U to V has direct vertices
{
cout<<"("<<u<<","<<v<<")"< <; }else
{
intmid = Path[u][v]; PrintPath(u,mid,Path); PrintPath(mid,v,Path); }}Copy the code5.5.3 summary
| To solve the problem | Time complexity | Scope of application | |
|---|---|---|---|
| Dijkstra | Single source shortest path | $O( | V |
| Floyd | Shortest path to each vertex | $O( | V |
5.6 Topology Sorting
AOV net: In short, a net that is active at the vertex
Topological ordering exists: the necessary condition is that the directed graph is acyclic, or that there is no strongly connected component with vertices greater than 1.
The sufficient condition is that the adjacency matrix of the digraph is triangular matrix.
Topological ordered sequences exist only if the adjacency matrix is triangular
Multiple styles of graphs can be determined based on unique topological sorting.
The core algorithm of topological sorting :(similar in the real problem)
// Algorithm idea:
// 1) Select a vertex output with zero input from the directed graph
// 2) Delete the vertex and delete all edges starting from the vertex
// 3) Repeat the previous two steps until there are no vertices without a precursor in the remaining graph
// Adjust the adjacency table header structure accordingly
typedef struct
{
char data;
int count; //count is used to count inputs
ArcNode *firstarc;
}VNode;
// use the adjacency list storage structure
int TopSort(AGraph *G)
{
int i,j,n=0;
int stack[maxsize],top=- 1;
ArcNode *p;
for(i=0; i<G->n; i++)// Push vertices with zero entry degree to the stack
if(G->adjlist[i].count==0)
stack[++top] = i;
while(top! =- 1)
{
i = stack[top--]; // Vertex unstack
++n;
cout<<i<<endl;
p = G->adjlist[i].firstarc;
while(p! =NULL)
{
j = p->adjvex;
--(G->adjlist[j].count);
if(G->adjlist[j].count==0)
stack[++top] = j; p = p->nextarc; }}if(n==G->n) // Topology sort succeeded
return 1;
else // Topology sort failed
return 0;
}
// use the adjacency matrix storage structure
int TopSort(MGraph *G)
{
int i,j,n=0;
int stack[maxsize],top=- 1;
for(i=0; i<G->n; i++)// Push vertices with zero entry degree to the stack
if(G->vex[i].count==0)
stack[++top] = i;
while(top! =- 1)
{
i = stack[top--]; // Vertex unstack
++n;
cout<<i<<endl;
for(j=0; j<G->n; j++) {if(G->edges[i][j]>0)
{
G->vex[j].indegree--;
if(G->vex[j].indegree==0)
{
stack[++top] = j; }}}}if(n==G->n) // Topology sort succeeded
return 1;
else // Topology sort failed
return 0;
}
// Topologically sorted sequences may not be unique
Copy the codeThe method of finding the inverse topological sequence is similar… In addition, the sequence of vertices recorded according to the sequence of the DFS algorithm (i.e. the sequence of the vertices exiting the system stack) is the reverse topological ordered sequence
The algorithm complexity of topological sorting is O(n+ E).
(Focus on the process of manual topology sorting)
5.7 Critical Path
AOE net: a net that is active on the side
In AOE network, the path with the maximum path length is called critical path.
The critical path represents both the longest path and the shortest time to complete the project
Activities on the critical path are critical activities, and critical activities must be on the critical path.
Critical paths in the network are not unique, and time can be reduced only by accelerating activity on all critical paths.
The specific steps are as follows:
1) Topological ordered sequence A and inverse topological ordered sequence B are calculated according to the figure
2) Calculate the earliest occurrence time according to sequence A
Calculate the latest occurrence time according to sequence B
3) Find the earliest and latest time of each activity
4) Identify the activities that occur at the same time as the earliest and the latest are critical activities. The path composed of critical activities is critical activities