Graph structure is a kind of nonlinear data structure. There are many examples of Graph in real life, such as transportation network, subway network, social network, state execution in computer (automata), etc. All can be abstracted into Graph structure. A Graph is composed of a finite non-empty set of vertices and a set of edges between vertices. Usually expressed as:G(V,E)Where,G represents a graph, V is the set of vertices in graph G,E is the set of edges in graph G. The vertex set V (G) in a graph structure cannot be empty and must contain one vertex, while the edge set in a graph structure can be empty, indicating that there are no edges.The basic concept of ## graphs

1. Undirected Graph

A graph is called undirected if all its edges are undirectional. A typical undirected graph is shown in Figure 2. Since edges in an undirected graph are not directional, there is no requirement for the order of the vertices when we represent edges

2. Undirected Graph

A graph structure in which edges are directional is called a directed graph, as shown in Figure 3. Since the edges of a graph have directionality, the order of the two vertices is required when we represent the edges##### Note: An undirected graph can also be understood as A special directed graph in which edges point to each other, with A pointing to B and B pointing to A

3. Undirected complete graph

An undirected graph with an edge between every two vertices is called an undirected complete graph.

4. Directed complete graph

A directed graph is called a directed perfect graph if there are two opposite edges between every two vertices

5. Degree of vertices

The number of edges connecting a vertex is called the degree of that vertex. The degree of a vertex is represented differently in directed graphs and undirected graphs. For undirected graphs, the degree of a vertex V is simply the number of edges connecting it, denoted as D(V). For example, in the undirected graph shown in Figure 2, the degree of vertex V5 is 3. V6 has a degree of 2. For directed graphs, which are a little more complicated, the degree of a vertex can be in or out depending on the directionality of the edges connecting vertex V. The entry degree is the number of entry edges with the vertex as the endpoint, denoted by ID(V). The outgoing degree is the number of outgoing edges at the end of the vertex, denoted as OD(V). Thus, in a directed graph, the total degree of a vertex V is the sum of the in and out degrees, that is, D(V) = ID(V) + OD(V). For example, in the directed graph shown in Figure 3, vertex V5 has an in degree of 3 and an out degree of 1, so the total degree of vertex V5 is 4. ####6. Unauthorized graph and weighted graph

Shall not be entitled to:

There is no weight between vertices

Weighted graph:

A weighted graph means that an edge has some weight. The notion of a mathematical weighted average where the weight can be anything you want to represent: distance or time spent or ticket prices.

The representation of figure

How do I represent a graph in a program? We know that a graph contains many vertices and also contains the lines (edges) between vertices, both of which are very important graph information and therefore need to be represented in the program.Copy the code

[Data Structure and Algorithm Design] Store the picture on the left in the computer. Please design a data structure and store it properly

##### the representation of vertices: • The representation of vertices is relatively simple. Let’s discuss the representation of vertices first. • The representation of vertices above is abstracted as 1, 2, 3, 4, 5, and can also be abstracted as A, B, C, D, E. • A, B, C, D, E can be stored in an array (storing all vertices) • Of course, A, B, C, D, E can also represent data with other meanings (such as the name of the village). In this case, we can create another array, It is used to store corresponding other data. • Because an edge is a relationship between two vertices, it is slightly more difficult to represent.

Adjacency matrix

• An adjacency matrix associates each node with an integer that acts as a subscript to the array. • We use a two-dimensional array to represent the connections between vertices.

In a two-dimensional array, 0 indicates no connection and 1 indicates a connection. Using a two-dimensional array, we can quickly find which vertices are connected to a vertex (v0, for example, only needs to traverse the first line). In addition, the connection between a vertex and itself is usually represented by 0.

The adjacency matrix problem: if it is an undirected graph, the adjacency matrix presents a two-dimensional array that is actually a symmetric graph. When V0->V4 is 1, the symmetrical position V4->V0 must also be 1. In this case, space is wasted. Is there any way you can optimize it? #### Adjacency matrix Data structure design for matrix storage

#### code implementation

  1. Determine number of vertices/edges
  2. Read vertex information
  3. Initialize the adjacency matrix
  4. Read in edge information
  5. Loop to print
