As an important concept in data structures, graphs play a role in connecting the world. Compared with trees and binary trees, graphs are more flexible and diverse. They can describe complex relationships in various practical problems, such as interpersonal connections in social networks, route planning in urban transportation, and communication paths in electronic networks.
Whether you are a beginner or an advanced person, this article will provide you with simple, easy-to-understand, practical and feasible knowledge points to help you better grasp the importance of graphs in data structures and algorithms, thereby improving your algorithmic problem-solving capabilities. Next, let us embark on a wonderful journey of data structures and algorithms.
Table of Contents
Basic concepts of graphs
Storage representation of graph
Basic operations on graphs
Graph Traversal and Connectivity
minimum spanning tree
shortest path problem
critical path problem
Basic concepts of graphs
A graph is a nonlinear data structure consisting of a set of vertices (nodes) and the edges (relationships) connecting these vertices. Graphs are used to represent the relationships between elements and describe the connections between elements in the graph through nodes and edges.
The definition of a graph includes the following elements
Vertices: Nodes in a graph represent entities or objects, usually represented by circles or boxes. Each node can contain some relevant information, such as name, attributes, etc.
Edge: The edge in the graph represents the relationship between vertices and is used to connect different vertices. Edges can be directed (arrows indicate direction) or undirected (no arrows), or they can be weighted (indicating the edge’s weight).
Adjacent points: For a vertex, the vertices directly connected to it are called adjacent points. Adjacent points are connected by edges.
Path: A path is a sequence of edges passing between vertices. The length of a path can be calculated by the number of edges it passes.
Circle: If the starting point and end point of the path are the same vertex and pass through at least one edge, a circle is formed. Circles are also called loops.
Directed and undirected graphs:
Degree of vertex:
For an undirected graph, the degree of a vertex v refers to the number of edges attached to the vertex, denoted as TD(v).
For directed graph, what we want to discuss is the in-degree and out-degree of the vertices:
The degree of vertex v is equal to the sum of in-degree and out-degree, that is, TD(v) = ID(v) + OD(v).
Entry is the number of directed edges ending with vertex v, recorded as ID(V); Outdegree is the number of directed edges starting from vertex v , recorded as OD(v).
Description of the relationship between vertices:
Connected graphs and strongly connected graphs:
Subfigure: (Study part of the figure)
For directed graphs, the concepts of subgraphs and generated subgraphs are the same:
Connected components:
The maximal connected subgraph in an undirected graph is called a connected component:
The maximal strongly connected subgraph in a directed graph is called the strongly connected component of the directed graph:
Spanning tree:
The spanning tree of a connected graph is a minimal connected subgraph that contains all the vertices in the graph.
Generate forest:
In a disconnected graph, the spanning tree of connected components constitutes the spanning forest of the disconnected graph.
Several special forms of pictures:
Reviewing the key points, the main contents are summarized as follows:
Storage representation of graph
Graphs can be stored and represented in many ways, and there are two main common methods: adjacency matrix and adjacency list.
Adjacency matrix method:
The adjacency matrix is a two-dimensional array used to represent the connection relationships between nodes in the graph. For a graph with n nodes, the adjacency matrix is a square matrix of size n×n. If there is an edge between node i and node j, the element in row i and column j in the adjacency matrix is 1; otherwise it is 0. The advantage of the adjacency matrix is that it can quickly determine whether there is an edge between any two nodes, but the disadvantage is that it takes up a lot of space when the graph is sparse.
If we use the adjacency matrix method to store weighted graphs (nets):
Adjacency list method:
Determine the index of the next node connected to the current node based on directed and undirected connections:
Reviewing the key points, the main contents are summarized as follows:
Cross linked list method to store directed graph:
Adjacency multiple tables store undirected graphs:
If you delete nodes and edges, the corresponding results will be as follows:
Reviewing the key points, the main contents are summarized as follows:
Basic operations of graphs
If we want to know whether there is an edge between two nodes, we can use the adjacency matrix or adjacency list:
If we want to insert vertex x in the graph, we can do it in the following way:
If you want to delete a certain vertex x in the graph, you can do it in the following way:
If you want to know the first adjacent point of vertex x in the graph, if there is one, return the vertex number. If x has no adjacent point or x does not exist in the graph, then return -1:
Graph traversal and connectivity
Graph traversal refers to the process of visiting all nodes in the graph. Through traversal, we can gain a comprehensive understanding of the structure of the graph and the relationships between nodes. Commonly used graph traversal algorithms include Breadth-First Search (BFS) and Depth-First Search (DFS).
Breadth-First Traversal: Breadth-First Search (BFS) of the graph is a strategy that starts from the starting node, first visits the node closest to the starting point, and then expands the access outward layer by layer. . It ensures that nodes close to the starting node are visited first, and then nodes slightly farther away are visited.
An example of breadth-first traversal of a sequence is as follows:
The following is a basic code example for implementing breadth-first traversal of a graph in C:
#include <stdio.h>
#defineMAX_NODES 100
typedef struct {
int neighbor[MAX_NODES];
int numNeighbors;
int visited;
} Node;
void bfs(Node graph[], int start, int numNodes) {
int queue[MAX_NODES];
int front = 0, rear = 0;
// Add the starting node to the queue and mark it as visited
queue[rear + + ] = start;
graph[start].visited = 1;
while (front != rear) {
int current_node = queue[front + + ]; // The first node of the queue is dequeued
printf("%d ", current_node); // Access the current node
// Traverse the neighbor nodes of the current node
for (int i = 0; i < graph[current_node].numNeighbors; i + + ) {
int neighbor = graph[current_node].neighbor[i];
if (!graph[neighbor].visited) { // If the neighbor node has not been visited
queue[rear + + ] = neighbor; //Enqueue neighbor node
graph[neighbor].visited = 1; // Mark neighbor nodes as visited
}
}
}
}
int main() {
//Create a sample image
Node graph[MAX_NODES];
//Initialize nodes and edges in the graph
for (int i = 0; i < MAX_NODES; i + + ) {
graph[i].numNeighbors = 0;
graph[i].visited = 0;
}
//Add edge relationship
graph[0].neighbor[graph[0].numNeighbors + + ] = 1;
graph[0].neighbor[graph[0].numNeighbors + + ] = 2;
graph[1].neighbor[graph[1].numNeighbors + + ] = 3;
graph[2].neighbor[graph[2].numNeighbors + + ] = 4;
graph[2].neighbor[graph[2].numNeighbors + + ] = 5;
graph[3].neighbor[graph[3].numNeighbors + + ] = 6;
graph[4].neighbor[graph[4].numNeighbors + + ] = 7;
// Perform breadth-first traversal
bfs(graph, 0, 8); // Assume there are 8 nodes in the graph
return 0;
}
Breadth-first spanning tree is used to generate a tree structure in a breadth-first manner starting from a given starting node in an undirected graph or directed graph. The tree contains the The shortest path from a node to all reachable nodes.
Reviewing the key points, the main contents are summarized as follows:
Depth-First Traversal: Depth-First Search (DFS) is a strategy to go as far as possible first, that is, go to the end along the current path until you can go no further, and then backtrack Go to the previous node and continue to explore other paths until all nodes have been visited.
Depth-first spanning tree refers to a tree-like structure generated by a depth-first search algorithm. The tree contains the shortest path from a given starting node to all reachable nodes.
Here is a basic code example for depth-first traversal in C:
#include <stdio.h>
#defineMAX_NODES 100
typedef struct {
int neighbor[MAX_NODES];
int numNeighbors;
int visited;
} Node;
void dfs(Node graph[], int current_node) {
printf("%d ", current_node); // Visit the current node first
graph[current_node].visited = 1; // Mark the current node as visited
// Traverse the neighbor nodes of the current node and call the dfs function recursively
for (int i = 0; i < graph[current_node].numNeighbors; i + + ) {
int neighbor = graph[current_node].neighbor[i];
if (!graph[neighbor].visited) { // If the neighbor node has not been visited
dfs(graph, neighbor); // Recursively visit neighbor nodes
}
}
}
int main() {
//Create a sample image
Node graph[MAX_NODES];
//Initialize nodes and edges in the graph
for (int i = 0; i < MAX_NODES; i + + ) {
graph[i].numNeighbors = 0;
graph[i].visited = 0;
}
//Add edge relationship
graph[0].neighbor[graph[0].numNeighbors + + ] = 1;
graph[0].neighbor[graph[0].numNeighbors + + ] = 2;
graph[1].neighbor[graph[1].numNeighbors + + ] = 3;
graph[2].neighbor[graph[2].numNeighbors + + ] = 4;
graph[2].neighbor[graph[2].numNeighbors + + ] = 5;
graph[3].neighbor[graph[3].numNeighbors + + ] = 6;
graph[4].neighbor[graph[4].numNeighbors + + ] = 7;
// Perform depth-first traversal
dfs(graph, 0); // Assume that we start traversing from node 0
return 0;
}
Connected components
A connected component refers to the largest connected subgraph in an undirected graph. A connected component consists of several vertices and the edges between them, where each vertex can reach each other through paths to other vertices.
In an undirected graph, a connected component can be understood very intuitively as a region in the graph in which all vertices can reach each other. Each connected component is part of a graph, and a graph can have multiple connected components.
In directed graphs, the definition of connected components is relatively complex. Connectivity of a directed graph requires taking into account directed paths between vertices. A connected component in a directed graph means that each vertex in the graph has at least one directed path to reach all other vertices.
Reviewing the key points, the main contents are summarized as follows:
Minimum spanning tree
Minimum spanning tree refers to finding a spanning tree that contains all vertices in an undirected weighted connected graph, and the sum of the weights of all edges of the tree is the smallest. Minimum spanning tree has the following characteristics:
There may be multiple minimum spanning trees; the number of edges in the minimum spanning tree is equal to the number of vertices minus 1; there will be no cycles in the minimum spanning tree.
Common algorithms for solving the minimum spanning tree problem include Prim’s algorithm and Kruskal’s algorithm.
Prim’s algorithm(Prim): Build a spanning tree starting from a certain vertex; each time the new vertex with the smallest cost is included in the spanning tree until all vertices are included.
Here we choose city p as the root node, and then expand outward in order to find the node with the smallest cost between the connections, and finally get the minimum cost:
Kruskal algorithm (Kruskal): Select an edge with the smallest weight each time and connect both ends of this edge (the ones that are already connected are not selected) until all nodes are connected.
Comparison of the two algorithms:
Shortest path problem
The shortest path problem of a graph refers to the problem of finding the shortest path between two vertices in a weighted directed graph or undirected graph. The shortest path can be measured by the sum of edge weights. The shortest path problem is mainly divided into the following two situations:
Single-source shortest path: The shortest path from a given starting node to all other nodes in the graph. It can be used to solve the shortest path problem from a fixed starting point to other nodes.
BFS algorithm (unweighted graph):
Dijkstra’s algorithm (weighted graph, unweighted graph):
Shortest path between vertices: Calculate the shortest path between any two nodes in the graph. It can be used to solve the shortest path problem between any pair of nodes.
Floyd algorithm (weighted graph, unweighted graph):
Reviewing the key points, the main contents are summarized as follows:
critical path problem
The critical path refers to the longest path in the project plan that cannot be delayed. It determines the shortest completion time of the entire project. Critical path problems are commonly used in project management and engineering planning.
In the AOE network we need to understand the following concepts:
After citing the relevant examples above, we next start to calculate the corresponding values:
Find the earliest occurrence time of all events: (Wait until the slowest one is completed)
Find the latest occurrence of all events: (The latest occurrence time of the sink is consistent with the earliest occurrence time. We use the sink as the trigger point to perform topological sorting, that is, subtract the events that occur on the corresponding path. Thus, the latest occurrence time of this point is obtained):
Find the earliest occurrence time of all activities: (The earliest occurrence time of the activity is calculated from the earliest occurrence time of the event at the previous calculation):
Find the latest occurrence time of all activities: (obtained by subtracting the time required for the corresponding activity from the latest occurrence time of the event at the previous calculation)
Find the time margin of all activities: (latest occurrence time of activity minus earliest occurrence time of activity)
Note: The following are the corresponding key activities and characteristics of the critical path:
Reviewing the key points, the main contents are summarized as follows:
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56,494 people are learning the system