Basic concepts of graphs
The concept of graph
Graph: Vertex Vertex; Arc Arc. (at least one vertex)
Directed graph Digraph: directed arc; A->B (arc head B/arc tail A); directed complete graph. G=
Undirected graph Undigraph: undirected edge Edge; undirected complete graph. G=(v,a)
Point
Adjacent points: An undirected graph such as A and B are adjacent points to each other, and a directed graph such as A is adjacent to B
Degree of vertex of undirected graph, TD(A)=2;
Vertex degree of directed graph, ID(A)=1,OD(A)=2,TD(A)=3
Path
Classification of pictures
1.DG (directed graph), UDG (undirected graph),
2.DN (network, weighted directed graph) and UDN (arc or edge weighted undirected graph).
3. Sparse graphs and dense graphs
4. Connected graphs and disconnected graphs
Connected graph (undirected)
In the undirected graph G=(V, E), for any two vertices u and v, there is a path from u to v. 
Strongly connected graph (directed)
In the directed graph G=(V, E), for any two vertices u and v, there is a directed path from u to v.
Maximal connected subgraph (connected components)
In a disconnected graph
Minimal connected subgraph (spanning tree)
In a connected graph
condition:
1. All vertices n in the graph
2. Enough to form n-1 edges of a tree
Features:
no loop
As shown in the picture, there are 5 points, find 4 edges
Graph storage structure
Adjacency matrix representation
Method: Vertex table + adjacency matrix (storing relationships between vertices)
Features:
No direction
promising
Array (adjacency matrix) storage representation of graph
typedef *** VertexType;//Define vertex type
#define MVNUM 100 //Maximum number of vertices
#define INFINITY 32767 //Maximum value∞
typedef enum{DG, DN, UDG, UDN} GraphKind;//Graph type: directed, undirected, etc.
// definition of arc
typedef struct ArcType {
int/double adj; //Number of adjacencies, 0/1 or w/∞
InfoType *info; //Additional information for arc, InfoType can be char and int
}ArcType;
// Definition of graph
typedef struct {
VertexType vexs[MVNUM]; //Vertex information
ArcType arcs[MVNUM][MVNUM]; // Adjacency matrix
int vexnum, arcnum; // Number of vertices, number of arcs
GraphKind kind; //Graph type tag
} MGraph; //Matrix graph
create
//Input the type of graph and vertex and edge information to construct graph G (adjacency matrix representation)
Status CreateGraph(Mgraph &G) {
scanf(“%d”, & amp;G.kind);//Enumeration values DG,DN…real input 0 1…
switch (G.kind) {
case DG : return CreateDG(G);
case DN : return CreateDN(G);
case UDG : return CreateUDG(G);
case UDN : return CreateUDN(G);
default: return ERROR;
}
//Create an undirected network G
Status CreateUDN(Mgraph & amp;G){
cin>>G.vexnum>>G.arcnum>>IncInfo; //IncInfo is 0 and the arc has no additional information
for (i=0; i< G.vexnum; + + i) cin>>G.vexs[i];
for (i=0; i< G.vexnum; + + i)
for(j=0; j< G->vexnum; + + j)
G.arcs[i][j] = {INFINITY, NULL}; //Initialization of each arc
for (k=0;k< G.arcnum; + + k){
scanf("%c %c %lf", & amp;v1, & amp;v2, & amp;w); //Enter an "edge" and its weight
i=LocateVex(G,v1);j= LocateVex(G,v2); //Determine the vertex subscript
G.arcs[i][j].adj = w;
if (IncInfo) cin>>G.arcs[i][j].info;
G.arcs[j][i]= G.arcs[i][j]; //The undirected network needs to add symmetric arcs
}
} //END
Advantages and disadvantages
Advantages: easy to find vertex degrees (distinguish directed/undirected graphs), find adjacent points, easy to determine whether there are arcs or edges connecting two points
Disadvantages: It is not conducive to the storage of sparse graphs, because the corresponding information must be stored even when the arc does not exist; and sufficient space must be allocated in advance
Adjacency list representation
Method: vertex array, each array element contains two parts: data + firstarc (a linked list composed of adjacent point subscripts)
No direction
promising
Adjacency list storage structure definition
typedef struct ArcNode {
int adjvex;
struct ArcNode * nextarc;
InfoType *info;
} ArcNode;
typedef struct VNode {
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MVNUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
GraphKind kind;
} ALGraph; //adjacency list graph
Create
Status CreateDN(ALGraph & amp;G){ //Build a directed network
scanf(“%d%d%d”, & amp;G.vexnum, & amp;G.arcnum, & amp;IncInfo);
for (i=0; i< G.vexnum; + + i) {
cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL;
}
for (k=0;k< G.arcnum;k + + ) {
cin>>v1>>v2>>w;
i=LocateVex(G,v1); j= LocateVex(G,v2);
arc=new ArcNode;
arc->adjvex=j;
if (IncInf) cin>>arc->info;
arc->nextarc = G.vertices[i].firstarc; //Insert to the starting position
G.vertices[i].firstarc=arcn;//Adjacent points and input are arranged in reverse order, forward order?
} //The order of adjacent points depends on the input order and the creation program, and the default is positive order.
Return OK;
} //Think about what else is different about creating an undirected graph?
Cross linked list representation (omitted)
Summary
Graph traversal
Concept of graph traversal
Depth-First Searching-dfs
Principle
Same as the root traversal of the tree
Algorithm implementation
Adjacency matrix
Adjacency list
Implementation code of two methods
int visited[G.vexNum]; // Define a global array visited to record whether each vertex has been visited
//Declaration and implementation of DFS function
void DFS(Graph G, int v, Status (*visit)(ElemType));
void DFS(Graph G, int v, Status (*visit)(ElemType)){
visit(v); // Visit the current vertex
visited[v] = TRUE; // Mark the current vertex as visited
for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
if (!visited[w]) { // If the adjacent vertex has not been visited
DFS(G, w, visit); // Recursively call the DFS function and continue to visit adjacent vertices
}
}
return; // Return to the previous level of recursion
}
//Declaration and implementation of DFSTraverse function
void DFSTraverse(Graph G, Status (*visit)(int v));
void DFSTraverse(Graph G, Status (*visit)(int v)){
for (int v = 0; v < G.vexnum; + + v) { // Initialize the visited array and mark all vertices as unvisited
visited[v] = FALSE;
}
for (int v = 0; v < G.vexnum; + + v) { // Traverse all vertices
if (!visited[v]) { // If the vertex has not been visited
DFS(G, v, visit); // Call the DFS function to start a depth-first search from this vertex
}
}
}
Complexity: DFS is called once for each vertex. The main operation of DFS is to find adjacent points.
The complexity of finding the adjacent points of a vertex when storing the adjacency matrix is O(n), and the total complexity is O(n2);
When storing adjacency lists, the complexity of searching all vertices and all adjacent points is O(e), and the total complexity is O(n + e).
Breadth-First Searching-BFS
principle
Algorithm implementation
Access dequeued adjacencies
void BFS(Graph G, int v, Status (*visit)(ElemType){
visit (v); visited[v]=TRUE;
InitQueue(Q); EnQueue(Q, v);
while (!QueueEmpty(Q)) {
DeQueue(Q, v);
for(w=FirstAdjVex(G,v); w>=0;w=NextAdjVex(G,v,w))
if ( ! visited[w] ) {
visit(w); visited[w]=TRUE; EnQueue(Q, w);
}
}
}
void BFSTraverse(Graph G, Status (*visit)(int v)) {
for (v=0; v<G.vexnum; + + v) visited[v] = FALSE;
for (v=0; v<G.vexnum; + + v)
if (!visited[v]) BFS(G, v, visit);
} //In the textbook, the two function codes here are merged into one function.
Complexity: Each vertex enters the queue once, and the main operation when dequeuing is to find adjacent points.
When storing adjacency matrices, the complexity of finding the adjacent points of a vertex is O(n), and the total complexity is O(n2);
When using adjacency list storage, the complexity of finding all adjacent points of all fixed points is O(e), and the total complexity is O(n + e).
Application of graph traversal
1. Get out of the maze
2. Circular dependency and deadlock problems are equivalent to determining whether there is a directed loop
3. Application: Maze shortest path, connectivity and connected components, spanning tree
Conclusion: During the dfs process, start from v to find the adjacent point w. If w is the ancestor node that has been visited, then
Summary and promotion
Summarize
Backtracking implementation
promotion