#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define INFINITYC 0 typedef int Status #define INFINITYC 0 typedef int Status; /* typedef char VertexType; /* typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; / / typedef struct {VertexType vexs[MAXVEX]; /* EdgeType arc[MAXVEX][MAXVEX]; /* adjacency matrix */ int numNodes, numEdges; /* The number of vertices and edges in the graph */}MGraph; void CreateMGraph(MGraph *G){ int i,j,k,w; Printf (" Input number of vertices and edges :\n"); / / 1. Input vertex/number of edges the scanf (" % d, % d ", & G - > numNodes, & G - > numEdges); Printf (" vertices: % d, number of edges: % d \ n ", G - > numNodes, G - > numEdges); For (I = 0; i<= G->numNodes; i++) scanf("%c",&G->vexs[i]); //3. Initialize the adjacency matrix for(I = 0; i < G->numNodes; i++) for(j = 0; j < G->numNodes; j++) G->arc[i][j] = INFINITYC; //4. Input side table information for(k = 0; k < G->numEdges; K++){printf(" subscript I, subscript j, weight w\n" on input edge (vi,vj)); scanf("%d,%d,%d",&i,&j,&w); G->arc[i][j] = w; // If there is no digraph, the matrix is symmetric; G->arc[j][i] = G->arc[i][j]; For (int I = 0; i < G->numNodes; i++) { printf("\n"); for (int j = 0; j < G->numNodes; j++) { printf("%d ",G->arc[i][j]); } } printf("\n"); } int main(void) {printf(" adjacency matrix implementation graph store \n"); /* MGraph G; CreateMGraph(&G); return 0; }Copy the code
Another serious problem with adjacency matrices is that if the graph is a sparse graph there will be a lot of zeros in the matrix, which means we waste computer storage to represent edges that don't exist at all. And even if there's only one edge, we have to go through a row to find that edge, which wastes a lot of time.Copy the code

Adjacency list

An adjacency list consists of each vertex in the graph and the list of vertices adjacent to the vertex. This list can be stored in any of several ways: arrays/linked lists/dictionaries (hash tables). #### Data structure design for adjacency list storage #### adjacency list storage storage code implementation ideas

#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define M 100 #define true 1 #define false 0 typedef char Element; typedef int BOOL; // typedef struct Node{int adj_vex_index; // the index of the arc header, that is, the index to Element data; Struct Node * next; }EdgeNode; Typedef struct vNode{Element data; EdgeNode * firstedge; // Who is next at the vertex? }VertexNode, Adjlist[M]; Typedef struct Graph{Adjlist Adjlist; Int arc_num; Int node_num; // Number of nodes BOOL is_directed; }Graph, *GraphLink; void creatGraph(GraphLink *g){ int i,j,k; EdgeNode *p; Printf (" Input the number of vertices, edges, and direction? : \ n "); scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed); Printf (" Input vertex information: \n"); for (i = 0; i < (*g)->node_num; i++) { getchar(); scanf("%c", &(*g)->adjlist[i].data); (*g)->adjlist[i].firstedge = NULL; } //3. printf(" input side information: \n"); for (k = 0; k < (*g)->arc_num; k++){ getchar(); scanf("%d %d", &i, &j); P = (EdgeNode *)malloc(sizeof(EdgeNode)); // (p-> adj_VEX_index = j; I p->next = (*g)-> adjList [I]. [I]. Firstedge = p (*g)-> AdjList [I]. Firstedge = p; //j->i if(! (* g) - > is_directed) {/ / j -- -- -- -- -- > I / / (1) to create a new node p = (EdgeNode *) malloc (sizeof (EdgeNode)); // ip_vex_index = 1; P ->next = (*g)->adjlist[j]. [I]. Firstedge = p -> adjList [j]. Firstedge = p; } } } void putGraph(GraphLink g){ int i; Printf (" Store information in adjacency list :\n"); For (I = 0; i < g->node_num; i++) { EdgeNode * p = g->adjlist[i].firstedge; while (p) { printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data); p = p->next; } printf("\n"); } } int main(int argc, const char * argv[]) { // insert code here... Printf (" Store of adjacency list implementation graph \n"); /* How many vertices, edges, and directed are stored in an adjacency list? : 4 5 0 Input vertex information: 0 1 2 3 Input edge information: 0 1 0 2 0 3 2 1 2 3 Store information in the adjacency list: 0 - > 3 - > 2 - > 1 0 0 1 - > 2 - > 2 - > 2 - > 3 0 1 2 3-2-3 - > > 0 > 0 * / / * adjacency graph table storage input vertex number, number of edges and has to? : 4 5 1 Input vertex information: 0 1 2 3 Input edge information: 1 0 1 2 2 1 2 0 0 3 Store information in the adjacency list: 0->3 1->2 1->0 2->0 2->1 */ GraphLink g = (Graph *)malloc(sizeof(Graph)); creatGraph(&g); putGraph(g); return 0; }Copy the code

