Directory
Understanding of 4 kinds of graphs
Adjacency Matrix Representation of Graph
Code
Understanding of 4 kinds of graphs
Directed graph: Indicates that there is an order relationship between two vertices, and the two vertices are ordered pairs
Undirected graph: Indicates that two vertices have no order relationship, and two vertices are unordered pairs
Directed network: weights are added to the directed graph
Undirected network: weights are added to the undirected graph
Adjacency matrix representation of graph
We use a matrix to represent the relationship between the vertices in the graph. When there are n vertices, we need to store n vertex information and n*n arc information.
As shown in the figure is the adjacency matrix of a directed graph , the data 1 in row v1 and v3 represents an arc from the v1 vertex to the v3 vertex in the graph.
We stipulate that, for a graph: use 1 and 0 to indicate whether two vertices are connected; for a network, the data in the matrix indicates the weight, and if there is no relationship, use infinity to indicate.
undirected graph display
directed graph display
undirected web display
Directed display
Using the adjacency matrix is suitable for judging whether two vertices have edges, and it is easy to find the degree of each vertex
Code Implementation
The input here is because there are characters and numbers. If you use scanf to input, pay special attention to the ‘\
‘ problem left by using getchar to cancel the previous input. If you use cin syntax, you don’t need to worry about these issues
typedef struct ArcCell {
int adj; // Vertex relationship, if it is a network, no weight is represented by infinity; if it is a graph, 0 means no connection, 1 means there is a connection between two points
char* info;//A pointer indicating arc-related information
}ArcCell;
typedef struct
{
char vexs[MAX_VERTEX_NUM];//vertex vector
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//adjacency matrix
int vexnum; // number of vertices
int arcnum; // number of arcs
}MGraph;
/**********Determine the vertex position function**********/
int LocateVex(MGraph & G, char num)
{
int i = 0;
for (i = 0; i < G.vexnum; i ++ )
{
if ( G.vexs[i]==num)
{
return i;
}
}
return -1;
}
/***********Input arc information function**********/
void Input(char* & p)
{
char arr[10] = { 0 };
scanf("%s", arr);
p = arr;
}
/**********Constructing an undirected network**********/
void CreateUDN(MGraph & G)
{
int IncInfo;
int i = 0;
int j = 0;
int k = 0;
printf("Please input the number of vertices and arcs of the graph, whether it contains information:");
scanf("%d%d%d", & amp;G.vexnum, & amp;G.arcnum, & amp;IncInfo);//IncInfo is 0 means each arc does not contain other information
\t
for ( i = 0; i < G.vexnum; i ++ )//Create vertex table
{
printf("Please enter the %d vertex information:\
", i + 1);
//getchar(); //Get the \
character entered above. If you use scanf input, be sure to add getchar() to get the \
character entered above, otherwise it will read the \
character entered above to G.vexs[i]
//G.vexs[i]= getchar();
cin >> G.vexs[i];
}
//Initialize the adjacency matrix
for (i = 0; i< G.vexnum; i ++ )
{
for (j = 0; j < G.vexnum; j ++ )
{
G.arcs[i][j].adj = INT_MAX;
G.arcs[i][j].info = NULL;
}
}
// construct adjacency matrix
char a, b;
int c ;
for (k = 0; k < G. arcnum; k ++ )
{
//getchar();//Get the \
character entered above. If you use scanf input, be sure to add getchar() to get the \
character entered above, otherwise it will read the \
character entered above to a
printf("Please enter the start point information, end point information, weight:\
");
//scanf("%c %c %d", &a, &b, &c);
cin >> a >> b >> c;
i = LocateVex(G, a);
j = LocateVex(G, b);
G.arcs[i][j].adj = c;
// undirected graph, symmetric
G.arcs[j][i].adj=c;
//If the arc has relevant information, enter
if (IncInfo)
{
Input(G. arcs[i][j]. info);
}
\t\t
}
}
/**********Construct undirected graph**********/
void CreateUDG(MGraph & G)
{
int IncInfo = 0;
int i = 0;
int j = 0;
int k=0;
printf("Please input the number of vertices and arcs of the graph, whether it contains information:");
scanf("%d %d %d", & amp;G.vexnum, & amp;G.arcnum, & amp;IncInfo);//IncInfo is 0, indicating that each arc does not contain other information;
for (i = 0; i < G.vexnum; i ++ )//Create a vertex table
{
printf("Please enter the %d vertex information:\
", i + 1);
getchar(); //Get the \
character entered above
G.vexs[i] = getchar();
}
//Initialize the adjacency matrix
for (i = 0; i < G.vexnum; i ++ )
{
for (j = 0; j < G.vexnum; j ++ )
{
G.arcs[i][j].adj = 0;
G.arcs[i][j].info= NULL;
}
}
// construct adjacency matrix
char a, b;
for (k = 0; k < G. arcnum; k ++ )
{
getchar(); //Get the \
character entered above
printf("Please enter the start point and end point of the edge:\
");
scanf("%c %c", &a, &b);
i = LocateVex(G, a);
j = LocateVex(G, b);
G.arcs[i][j].adj = 1;
//If the arc has relevant information, enter
if (IncInfo)
{
Input(G. arcs[i][j]. info);
}
// undirected graph, symmetric
G.arcs[j][i] = G.arcs[i][j];
}
}
/**********Construct a directed network**********/
void CreateDN(MGraph & G)
{
int IncInfo = 0;
int i = 0;
int j = 0;
int k = 0;
printf("Please input the number of vertices and arcs of the graph, whether it contains information:");
scanf("%d %d %d", & amp;G.vexnum, & amp;G.arcnum, & amp;IncInfo);//IncInfo is 0 means each arc does not contain other information
for (i = 0; i < G.vexnum; i ++ )//Create a vertex table
{
printf("Please enter the %dth vertex information: ", i + 1);
getchar(); //Get the \
character entered above
G.vexs[i] = getchar();
\t
}
//Initialize the adjacency matrix
for (i = 0; i < G.vexnum; i ++ )
{
for (j = 0; j < G.vexnum; j ++ )
{
G.arcs[i][j] = { INT_MAX , NULL };
}
}
// construct adjacency matrix
char a, b;
int c = 0;
for (k = 0; k < G. arcnum; k ++ )
{
getchar();
printf("Please enter the start point information, end point information, weight\
");
scanf("%c %c %d", &a, &b, &c);
i = LocateVex(G, a);
j = LocateVex(G, b);
G.arcs[i][j].adj = c;
//If the arc has relevant information, enter
if (IncInfo)
{
Input(G. arcs[i][j]. info);
}
//There is a difference between the directed network and the undirected network here
}
}
/**********Constructing a directed graph**********/
void CreateDG(MGraph & G)
{
int IncInfo = 0;
int i = 0;
int j = 0;
int k = 0;
printf("Please input the number of vertices and arcs of the graph, whether it contains information:");
scanf("%d %d %d", & amp;G.vexnum, & amp;G.arcnum, & amp;IncInfo);//IncInfo is 0 means each arc does not contain other information
for (i = 0; i < G.vexnum; i ++ )//Create a vertex table
{
printf("Please enter the %dth vertex information: ", i + 1);
getchar(); //Get the \
character entered above
G.vexs[i] = getchar();
}
//Initialize the adjacency matrix
for (i = 0; i < G.vexnum; i ++ )
{
for (j = 0; j < G.vexnum; j ++ )
{
G.arcs[i][j].adj= 0;
G.arcs[i][j].info = NULL ;
}
}
// construct adjacency matrix
char a, b;
for (k = 0; k < G. arcnum; k ++ )
{
getchar(); //Get the \
character entered above
printf("Please enter the starting point information and end point information\
");
scanf("%c %c", &a, &b);
i = LocateVex(G, a);
j = LocateVex(G, b);
G.arcs[i][j].adj = 1;
//If the arc has relevant information, enter
if (IncInfo)
{
Input(G. arcs[i][j]. info);
}
//There is a difference between directed graphs and undirected graphs
}
}
/**********Print out the adjacency matrix**********/
void print_Matrix(MGraph G)
{
int i, j;
printf("\
The vertices of the graph are:");
for (i = 0; i < G.vexnum; i ++ )
{
printf("%c ", G.vexs[i]);
}
printf("\
Output adjacency matrix:\
");
for (i = 0; i < G.vexnum; i ++ )
{
for (j = 0; j < G.vexnum; j ++ )
{
if (G.arcs[i][j].adj== INT_MAX)
printf("\t%8s", "∞");//judgment graph and network
else
printf("\t?", G.arcs[i][j].adj);
}
printf("\
");
}
}