#include <stdio.h>
#define MAXVEX 10
typedef char VertexType;
typedef int EdgeType;
int visited[MAXVEX];
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexs;
}MyGraph;
void creatMyGraph(MyGraph* G) {
printf("请输入顶点数：\n");
scanf_s("%d", &G->numVertexs);
for (int i = 0; i < G->numVertexs; i++) {
printf("请输入第%d个顶点", i);
while (getchar() != '\n');
scanf_s("%c", &G->vexs[i],sizeof(char));
}
for (int j = 0; j < G->numVertexs; j++) {
G->arc[j][j] = 0;
for (int k = 0; k < j; k++) {
printf("请输入节点%c和%c之间的权值", G->vexs[j], G->vexs[k]);
while (getchar() != '\n');
scanf_s("%d", &G->arc[j][k]);
G->arc[k][j] = G->arc[j][k];
}
}
}
void DFS(MyGraph G, int i) {
int j;
printf("%c", G.vexs[i]);
visited[i] = 1;
for (j = 0; j < G.numVertexs; j++) {
if (G.arc[i][j] != 0) {
if (visited[j] == 0)
DFS(G, j);
}
}
}
void DFSTraverse(MyGraph G) {
int i;
for (i = 0; i < G.numVertexs; i++) {
visited[i] = 0;
}
for (i = 0; i < G.numVertexs; i++) {
if (visited[i] == 0) {
DFS(G, i);
}
}
}
void Prim(MyGraph G) {
int lowcost[MAXVEX];
int adjvex[MAXVEX];
lowcost[0] = 0;
adjvex[0] = 0;
int i,min,k,j;
for (i = 1; i < G.numVertexs; i++) {
lowcost[i] = G.arc[0][i];
adjvex[i] = 0;
}
for (i = 1; i < G.numVertexs; i++) {
min = 65535;
k = 0;
for (j = 0; j < G.numVertexs; j++) {
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
printf("(%d,%d)", adjvex[k], k);
for (j = 0; j < G.numVertexs; j++) {
if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
lowcost[j] = G.arc[k][j];
adjvex[j] = k;
}
}
}
}
int main() {
MyGraph G;
creatMyGraph(&G);
DFSTraverse(G);
Prim(G);
}
这里在scanf_s这个函数的使用中遇到了一些问题，简单来说，%d不需要长度参数，%s和%c都需要长度参数，否则会警告。 %d不会受到回车的影响 %c会受到上一个回车的影响 %s不会受到上一个回车的影响，但是会受到上次输入溢出字符的影响（比如上一个scanf希望获得一个字符，但是输入了多个字符，那么从第二个字符之后的字符会直接赋值给这个字符串 所以在获取字符之前最好使用一下getchar()