Graph traversal

### Graph traversal – depth-first traversal

#### graph traversal – adjacency matrix depth – first traversal code implementation path

  1. Input the vertex and edge information into the graph structure;
  2. Create a Visited array that identifies whether the vertices have already been traversed.
  3. Initialize the Visited array, setting the elements of the array to FALSE
  4. Select vertices to begin traversal (note the case of non-connected graphs).
  5. Inbound recursion; Prints the vertex information corresponding to I. And marks the vertex as traversed.
  6. Loop through the edge table to determine whether the current arc[I][j] is equal to 1, and the current vertex has not been traversed, then continue recursive DFS;
#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /* typepedef int Boolean; /* typepedef int Boolean; /* Boolean is a Boolean type whose value is TRUE or FALSE */ typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; */ #define MAXSIZE 9 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITYC 65535 typedef struct { VertexType vexs[MAXVEX]; /* EdgeType arc[MAXVEX][MAXVEX]; /* int numVertexes, numEdges; /* The number of vertices and edges in the graph */}MGraph; Void CreateMGraph(MGraph *G) {int I, j; G->numEdges=15; G->numVertexes=9; */ G->vexs[0]='A'; G->vexs[1]='B'; G->vexs[2]='C'; G->vexs[3]='D'; G->vexs[4]='E'; G->vexs[5]='F'; G->vexs[6]='G'; G->vexs[7]='H'; G->vexs[8]='I'; /* for (I = 0; i < G->numVertexes; i++) { for ( j = 0; j < G->numVertexes; j++) { G->arc[i][j]=0; */ G->arc[0][1]=1; G->arc[0][5]=1; G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1; G->arc[3][7]=1; G->arc[3][6]=1; G->arc[3][8]=1; G->arc[4][5]=1; G->arc[4][7]=1; G->arc[5][6]=1; G->arc[6][7]=1; /*5. Undirected graphs are symmetric matrices. */ for(I = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; / / Boolean visited[MAXVEX]; //1. Identify whether the vertex is marked; //2. Select a vertex to start with (note: in the case of an unconnected graph) //3. Enter recursion, print I point information, identification; Visted void DFS(MGraph G,int I){//1. Visited [I] = TRUE; printf("%c",G.vexs[i]); //2.0~numVertexes for(int j = 0; j < G.numVertexes; j++){ if(G.arc[i][j] == 1 && ! visited[j]) DFS(G, j); } } void DFSTravese(MGraph G){ //1. Initialize for(int I =0; i<G.numVertexes; i++){ visited[i] = FALSE; } // a vertex for(int I = 0; i<G.numVertexes; i++){ if(! visited[i]){ DFS(G, i); } } } int main(int argc, const char * argv[]) { // insert code here... Printf (" Adjacency matrix depth-first traversal! \n"); MGraph G; CreateMGraph(&G); DFSTravese(G); printf("\n"); return 0; }Copy the code

Depth-first traversal results:AFGHEDICB#### graph traversal – adjacency list of graph traversal processing

#### graph traversal – adjacency list depth – first traversal code implementation path

  1. Use an adjacency matrix to store information in an adjacency list
  2. Create a Visited array that identifies whether the vertices have already been traversed.
  3. Initialize the Visited array, setting the elements of the array to FALSE
  4. Select vertices to begin traversal (note the case of non-connected graphs).
  5. Inbound recursion; Prints the vertex information corresponding to I. And marks the vertex as traversed.
  6. Iterate over the edge table to determine whether the current vertex is equal to 1, and the current vertex has not been traversed, then continue recursive DFS;
