This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging
figure
- Definition: the Graph = (V, E)
- V: a finite non-empty set of vertices (data elements)
- E: A finite set of edges
Terms and terms for graphs
- Vertex: a data element in a graph.
- Edge: If
E must have
E, then (v,w) is said to have an edge between vertices V and w.
- Arc: If
E is directed, then
means that there is a directed edge between vertices v and w, also called an arc.
- Undirected graph: a graph consisting of a set of vertices and a set of edges. Each side is directionless
- Digraph: Since the “arc” is directed, a graph consisting of a set of vertices and a set of arc is called a digraph. ,
- Complete graph
- Vertex: n, edge: e
- Undirected complete graph: An undirected graph with **e=n(n-1)/2 ** edges
- Directed complete graph: a directed graph with e=n(n-1) arc
- Sparse graph: e
- Dense graph: e>nlogn
- Weight: The edges of some graphs have numbers associated with them
- Net: map with edge/arc weights
- Adjacencies: If there is an edge between vertices V and W,
Vertices V and W are said to be mutually adjacent
- 1. The number of edges associated with the vertex, denoted as TD(v).
- 1. The number of directed edges ending in v, denoted as ID(v).
- 1. The number of directed edges starting at v, denoted as OD(v).
Degree (TD)= Out (OD)+ in (ID)
- Path: A sequence of vertices formed by successive edges.
- Path length: sum of the number/weights of paths or arcs.
- Simple path: a path whose vertices are different except that the beginning and end of the path may be the same.
- Simple loop (simple loop) : a path whose vertices are different except that the beginning and end of the path are the same.
- Connected graph
-
Undirected graph
- There are paths between any two vertices in graph G
- Connected components: If the undirected graph is not a connected graph, the maximal connected subgraphs of the graph are called the connected components of the graph.
A maximally connected subgraph means that the subgraph is G connected. If any vertex of G is added that is not in the subgraph, the subgraph is no longer connected.
-
Directed graph
- Strongly connected graph: There is a directed path between any two vertices
- Strongly connected components: maximal strongly connected subgraphs
-
- Minimal connected subgraph: the subgraph is a connected subgraph of G. If any edge is removed from the subgraph, the subgraph is no longer connected. (n vertices, n minus 1 edges)
- Spanning tree: a minimal connected subgraph containing all vertices of an undirected graph G.
- Spanning forest: A set of spanning trees of connected components for a nonconnected graph.
The storage structure of the diagram
Adjacency matrix representation of graphs
Let the graph A = (V, E) have n vertices, then the adjacencies matrix of the graph is A two-dimensional array A.edge [n][n], defined as:
Adjacencies matrix representation of undirected graphs
- The adjacencies matrix of an undirected graph is symmetric and compressively stores (upper/lower) triangles.
- The degree of vertex I is equal to the number of 1s in row (column) I;
- One half of the number of 1s in the matrix is the number of edges in the graph
- It is easy to determine whether there are edges between vertex Vi and vertex Vj (see if the value of row I and column J in the matrix is 1)
- Add (delete) edges to the graph without changing vertices: simply assign 1 (clear 0) to the corresponding component of the two-dimensional array.
In the adjacencies matrix of a complete graph, the diagonal elements are 0 and the rest are 1.
Adjacency matrix representation of a directed graph
In the adjacency matrix of a directed graph,
Meaning of line I: the arc with node vi as its tail (i.e. the outdegree edge); Meaning of column I: the arc headed by node vi (i.e., the edge of entry degree).
- The adjacence matrix of a directed graph may be asymmetric.
- The outdegree of the vertices is equal to the sum of the ith row elements
- The input degree of the vertices is equal to the sum of the elements in column I
- The degree of the vertices is equal to the sum of the elements in row I + the sum of the elements in column I
- It’s easy to tell if vertex Vi and vertex Vj are arced together
- Add (delete) edges to the graph without changing vertices: simply assign 1 (clear 0) to the corresponding component of the two-dimensional array.
The adjacence matrix representation of a network (i.e., a weighting graph)
The storage representation of the adjacency matrix
#define INFINITY 1000 // Define an infinite number
#define MAX_VERTEX_NUM // Maximum number of vertices
// The graph type enumeration defines {directed graph, directed network, undirected graph, undirected network}
typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct ArcCell{/ / edge definition
VRType adj; // VRType is the vertex relationship type.
// For the unmatched graph, use 1 or 0 to indicate adjacent no;
// For the weighted graph (network), it is the weight type.
InfoType* info; // A pointer to the arc related information
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
typedef struct { // The definition of the graph
// Vertex information
VertexType vexs[MAX_VERTEX_NUM]; // Vertex vector
AdjMatrix arcs; // The adjacency matrix
int vexnum, arcnum; // Number of vertices and number of edges
GraphKind kind; // The type of the picture
} MGraph;
Copy the codeThe undirected network algorithm is constructed by the adjacencies matrix representation
/*--------------- uses adjacencies matrix to establish undirected network ---------------*/
// Algorithm idea
// 1. Enter the total number of vertices and the total number of edges.
// 2. Input points' information into the vertex table.
// 3. Initialize the adjacencies matrix so that each weight is initialized to its maximum value.
// 4. Construct the adjacencies matrix.
void CreateUDN(MGraph &G){
cin >> G.vexnum >> G.arcnum; // Input the number of vertices and edges
for(int i = 0; i < G.vexnum; i++){
// Create a vertex table
G.vexs[i] = new char[10];
cin >> G.vexs[i]; // Read the vertex information
}
for(int i = 0; i < G.vexnum; i++)
// The adjacencies matrix is initialized
for(j = 0; j < G.vexnum; j++){
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
for(k = 0; k < G.arcnum; k++){
v1 = new char[10];
v2 = new char[10];
cin >> v1 >> v2 >> w; // Read the weight of edge e
i = LocateVex_MG(G, v1); // Find the position of vertex v1 in the graph
j = LocateVex_MG(G, v2);
G.arcs[i][j].adj = w;
G.arcs[j][i].adj = w;
delete v1;
deletev2; }}int LocateVex_MG(MGraph G, VertexType x){
// Find the position of vertex x in the graph
for(int k = 0; strcmp(G.vexs[k], x); k++);
return k;
}
Copy the codeThe characteristics of adjacency matrix representation
- Advantages: easy to realize the operation of the graph, such as: find the degree of a vertex, judge whether there is an edge between the vertices, find the vertex adjacent point and so on.
- Disadvantages: N vertices require n*n cells to store edges; The space efficiency is O(n^2). This is especially a waste of space for sparse graphs.
Adjacency list representation of a graph
- Establish a single linked list for each vertex VI, link the information of the edges associated with vi, and set each node as 3 domains.
- One part is a single linked list that holds edge/arc information
- The other part is the array, mainly used to hold the data information of the vertices themselves
Adjacency list of undirected graphs
- Edge links emitted by the same vertex are in the same edge linked list, and each link node represents an edge (edge node).
The adjacency list is not unique because the chain order of each edge node is arbitrary
- The space efficiency is O(n+2e). If the sparse graph (e<
- Half of the number of edge nodes in all linked lists is the number of edges in the graph
TD(Vi)= Number of linked nodes in the single linked list
Adjacency list of digraph
- Space efficiency: O(n+e)
- Outturn: OD(Vi) = Number of linked nodes in the single link outturn table
- Input degree: ID(Vi) = The number of arcs whose adjacent domain is Vi
- TD(Vi) = OD(Vi) + I D(Vi)
The adjacency list store representation of a graph
typedef struct ArcNode{
// Edge node definition
int adjvex; // The position of the vertex to which the arc points
struct ArcNode* nextarc; // A pointer to the next arc
InfoType* info; // A pointer to information related to the arc
} ArcNode;
typedef struct VNode{
// Vertex node definition
// Table header node
VertexType data; // Vertex information
ArcNode* firstarc; // Point to the first arc attached to the vertex
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
// Figure structure definition
AdjList vertices; // The vertex structure array of the graph
int vexnum, arcnum; // The number of vertices and edges
int kind;
} ALGraph;
Copy the codeThe adjacency list representation is used to construct the directed graph
/*------------ uses the adjacency list notation to construct the directed graph ------------*/
void GreateDG_ALG(ALGraph &G){
// Construct a directed graph
cin >> G.vexnum >> G.arcnum;
for(i = 0; i < G.vexnum; i++){
// Create a vertex table
G.vertices[i].data = new char[10];
cin >> G.vertices[i].data; // Read the vertex information
G.vertices[i].firstarc = NULL;
}
for(k = 0; k < G.arcnum; k++){
// Create an edge table
v1 = new char[10];
v2 = new char[10];
cin >> v1 >> v2;
i = LocateVex_ALG(G, v1); / / arc tail
j = LocateVex_ALG(G, v2); / / arc head
p = new ArcNode;
p->adjvex = j;
p->nextarc = G.vertices[i].firstarc;
p->info = NULL;
G.vertices[i].firstarc = p; / / forward}}Copy the codeAn adjacence list representation is used to construct an undirected graph
/*------------ uses adjacency list notation to construct undirected graphs ------------*/
void CreateUDG(ALGraph &G){
cin >> G.vexnum >> G.arcnum; // Input total number of vertices, total number of edges
for(i = 0; i < G.vexnum; i++){
// Input each point to construct the table head node table
cin >> G.vertices[i].data; // Enter the vertex value
G.vertices[i].firstarc = NULL; // Initialize the pointer field of the header node to NULL
}
for(k = 0; k < G.arcnum; ++k){
// Input the edges to construct the adjacencies list
cin >> v1 >> v2; // Input 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 number of the adjacent point is j
Insert the new node *p1 into the edge table header of vertex vi
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;
p2 = new ArcNode; // Generate another symmetric new edge node *p2
p2->adjvex = i;
// Insert the new node *p2 into the edge table header of vjp2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2; }}Copy the codeCharacteristics of adjacency list notation
- Advantages: high space efficiency, easy to find vertex adjacencies
- Disadvantages: To judge whether there are edges or arcs between two vertices, it is necessary to search the single linked list corresponding to the two nodes, which is not convenient for adjacence matrix
The relation between adjacency matrix and adjacency list representation
- Relation: Each linked list in the adjacencies list corresponds to a row in the adjacencies matrix, and the number of nodes in the linked list is equal to the number of non-zero elements in the row.
- The difference between
- For any given undirected graph, the adjacency matrix is unique (column and column numbers correspond to vertex numbers), but the adjacency list is not unique (the order of links is independent of vertex numbers).
- The space complexity of the adjacency matrix is O(n*2) and the space complexity of the adjacency list is O(n+e).
- Purpose: The adjacency matrix is mainly used in dense graphs; The adjacency list is mostly used in sparse graphs
Cross list — used for directed graphs
- The representation of nodes in the node table
- Representation of nodes in the table of edge nodes
- info: indicates the data field of the edge node, which stores the weight of the edge. -tailvex: Address of the departure node for this edge. - headvex: indicates the address of the end node of this edge. - hlink: indicates the address of the next edge of the same terminating node. - tlink: indicates the address of the next edge in the same starting point.Copy the codetypedef struct ArcBox{
// Arc node structure representation
int tailvex, headvex;
InfoType* info;
struct ArcBox* hlink, *tlink;
} ArcBox;
typedef struct VexNode{
// Structure representation of vertices
VertexType data;
ArcBox* firstin,* firstout;
} VexNode;
typedef struct{
// A crossword list of digraphs
VexNode xlist[MAX_VERTEX_NUM]; // Vertex nodes
int vexnum, arcnum; // The current number of vertices and arcs in the digraph
} OLGraph;
void CreatDG_OLG(OLGraph &G){
// Construct a directed graph
cin >> G.vexnum >> G.arcnum; // Number of vertices, number of arcs
for(i = 0; i < G.vexnum; i++){
// Create a vertex table
G.xlist[i].data = new char[10];
cin >> G.xlist[i].data; // Read the vertex information
G.xlist[i].firstin = NULL;
G.xlist[i].firstout = NULL;
}
for(k = 0; k < G.arcnum; k++){
// Create a cross list
v1 = new char[10];
v2 = new char[10];
i = LocateVex_OLG(G, v1);
j = LocateVex_OLG(G, v2);
p = new ArcBox;
p->info = NULL;
p->headvex = j; // The end of the arc
p->tailvex = i; // The beginning of the arc
p->hlink = G.xlist[j].firstin; / / forwardp->tlink = G.xlist[i].firstout; G.xlist[j].firstin = G.xlist[i].firstout = p; }}Copy the codeAdjacent multitable storage representation of undirected graphs
- Mark: Indicates whether the edge has been searched
- Ivex, jvex: The positions in the graph of the two vertices to which the edge is attached
- Ilink: Points to the next edge attached to the vertex ivex
- Jlink: Points to the next edge attached to the vertex jvex
- Info: A field of Pointers to various information related to edges
In the link storage (adjacence list, inverse adjacence list, cross linked list and adjacence multiple list) of graphs, the table head vector needs to occupy N storage units, and all edge nodes need to occupy 2E or E storage units, so a maximum of (N + 2E) storage units are needed. This storage method can save storage space for sparse graphs.
Graph traversal
- Definition: starting from a vertex in a given connected graph, visiting all vertices in the graph along some edges, and making each vertex only visited once is called the traversal of the graph, which is the basic operation of the graph.
- Traversal: The process of finding the adjacencies of each vertex.
- The characteristics of graphs: there may be loops in graphs, and any vertex of graphs may communicate with other vertices. After visiting a vertex, they may return to the vertex they visited along some edges.
How to avoid repeated visits?
- Set the auxiliary array visited [n] to mark each visited vertex.
- The initial state is 0
- I was visited [I]
Depth-first Search (DFS — Depth_First Search)
Basic idea: preorder traversal process of imitation tree.
Simple analysis
- Access starting point V;
- If the first adjacent point of V is not visited, the depth traversal of this adjacent point;
- If the current adjacencies have been accessed, the second adjacencies of V are found and traversed again.
Detailed induction
- After accessing a starting vertex V in the graph, starting from V, access any of its adjacent vertex w1;
- Starting from w1, access w2, which is adjacent to w1 but has not yet been accessed.
- And then from W2, a similar visit…
- This continues until vertex U is reached where all adjacent vertices have been accessed.
- And then, taking a step back,Rewind to the vertex that was visited last timeTo see if there are any other adjacent vertices that have not been accessed.
- If so, the vertex is accessed, and then similar access is performed from the vertex;
- If not, take a step back and search. This process is repeated until all vertices in the connected graph have been accessed.
Depth first search algorithm for graph
Connected graph
int visited[MAX_VERTEX_NUM]; // Global variables
void Visit(VertexType x){cout << x << ""; }/*----------- Depth first search algorithm for graphs (connected graphs) -----------*/
void DFS(Graph G, int v){
Visit(v);
visited[v] = true;
// FirstAdjVex(G, v) indicates the first adjacent point of v
NextAdjVex(G, v, w) indicates the next adjacent point of V with respect to w
W >= 0 indicates that the adjacencies exist
for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
if(! visited[w])DFS(G, w);
}
Copy the codeA connected graph
/*----------- Depth first search algorithm for graphs (disconnected graphs) -----------*/
void DFSTraverse(Graph G){
for(v = 0; v < G.vexnum; ++v) visited[v] = false; // Access flag number initialization
for(v = 0; v < G.vexnum; ++v)
if(! visited[v])DFS(G, v);
}
Copy the codeThe process of traversing the graph is essentially the process of finding the adjacent points of each vertex. Given the memory structure of the graph, the result of traversal from a vertex should be unique.
The adjacency matrix represents a depth-first search traversal of the graph
/*----------- The adjacency matrix represents the depth-first search traversal of the graph -----------*/
void DFS_AM(AMGraph G, int v){
// Figure G is the type of adjacent matrix
cout << v;
// Access the VTH node
visited[v] = true;
for(w = 0; w < G.vexnum; w++){
// Check the row of the adjacencies matrix v once
if((G.arcs[v][w] ! =0) && (! visited[w]))DFS(G, w);
If w is not accessed, then DFS is called recursively}}Copy the codeThe adjacency list represents a depth-first search traversal of the graph
/*----------- the adjacency list represents a depth-first search traversal of the graph -----------*/
void DFS_AL(ALGraph G, int v){
// Figure G is an adjacencies list type
cout << v;
visited[v] = true; // Access the VTH vertex
p = G.vertics[v].firstarc; // p refers to the first edge node of v's edge list
while(p ! =NULL) {// Edge nodes are not null
w = p->adjvex; // indicates that w is the adjacent point of V
if(! visited[w])DFS(G, w); // If w is not accessed, DFS is called recursively
p = p->nextarc; // p points to the next edge node}}Copy the codeEfficiency analysis of DFS algorithm
- Using the adjacencies matrix to represent the graph, traversing every vertex in the graph must scan the row of the vertex from scratch, and the time complexity is O(n^2).
- If the adjacencies list is used to represent the graph, although there are 2e table nodes, the traversal can be completed only by scanning E nodes. The time complexity is O(n+e) plus the time of accessing n head nodes.
Dense graphs are suitable for depth traversal on the adjacence matrix.
Sparse graphs are suitable for depth traversal on the adjacency list.
Breadth_First Search (BFs-breadth_first Search)
Basic idea: imitation tree hierarchy traversal process
Simple analysis
- After visiting the starting point V, the adjacent points of V are accessed successively.
- Then access the unvisited adjacencies of these vertices in turn;
- Until all vertices have been accessed.
Breadth-first search is a hierarchical search process, where each step forward may access a set of vertices, unlike depth-first search, where there is a fallback.
Therefore, breadth-first search is not a recursive process, nor is its algorithm recursive.
Algorithm thought
- Start from some vertex V in the graph, visit V, and set the value of visited[v] to true, then queue V.
- As long as the queue is not empty, the following processing is repeated
- Team head point u out
- Check all adjacencies w of U in turn, if the value of visited[w] is false, then visit W, and set the value of visited[w] to true, then add W to the queue
A wide order first search traversal algorithm for graphs
Connected graph
/*------------ breadth-first non-recursive traversal of connected graphs G (connected graphs) ------------*/
void BFS(Graph G, int v){
cout << v;
visited[v] = true; // Access the VTH vertex
InitQueue(Q);
EnQueue(Q, v);
while(!QueueEmpty(Q)){
DeQueue(Q, u);
for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
if(! visited[w]){W is the unvisited adjacent vertices of U
cout << w;
visited[w] = false;
EnQueue(Q, w); / / w into the team}}}Copy the codeA connected graph
/*------------ breadth-first non-recursive traversal of connected graphs G (disconnected graphs) ------------*/
void BFSTraverse(Graph G){
for(v = 0; v < G.vexnum; ++v) visited[v] = false; // Access flag number initialization
for(v = 0; v < G.vexnum; ++v)
if(! visited[v])BFS(G, v);
}
Copy the codeEfficiency analysis of BFS algorithm
- If the adjacencies matrix is used, then BFS cycles through the entire row (n elements) of the matrix for each vertex that is accessed, at a total time cost of O(n^2).
- If the adjacencies list is used to represent the graph, although there are 2e table nodes, the traversal can be completed only by scanning E nodes. The time complexity is O(n+e) plus the time of accessing n head nodes.
Efficiency comparison between DFS and BFS algorithms
- Same space complexity, all O(n)(borrowed from stack or queue);
- The time complexity is only related to the storage structure (adjacency matrix or adjacency list), not the search path.
Summary: The process of traversing a graph is essentially a process of finding adjacents through edges or arc. Therefore, the time complexity of breadth-first search traversing a graph is the same as depth-first search traversing a graph. The only difference between the two is the order of accessing vertices.
Adjacency matrix O(n2) Adjacency list O(n+e)