The data nodes in the graph have a many-to-many relationship. A node has multiple predecessors and multiple successors. There are even undirected graphs that do not distinguish between predecessors and successors, and only require adjacency relationships between nodes. Therefore, describing this data relationship requires a new data structure.
A graph consists of a vertex set and an edge set. A vertex represents a data node, and an edge represents the adjacency relationship between data vertices.
There are various data structures describing graphs. Teacher Xiaoyu in bilibili also said that there is no single answer to program programming. Just solve the problem. Because the degree of freedom in programming is greater than in the field of mathematics, there is no one correct answer like mathematics problems. and a few solutions. A program can solve problems, and a program that is clear and easy to understand is a good program. Making some changes and improvements based on the predecessors can be considered a better program.
The graph can be described by an adjacency matrix, which contains an array member that stores all vertices, and a two-dimensional matrix that stores the adjacency relationship between vertices. The matrix element value indicates whether the two vertices corresponding to the two subscripts have an adjacency relationship. For Weight edge, then the matrix element value represents the weight of the corresponding edge, and there is also a member representing the number of vertices and a member representing the number of edges. Such a structure variable can represent all the data information of the graph.
Graphs can also be represented by adjacency lists. Because for sparse graphs, using adjacency matrices to store edges is too wasteful of memory. The structure members of the adjacency list include a one-dimensional array composed of a singly linked list header, a total number of vertices, and a total number of edges. Each header is also a structure variable: one member stores the vertex, and another member stores a pointer to the adjacency list node. The adjacency list node is also a structure variable. One of its members stores the subscript of another vertex adjacent to the top of the table in the header array. One member stores the weight of the corresponding edge. The last member is a pointer to the next table node. . In this way, such an adjacency list structure variable also stores all the information of the graph.
This example is an exercise, and the functions included are as follows:
Function createGraphAdjMatrix creates an adjacency matrix from all fragmentary known information of the graph.
The function createGraphAdjList creates an adjacency list from all the known information of the graph.
Function matrixToList creates an adjacency list from an adjacency matrix.
The function listToMatrix creates an adjacency matrix from an adjacency list; it actually assigns values to each member of the structure.
The function displayGraphAdjMatrix outputs all the information of the graph from the adjacency matrix, expressed in a matrix.
The function displayGrapgAdjList outputs all the information of the graph from the adjacency list, expressed as a linear list. The purpose of these two outputs is also to check whether the structure variables of the graph are established accurately.
The complete code is as follows, first the file code where the main function is located:
#include<iostream>
#include<stdio.h>
using namespace std;
#defineMAXVERTEX 15
#define INFINI 65555
struct GraphAdjaMatrix {<!-- -->
char vertexes[MAXVERTEX];
int edges[MAXVERTEX][MAXVERTEX];
int numVertexes;
int numEdges;
};
struct AdjaListNode {<!-- -->
int indexOfVertex;
int weightOfEdge;
AdjaListNode* pt;
};
struct AdjListHead {<!-- -->
char vertex;
AdjaListNode* pt;
};
struct GraphAdjaList {<!-- -->
AdjListHead vertexes[MAXVERTEX];
int numVertexes;
int numEdges;
};
extern void createGraphAdjMatrix(GraphAdjaMatrix & graphAdjMatrix,
int numVertexes,int numEdges,int edges[][6],char vertexes[]);
extern void createGraphAdjList(GraphAdjaList & graphAdjList,
int numVertexes, int numEdges, int edges[][6], char vertexes[]);
extern void matrixToList(GraphAdjaMatrix & graphAdjMatrix,
GraphAdjaList & graphAdjList);
extern void listToMatrix(GraphAdjaList & graphAdjList,
GraphAdjaMatrix & graphAdjMatrix);
extern void dispalyGraphAdjMatrix(GraphAdjaMatrix & graphAdjMatrix);
extern void displayGrapgAdjList(GraphAdjaList & graphAdjList);
int main() {<!-- -->
GraphAdjaMatrix graphAdjMatrix;
GraphAdjaList graphAdjList;
int numVertexes = 6, numEdges = 10;
int edges[][6] = {<!-- --> {<!-- -->0,5,INFINI,7,INFINI,INFINI},
{<!-- -->INFINI,0,4,INFINI,INFINI,INFINI},
{<!-- -->8,INFINI,0,INFINI,INFINI,9},
{<!-- -->INFINI,INFINI,5,0,INFINI,6},
{<!-- -->INFINI,INFINI,INFINI,5,0,INFINI},
{<!-- -->3,INFINI,INFINI,INFINI,1,0} };
char vertexes[] = {<!-- -->'a','b','c','d','e','f'};
createGraphAdjMatrix(graphAdjMatrix,numVertexes,numEdges,edges,vertexes);
createGraphAdjList(graphAdjList,numVertexes,numEdges,edges,vertexes);
GraphAdjaMatrix graphAdjMatrixNew;
GraphAdjaList graphAdjListNew;
matrixToList(graphAdjMatrix,graphAdjListNew);
listToMatrix(graphAdjList,graphAdjMatrixNew);
dispalyGraphAdjMatrix(graphAdjMatrixNew);
cout << endl;
displayGrapgAdjList(graphAdjListNew);
return 0;
}
Then follows the source file code where each function is located:
#include<iostream>
#include<stdio.h>
using namespace std;
#defineMAXVERTEX 15
#define INFINI 65555
struct GraphAdjaMatrix {<!-- -->
char vertexes[MAXVERTEX];
int edges[MAXVERTEX][MAXVERTEX];
int numVertexes;
int numEdges;
};
struct AdjaListNode {<!-- -->
int indexOfVertex;
int weightOfEdge;
AdjaListNode* pt;
};
struct AdjListHead {<!-- -->
char vertex;
AdjaListNode* pt;
};
struct GraphAdjaList {<!-- -->
AdjListHead vertexes[MAXVERTEX];
int numVertexes;
int numEdges;
};
void createGraphAdjMatrix(GraphAdjaMatrix & graphAdjMatrix,
int numVertexes, int numEdges, int edges[][6], char vertexes[]) {<!-- -->
graphAdjMatrix.numVertexes = numVertexes;
graphAdjMatrix.numEdges = numEdges;
\t
for (int i = 0; i < numVertexes; i + + )
graphAdjMatrix.vertexes[i] = vertexes[i];
for (int row = 0; row < numVertexes; row + + )
for (int column = 0; column < numVertexes; column + + )
graphAdjMatrix.edges[row][column] = edges[row][column];
}
void createGraphAdjList(GraphAdjaList & graphAdjList,
int numVertexes, int numEdges, int edges[][6], char vertexes[]){<!-- -->
graphAdjList.numEdges = numEdges;
graphAdjList.numVertexes = numVertexes;
for (int i = 0; i < MAXVERTEX; i + + )
graphAdjList.vertexes[i].pt = NULL;
for (int i = 0; i < numVertexes; i + + )
graphAdjList.vertexes[i].vertex = vertexes[i];
AdjaListNode* ptTail = NULL,*ptNew;
int i, j;
for ( i = 0; i < numVertexes; i + + )
for (j = 0; j < numVertexes; j + + )
if (edges[i][j] != 0 & amp; & amp; edges[i][j] != INFINI) {<!-- -->
ptNew = new AdjaListNode;
ptNew->indexOfVertex = j;
ptNew->weightOfEdge = edges[i][j];
\t\t\t
if (graphAdjList.vertexes[i].pt == NULL) {<!-- -->
ptNew->pt = NULL;
graphAdjList.vertexes[i].pt = ptNew;
ptTail = ptNew;
}
else {<!-- -->
ptNew->pt = ptTail->pt;
ptTail->pt = ptNew;
ptTail = ptNew;
}
}
}
void matrixToList(GraphAdjaMatrix & graphAdjMatrix,
GraphAdjaList & graphAdjList) {<!-- -->
graphAdjList.numEdges = graphAdjMatrix.numEdges;
graphAdjList.numVertexes = graphAdjMatrix.numVertexes;
for (int i = 0; i < MAXVERTEX; i + + )
graphAdjList.vertexes[i].pt = NULL;
for (int i = 0; i < graphAdjList.numVertexes; i + + )
graphAdjList.vertexes[i].vertex = graphAdjMatrix.vertexes[i];
AdjaListNode* ptTail = NULL, * ptNew;
int i, j;
for (i = 0; i < graphAdjList.numVertexes; i + + )
for (j = 0; j < graphAdjList.numVertexes; j + + )
if (graphAdjMatrix.edges[i][j] != 0 & amp; & amp;
graphAdjMatrix.edges[i][j] != INFINI) {<!-- -->
ptNew = new AdjaListNode;
ptNew->indexOfVertex = j;
ptNew->weightOfEdge = graphAdjMatrix.edges[i][j];
if (graphAdjList.vertexes[i].pt == NULL) {<!-- -->
ptNew->pt = NULL;
graphAdjList.vertexes[i].pt = ptNew;
ptTail = ptNew;
}
else {<!-- -->
ptNew->pt = ptTail->pt;
ptTail->pt = ptNew;
ptTail = ptNew;
}
}
}
void listToMatrix(GraphAdjaList & graphAdjList,
GraphAdjaMatrix & amp;graphAdjMatrix) {<!-- -->
graphAdjMatrix.numEdges = graphAdjList.numEdges;
graphAdjMatrix.numVertexes = graphAdjList.numVertexes;
for (int i = 0; i < graphAdjMatrix.numVertexes; i + + )
graphAdjMatrix.vertexes[i] = graphAdjList.vertexes[i].vertex;
int row, column;
//Initialization of the adjacency matrix, the main diagonal is 0, and the rest are infinity.
for(row = 0; row < graphAdjMatrix.numVertexes; row + + )
for(column = 0; column < graphAdjMatrix.numVertexes; column + + )
if (row == column)
graphAdjMatrix.edges[row][column] = 0;
else
graphAdjMatrix.edges[row][column] = INFINI;
\t
AdjaListNode* pt;
for (row = 0; row < graphAdjMatrix.numVertexes; row + + ) {<!-- -->
pt = graphAdjList.vertexes[row].pt;
while (pt != NULL) {<!-- -->
column = pt->indexOfVertex;
graphAdjMatrix.edges[row][column] = pt->weightOfEdge;
pt = pt->pt;
}
}
}
void dispalyGraphAdjMatrix(GraphAdjaMatrix & amp;graphAdjMatrix) {<!-- -->
cout << "adjacensy matrix :" << endl;
int row,column;
printf("<",' ');
for (row = 0; row < graphAdjMatrix.numVertexes; row + + )
printf("<",graphAdjMatrix.vertexes[row]);
printf("\
");
for (row = 0; row < graphAdjMatrix.numVertexes; row + + ) {<!-- -->
printf("%-3c", graphAdjMatrix.vertexes[row]);
for (column = 0; column < graphAdjMatrix.numVertexes; column + + )
if (graphAdjMatrix.edges[row][column] == INFINI)
printf("%3s", "∞");
else
printf("=",graphAdjMatrix.edges[row][column]);
cout << endl;
}
}
void displayGrapgAdjList(GraphAdjaList & graphAdjList) {<!-- -->
cout << "graph adjacency list:" << endl;
AdjaListNode* pt;
for (int i = 0; i < graphAdjList.numVertexes; i + + ) {<!-- -->
printf(",:",graphAdjList.vertexes[i].vertex);
pt = graphAdjList.vertexes[i].pt;
while (pt != NULL) {<!-- -->
printf("](%d)",pt->indexOfVertex,pt->weightOfEdge);
pt = pt->pt;
}
cout << endl;
}
}
The test results are as follows:
thanks for reading