#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 9 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITYC 65535 typedef int Status; /* typepedef int Boolean; /* typepedef int Boolean; /* Boolean is a Boolean type whose value is TRUE or FALSE */ typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; / / typepedef struct {VertexType vexs[MAXVEX]; /* EdgeType arc[MAXVEX][MAXVEX]; /* int numVertexes, numEdges; /* The number of vertices and edges in the graph */}MGraph; Adjacent table structure / * * * * * * * * * * * * * * * * * * * * / typedef struct EdgeNode / * * / side table nodes {int adjvex; /* Adjacency field, store the corresponding subscript */ int weight; */ struct EdgeNode *next; */ * EdgeNode; Typedef struct VertexNode /* VertexNode */ {int in; /* char data; /* EdgeNode *firstedge; }VertexNode, AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; /* The number of vertices and edges in the graph */}graphAdjList,* graphAdjList; Void CreateMGraph(MGraph *G) {int I, j; G->numEdges=15; G->numVertexes=9; */ G->vexs[0]='A'; G->vexs[1]='B'; G->vexs[2]='C'; G->vexs[3]='D'; G->vexs[4]='E'; G->vexs[5]='F'; G->vexs[6]='G'; G->vexs[7]='H'; G->vexs[8]='I'; /* for (I = 0; i < G->numVertexes; i++) { for ( j = 0; j < G->numVertexes; j++) { G->arc[i][j]=0; */ G->arc[0][1]=1; G->arc[0][5]=1; G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1; G->arc[3][7]=1; G->arc[3][6]=1; G->arc[3][8]=1; G->arc[4][5]=1; G->arc[4][7]=1; G->arc[5][6]=1; G->arc[6][7]=1; /*5. Undirected graphs are symmetric matrices. */ for(I = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; Void CreateALGraph(MGraph G,GraphAdjList *GL){//1. *GL = (GraphAdjList)malloc(sizeof(GraphAdjList)); (*GL)->numVertexes = G.numVertexes; (*GL)->numEdges = G.numEdges; For (int I = 0; i < G.numVertexes; I ++) {// Adlist [I]. In = 0; // Adlist (*GL)-> adList [I]. Data = g.vexs [I]; (*GL)->adjList[I]. Firstedge = NULL; } //3. for (int i = 0; i < G.numVertexes; i++) { for (int j = 0; j < G.numVertexes; J ++) {if (g.arc [I][j] == 1) {if (g.arc [I][j] == 1) {I ->j e = (EdgeNode *)malloc(sizeof(EdgeNode)); // The sequence number is j e->adjvex = j; E ->next = (*GL)->adjList[I]. (*GL)->adjList[i].firstedge = e; // The entry degree on vertex j ++; (*GL)->adjList[j].in++; // // create adjacent node in edge table j-> I // e = (EdgeNode *)malloc(sizeof(EdgeNode)); // // The serial number of the adjacency is j // e-> Adjvex = I; // e->next = (*GL)->adjList[j]. // (*GL)->adjList[j].firstedge = e; // // Entry on vertex j ++; // (*GL)->adjList[i].in++; } } } } Boolean visited[MAXSIZE]; Void DFS(GraphAdjList GL, int I) {EdgeNode *p; visited[i] = TRUE; Printf ("%c ",GL->adjList[I].data); p = GL->adjList[i].firstedge; //3. while (p) { if(! visited[p->adjvex]) DFS(GL,p->adjvex); p = p->next; Averse averse(GraphAdjList GL) {// averse averse(GraphAdjList GL) {// averse averse(GraphAdjList GL) {// averse averse(GraphAdjList GL) {// averse averse(GraphAdjList GL) {// averse averse(GraphAdjList GL); Set access record array to FALSE by default for (int I = 0; i < GL->numVertexes; I ++) {/* Initialize all vertex states to be unvisited */ visited[I] = FALSE; } //2. Select a vertex to start DFS traversal. For example A for(int I = 0; i < GL->numVertexes; I++) // call DFS on unvisited vertices, only once if connected graph. If (! visited[i]) DFS(GL, i); } int main(int argc, const char * argv[]) { // insert code here... Printf (" Adjacency list depth-first traversal! \n"); MGraph G; GraphAdjList GL; CreateMGraph(&G); CreateALGraph(G,&GL); DFSTraverse(GL); printf("\n"); return 0; }Copy the code

Graph traversal – breadth-first traversal features: 1. Put the root node at the end of the queue column. 2. Take one element at a time from the head of the queue column, look at all the next-level elements of that element, and place them at the end of the queue column. And write this element down as the precursor to its next level. 3. End the program when you find the element you are looking for. 4. If the entire tree is not found, end the program.#### adjacency matrix breadth-first traversal code implementation logic

