【Problem Description】
The road traffic between cities can be represented by an undirected graph. As shown below:
The vertices represent the cities, the edges represent the roads connecting the cities, and the weights on the edges represent the length of the roads between the cities.
Programming solves the following problems:
(1) Input city information and road information between cities, and establish the adjacency matrix storage structure of the graph
(2) In order to enable communication between cities, optical fibers will be laid along the roads, and a reasonable plan will be given to minimize the total cost of optical fibers.
【Input form】
Enter the city in the first line, separate the cities with spaces, and enter q to end.
In the next few lines, enter two cities and the length of the road between the cities in each line, separated by spaces. Enter q to end.
Enter the starting city name.
[Output format] The minimum spanning tree obtained from the start city, the output format is (start city, end city).
Note: There are English commas between cities and no spaces.
【Sample input】
Chengdu Xi’an Kunming Guiyang Wuhan Zhuzhou q
Chengdu Xi’an 842
Chengdu Kunming 1100
Chengdu Guiyang 967
Xi’an Wuhan 740
Guiyang Wuhan 1042
Guiyang Zhuzhou 607
Wuhan Zhuzhou 409
q
Chengdu
Notes
1. When entering side information, since the undirected graph is a symmetric matrix, the weight of the side must be recorded at the symmetrical position of the adjacency matrix.
2. Every time a vertex is added, all unjoined vertices must update the contents of the closedge array.
The total code is attached at the end! ! !
Steps:
1. Establish the adjacency matrix storage structure of the graph
1. Define the structure type of the array storage of the graph.
#define MaxVertexNum 25 /*The maximum number of vertices is set to 25*/
#define INF 32767 /*INF means ∞*/
typedef int EdgeType; /*Edge weight is set to integer*/
typedef struct /* adjacency matrix type definition */
{
char vexs[MaxVertexNum][10]; /*vertex table Chengdu, Wuhan...*/
EdgeType edges[MaxVertexNum][MaxVertexNum]; /*adjacency matrix, ie edge table*/
int n, e; /*number of vertices and edges*/
}MGraph;
2. Define the function to create the storage of the graph.
/*Return the serial number of the vertex city in the vertex array vexs, if there is no such city name, return -1*/
int VexID(MGraph *G,char VexName[])
{
int i;
for(i = 0; i < G -> n; i ++ )
{
if(strcmp(VexName, G->vexs[i]) == 0)
break;
}
if(i == G->n)
return -1;
else
return i;
}
void createGraph(MGraph *G)
{
int i, j, k, l;
char t[10], m[10];
/*Record vertex information*/
printf("\\
Please enter the city names one by one, enter q to exit:\\
");
for(i = 0; i < MaxVertexNum; i ++ )
{
printf("\\
city name with serial number %d:", i);
scanf("%s", G->vexs[i]);
/***Perfect the following code****/ /*If you enter q, exit the loop*/
if(strcmp(G->vexs[i],"q")==0) // compare strings
break;
G->n + + ; /*Record the number of input vertices*/
}
/* Initialize the adjacency matrix */
/***Perfect the following code****/ /*The elements on the main diagonal of the adjacency matrix are 0, and the rest are INF*/
for(i=0;i<G->n;i + + )
{
for(i=0;i<G->n;i + + )
{
if(i==j)
{
G->edges[i][j] = 0;
}
else
G->edges[i][j] = INF;
}
}
/*Record side information*/
printf("\\
Please enter side information, enter q to exit:\\
");
for(i = 0; ; i ++ )
{
printf("\\
start vertex:");
scanf("%s", t);
if(strcmp(t, "q") == 0)
break;
printf("\\
Terminating vertex: ");
scanf("%s", m);
printf("\\
edge weight:");
scanf("%d", &l);
j = VexID(G, t);
k = VexID(G, m);
/***Perfect the following code****/ ;/*Record the weight of the edge at the corresponding position of the adjacency matrix*/
if(j!=-1 & amp; & amp; k!=-1)
{
G->edges[j][k] = l; //undirected graph requires two-way mark
G->edges[k][j] = l;
//G->e + + ; //Increase the number of sides by one
}
else
{
printf("The input vertex information is wrong!");
i--;
}
}
G->e = i; /*Record the number of edges*/
}
Second, write the minimum spanning tree algorithm.
/*Define the Closedge array type as the auxiliary array type of Prim's algorithm*/
typedef struct
{
int adjvex; //target point
int lowcost; //The shortest distance to the target point
}Closedge;
/* Output Prim's algorithm for the minimum spanning tree. */
void Prim(MGraph *G,char *startCity)
{ /*G is the adjacency matrix storage of the graph, startCity is the starting city name*/
/*The algorithm will sequentially output the roads that need to lay optical cables*/
int k, j, i, minCost;
Closedge closedge[MaxVertexNum]; /*Define auxiliary array*/
int v = VexID(G, startCity);
if(v < 0)
{
printf("The input starting point city is wrong!\\
");
return;
}
closedge[v].lowcost = 0; //Initialize all the shortest distances to 0
for (j = 0; j < G->n; j ++ ) /*initialize closedge array*/
{ /***Perfect the following code****/
if(j!=v)
{
closedge[j].adjvex = v; // store the vertices in the closedge array accordingly
closedge[j].lowcost = G->edges[v][j]; //Store the edges into the closedge array accordingly
}
}
\t
for (i = 1; i < G->n; i ++ ) /* Add vertices to the set U in turn*/
{
for(j = 0; j < G->n; j ++ )/* locate the first vertex not added to U*/
if(closedge[j].lowcost != 0)
{
k = j;
break;
}
minCost = closedge[k].lowcost; /*Locate the vertex with the smallest lowcost in the V-U set*/
for (j = 0; j < G->n; j ++ )
if (closedge[j].lowcost < minCost & amp; & amp; closedge[j].lowcost != 0)
{
/***Perfect the following code****/
k = j;
minCost = closedge[j].lowcost;
}
printf("(%s,%s)\\
", G->vexs[closedge[k].adjvex], G->vexs[k]); /*Output new edges added to the tree */
/***Perfect the following code****/ /*add this vertex to the set U*/
closedge[k].lowcost = 0;
for (j = 0; j < G->n; j ++ ) /*Update the contents of the closedge array*/
{/***Perfect the following code****/
if((G->edges[k][j] < closedge[j].lowcost) & amp; & amp; (G->edges[k][j] != 0 ))
{
closedge[j].adjvex = k;
closedge[j].lowcost = G->edges[k][j];
}
}
}
}
3. Write the main function
int main(int argn,char *argv[])
{
int select, i, j;
char c[10];
MGraph *G;
char startCity[1024];
G = (MGraph *)malloc(sizeof(MGraph));
G->n = G->e = 0;
createGraph(G);
fflush(stdin);
gets(startCity);//Enter the departure city
Prim(G, startCity);
return 0;
}
Total Code
#include#include #include #define MaxVertexNum 25 /*The maximum number of vertices is set to 25*/ #define INF 32767 /*INF means ∞*/ typedef int EdgeType; /*Edge weight is set to integer*/ typedef struct /* adjacency matrix type definition */ { char vexs[MaxVertexNum][10]; /*vertex table Chengdu, Wuhan...*/ EdgeType edges[MaxVertexNum][MaxVertexNum]; /*adjacency matrix, ie edge table*/ int n, e; /*number of vertices and edges*/ }MGraph; /*Define the Closedge array type as the auxiliary array type of Prim's algorithm*/ typedef struct { int adjvex; //target point int lowcost; //The shortest distance to the target point }Closed Edge; /*Return the serial number of the vertex city in the vertex array vexs, if there is no city name, return -1*/ int VexID(MGraph *G,char VexName[]) { int i; for(i = 0; i < G -> n; i ++ ) { if(strcmp(VexName, G->vexs[i]) == 0) break; } if(i == G->n) return -1; else return i; } void createGraph(MGraph *G) { int i, j, k, l; char t[10], m[10]; /*Record vertex information*/ printf("\\ Please enter the city names one by one, enter q to exit:\\ "); for(i = 0; i < MaxVertexNum; i ++ ) { printf("\\ city name with serial number %d:", i); scanf("%s", G->vexs[i]); /***Perfect the following code****/ /*If you enter q, exit the loop*/ if(strcmp(G->vexs[i],"q")==0) // compare strings break; G->n + + ; /*Record the number of input vertices*/ } /* Initialize the adjacency matrix */ /***Perfect the following code****/ /*The elements on the main diagonal of the adjacency matrix are 0, and the rest are INF*/ for(i=0;i n;i + + ) { for(i=0;i n;i + + ) { if(i==j) { G->edges[i][j] = 0; } else G->edges[i][j] = INF; } } /*Record side information*/ printf("\\ Please enter side information, enter q to exit:\\ "); for(i = 0; ; i ++ ) { printf("\\ start vertex:"); scanf("%s", t); if(strcmp(t, "q") == 0) break; printf("\\ Terminating vertex: "); scanf("%s", m); printf("\\ edge weight:"); scanf("%d", &l); j = VexID(G, t); k = VexID(G, m); /***Perfect the following code****/ ;/*Record the weight of the edge at the corresponding position of the adjacency matrix*/ if(j!=-1 & amp; & amp; k!=-1) { G->edges[j][k] = l; //undirected graph requires two-way mark G->edges[k][j] = l; //G->e + + ; //Increase the number of sides by one } else { printf("The input vertex information is wrong!"); i--; } } G->e = i; /*Record the number of edges*/ } /* Output Prim's algorithm for the minimum spanning tree. */ void Prim(MGraph *G,char *startCity) { /*G is the adjacency matrix storage of the graph, startCity is the starting city name*/ /*The algorithm will sequentially output the roads that need to lay optical cables*/ int k, j, i, minCost; Closedge closedge[MaxVertexNum]; /*Define auxiliary array*/ int v = VexID(G, startCity); if(v < 0) { printf("The input starting point city is wrong!\\ "); return; } closedge[v].lowcost = 0; //Initialize all the shortest distances to 0 for (j = 0; j < G->n; j ++ ) /*initialize closedge array*/ { /***Perfect the following code****/ if(j!=v) { closedge[j].adjvex = v; // store the vertices in the closedge array accordingly closedge[j].lowcost = G->edges[v][j]; //Store the edges into the closedge array accordingly } } \t for (i = 1; i < G->n; i ++ ) /* Add vertices to the set U in turn*/ { for(j = 0; j < G->n; j ++ )/* locate the first vertex not added to U*/ if(closedge[j].lowcost != 0) { k = j; break; } minCost = closedge[k].lowcost; /*Locate the vertex with the smallest lowcost in the V-U set*/ for (j = 0; j < G->n; j ++ ) if (closedge[j].lowcost < minCost & amp; & amp; closedge[j].lowcost != 0) { /***Perfect the following code****/ k = j; minCost = closedge[j].lowcost; } printf("(%s,%s)\\ ", G->vexs[closedge[k].adjvex], G->vexs[k]); /*Output new edges added to the tree */ /***Perfect the following code****/ /*add this vertex to the set U*/ closedge[k].lowcost = 0; for (j = 0; j < G->n; j ++ ) /*Update the contents of the closedge array*/ {/***Perfect the following code****/ if((G->edges[k][j] < closedge[j].lowcost) & amp; & amp; (G->edges[k][j] != 0 )) { closedge[j].adjvex = k; closedge[j].lowcost = G->edges[k][j]; } } } } int main(int argn,char *argv[]) { int select, i, j; char c[10]; MGraph *G; char startCity[1024]; G = (MGraph *)malloc(sizeof(MGraph)); G->n = G->e = 0; createGraph(G); fflush(stdin); gets(startCity);//Enter the departure city Prim(G, startCity); return 0; }