#include <stdio.h> #include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR  0 #define TRUE 1 #define FALSE 0 typedef int Status; /* typepedef int Boolean; /* typepedef int Boolean; /* Boolean is a Boolean type whose value is TRUE or FALSE */ typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; */ #define MAXSIZE 9 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITYC 65535 typedef struct { VertexType vexs[MAXVEX]; /* EdgeType arc[MAXVEX][MAXVEX]; /* int numVertexes, numEdges; /* The number of vertices and edges in the graph */}MGraph; Void CreateMGraph(MGraph *G) {int I, j; G->numEdges=15; G->numVertexes=9; */ G->vexs[0]='A'; G->vexs[1]='B'; G->vexs[2]='C'; G->vexs[3]='D'; G->vexs[4]='E'; G->vexs[5]='F'; G->vexs[6]='G'; G->vexs[7]='H'; G->vexs[8]='I'; /* for (I = 0; i < G->numVertexes; i++) { for ( j = 0; j < G->numVertexes; j++) { G->arc[i][j]=0; */ G->arc[0][1]=1; G->arc[0][5]=1; G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1; G->arc[3][7]=1; G->arc[3][6]=1; G->arc[3][8]=1; G->arc[4][5]=1; G->arc[4][7]=1; G->arc[5][6]=1; G->arc[6][7]=1; /*5. Undirected graphs are symmetric matrices. */ for(I = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; / / struct {int data[MAXSIZE]; / / struct {int data[MAXSIZE]; int front; /* header pointer */ int rear; /* Queue */ Queue */ Queue */ Queue */ Queue */ Queue */ /* Initialize an empty Queue Q */ Status InitQueue(Queue *Q) {Q->front=0; Q->rear=0; return OK; } /* Return TRUE if Queue Q is empty, FALSE otherwise */ Status QueueEmpty(Queue Q) {if(q.front == q.ear) /* Queue empty flag */ return TRUE; else return FALSE; } /* If the queue is full, */ Status EnQueue(Queue *Q,int e) {if ((Q->rear+1)%MAXSIZE == Q->front) /* Return ERROR; Q->data[Q->rear]=e; */ rear=(Q->rear+1)%MAXSIZE; /* rear pointer moves one position back, */ /* back to array header */ return OK; */ Status DeQueue(Queue *Q,int *e) {if (Q->front == Q->rear) /* return ERROR; *e=Q->data[Q->front]; /* Assign the front element to e */ Q->front=(Q->front+1)%MAXSIZE; /* front moves back one bit, */ /* to the end of the array */ return OK; } / Queue End * * * * * * * * * * * * * * * * * * * * * * / / * 4.3 adjacency matrix breadth-first traversal - code * / Boolean visited [MAXVEX]; /* averse(MGraph G){int temp = 0; /* Averse (MGraph G); //1. Queue Q; InitQueue(&Q); For (int I = 0; i < G.numVertexes; i++) { visited[i] = FALSE; } //3. Loop over every vertex in the adjacency list (only once for connected graphs, for unconnected graphs) i < G.numVertexes; i++) { if(! visited[i]){ visited[i] = TRUE; printf("%c ",G.vexs[i]); //4. EnQueue(&q, I); while (! QueueEmpty(Q)) {// queue (&q, &i); for (int j = 0; j < G.numVertexes; j++) { if(G.arc[i][j] == 1 && ! visited[j]) { visited[j] = TRUE; printf("%c ",G.vexs[j]); EnQueue(&Q, j); } } } } } } int main(int argc, const char * argv[]) { // insert code here... Printf (" Adjacency matrix breadth-first traversal! \n"); MGraph G; CreateMGraph(&G); BFSTraverse(G); printf("\n"); return 0; }Copy the code

#### adjacency list breadth-first traversal code implementation logic

#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 9 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITYC 65535 typedef int Status; /* typepedef int Boolean; /* typepedef int Boolean; /* Boolean is a Boolean type whose value is TRUE or FALSE */ typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; / / typepedef struct {VertexType vexs[MAXVEX]; /* EdgeType arc[MAXVEX][MAXVEX]; /* int numVertexes, numEdges; /* The number of vertices and edges in the graph */}MGraph; Adjacent table structure / * * * * * * * * * * * * * * * * * * * * / typedef struct EdgeNode / * * / side table nodes {int adjvex; /* Adjacency field, store the corresponding subscript */ int weight; */ struct EdgeNode *next; */ * EdgeNode; Typedef struct VertexNode /* VertexNode */ {int in; /* char data; /* EdgeNode *firstedge; }VertexNode, AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; /* The number of vertices and edges in the graph */}graphAdjList,* graphAdjList; Void CreateMGraph(MGraph *G) {int I, j; G->numEdges=15; G->numVertexes=9; */ G->vexs[0]='A'; G->vexs[1]='B'; G->vexs[2]='C'; G->vexs[3]='D'; G->vexs[4]='E'; G->vexs[5]='F'; G->vexs[6]='G'; G->vexs[7]='H'; G->vexs[8]='I'; /* for (I = 0; i < G->numVertexes; i++) { for ( j = 0; j < G->numVertexes; j++) { G->arc[i][j]=0; */ G->arc[0][1]=1; G->arc[0][5]=1; G->arc[1][2]=1; G->arc[1][8]=1; G->arc[1][6]=1; G->arc[2][3]=1; G->arc[2][8]=1; G->arc[3][4]=1; G->arc[3][7]=1; G->arc[3][6]=1; G->arc[3][8]=1; G->arc[4][5]=1; G->arc[4][7]=1; G->arc[5][6]=1; G->arc[6][7]=1; /*5. Undirected graphs are symmetric matrices. */ for(I = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; Void CreateALGraph(MGraph G,GraphAdjList *GL){//1. *GL = (GraphAdjList)malloc(sizeof(GraphAdjList)); (*GL)->numVertexes = G.numVertexes; (*GL)->numEdges = G.numEdges; For (int I = 0; i < G.numVertexes; I ++) {// Adlist [I]. In = 0; // Adlist (*GL)-> adList [I]. Data = g.vexs [I]; (*GL)->adjList[I]. Firstedge = NULL; } //3. for (int i = 0; i < G.numVertexes; i++) { for (int j = 0; j < G.numVertexes; J ++) {if (g.arc [I][j] == 1) {if (g.arc [I][j] == 1) {I ->j e = (EdgeNode *)malloc(sizeof(EdgeNode)); // The sequence number is j e->adjvex = j; E ->next = (*GL)->adjList[I]. (*GL)->adjList[i].firstedge = e; // The entry degree on vertex j ++; (*GL)->adjList[j].in++; // // create adjacent node in edge table j-> I // e = (EdgeNode *)malloc(sizeof(EdgeNode)); // // The serial number of the adjacency is j // e-> Adjvex = I; // e->next = (*GL)->adjList[j]. // (*GL)->adjList[j].firstedge = e; // // Entry on vertex j ++; // (*GL)->adjList[i].in++; }}}} /* 5.2 *** *** */ /* struct {int data[MAXSIZE]; int front; /* header pointer */ int rear; /* Queue */ Queue */ Queue */ Queue */ Queue */ Queue */ /* Initialize an empty Queue Q */ Status InitQueue(Queue *Q) {Q->front=0; Q->rear=0; return OK; } /* Return TRUE if Queue Q is empty, FALSE otherwise */ Status QueueEmpty(Queue Q) {if(q.front == q.ear) /* Queue empty flag */ return TRUE; else return FALSE; */ Status EnQueue(Queue *Q,int e) {if ((Q->rear+1)%MAXSIZE == Q->front) /* Queue full */ return ERROR; Q->data[Q->rear]=e; */ rear=(Q->rear+1)%MAXSIZE; /* rear pointer moves one position back, */ /* back to array header */ return OK; */ Status DeQueue(Queue *Q,int *e) {if (Q->front == Q->rear) /* return ERROR; *e=Q->data[Q->front]; /* Assign the front element to e */ Q->front=(Q->front+1)%MAXSIZE; /* front moves back one bit, */ /* to the end of the array */ return OK; } / * * * * * * * * * * * * * * * * * * * * * * * * Queue End * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / / * 5.3 adjacency table breadth-first traversal * / Boolean visited [MAXSIZE]; // averse averse(GraphAdjList GL){// averse averse(GraphAdjList GL){// averse averse(GraphAdjList GL){// averse averse(GraphAdjList GL){// averse averse(GraphAdjList GL); Create a node. Queue Q; InitQueue(&Q); For (int I = 0; i < GL->numVertexes; i++) visited[i] = FALSE; Int I = 0; int I = 0; int I = 0; i < GL->numVertexes; I++){//4. If (! visited[i]){ visited[i] = TRUE; Printf ("%c ",GL->adjList[I].data); EnQueue(&Q, i); while (! QueueEmpty(Q)) { DeQueue(&Q, &i); p = GL->adjList[i].firstedge; While (p) {// judge if(! visited[p->adjvex]){ visited[p->adjvex] = TRUE; printf("%c ",GL->adjList[p->adjvex].data); EnQueue(&Q, p->adjvex); } p = p->next; } } } } } int main(int argc, const char * argv[]) { // insert code here... Printf (" adjacency list breadth-first traversal \n"); MGraph G; GraphAdjList GL; CreateMGraph(&G); CreateALGraph(G,&GL); BFSTraverse(GL); printf("\n"); return 0; }Copy the code