# include
# include
# define MAX_VEX 10//最大顶点个数
# define INF 0x3f3f3f3f//无穷大
# define SIZE 5//顶点信息最大字符串个数+1
typedef char VertexType[SIZE];
typedef int EdgeType;
typedef struct{
VertexType vexs[MAX_VEX];//顶点数组
EdgeType arc[MAX_VEX][MAX_VEX];//边表
int vexNum, edgeNum;//图中顶点和边的个数
}MGraph;//无向网图邻接矩阵
struct minEdge{
int adjvex;//顶点下标
int lowcost;//最小权值
}minEdge[MAX_VEX];//创建最小权值边数组
bool visited[MAX_VEX];//访问标志数组
void CrateMGraph(MGraph * G);//创建无向网图
void PrintMGraph(MGraph G);//打印邻接矩阵
void DFSTraverse(MGraph G);//深度优先遍历
void DFS(MGraph G, int i);//深度优先递归
void BFSTraverse(MGraph G);//广度优先遍历
void Prim(MGraph G, int start);//最小生成树-Prim算法
int main(void)
{
int start;
MGraph G;
CrateMGraph(&G);
PrintMGraph(G);
DFSTraverse(G);
BFSTraverse(G);
printf("请输入最小生成树的起始顶点:");
scanf("%d", &start);
Prim(G, start);
system("pause");
return 0;
}
//创建无向网图
void CrateMGraph(MGraph * G)
{
int i, j, k, w;
printf("请输入顶点和边的个数:");
scanf("%d %d", &G->vexNum, &G->edgeNum);
for(i = 0; i < G->vexNum; i++)
{
printf("请输入第%d个顶点的信息:", i+1);
scanf("%s", &G->vexs[i]);
}
for(i = 0; i < G->vexNum; i++)
for(j = 0; j < G->vexNum; j++)
G->arc[i][j] = INF;
for(k = 0; k < G->edgeNum; k++)
{
printf("请输入第%d条边(Vi, Vj)两个顶点的下标及权值:", k+1);
scanf("%d %d %d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];
}
}
//打印邻接矩阵
void PrintMGraph(MGraph G)
{
int i, j;
for(i = 0; i < G.vexNum; i++)
printf("t%s", G.vexs[i]);
printf("n");
for(i = 0; i < G.vexNum; i++)
{
printf("%st", G.vexs[i]);
for(j = 0; j < G.vexNum; j++)
{
if(G.arc[i][j] == INF)
printf("∞t");
else
printf("%dt", G.arc[i][j]);
}
printf("n");
}
}
//深度优先遍历
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i < G.vexNum; i++)
visited[i] = false;
printf("nDFS:t");
for(i = 0; i < G.vexNum; i++)
{
if(!visited[i])
DFS(G, i);
}
printf("n");
}
//深度优先递归
void DFS(MGraph G, int i)
{
int j;
visited[i] = true;
printf("%st", G.vexs[i]);
for(j = 0; j < G.vexNum; j++)
{
if(!visited[j] && G.arc[i][j] != INF)
DFS(G, j);
}
}
//广度优先遍历
void BFSTraverse(MGraph G)
{
int i , j;
for(i = 0; i < G.vexNum; i++)
visited[i] = false;
int Queue[MAX_VEX];//队列存放顶点对应下标
int front = 0, rear = 0;//队首队尾下标
printf("BFS:t");
for(i = 0; i < G.vexNum; i++)
{
if(!visited[i])
{
visited[i] = true;
printf("%st", G.vexs[i]);
rear = (rear + 1) % MAX_VEX;
Queue[rear] = i; //将此顶点下标入队
while(rear != front)//当队列不为空
{
front = (front + 1) % MAX_VEX;
i = Queue[front];//队首元素出队赋值给i,便于寻找一下个邻接点
for(j = 0; j < G.vexNum; j++)
{
if(!visited[j] && G.arc[i][j] != INF)//找到未被访问的顶点并且属于当前顶点i的邻接点
{
visited[j] = true;
printf("%st", G.vexs[j]);
rear = (rear + 1) % MAX_VEX;
Queue[rear] = j;//将找到顶点循环依次序入队
}
}
}
}
}
printf("nn");
}
//最小生成树-Prim算法
void Prim(MGraph G, int start)
{
int i;
for(i = 0; i < G.vexNum; i++)
{
minEdge[i].adjvex = start;
minEdge[i].lowcost = G.arc[start][i];
}
minEdge[start].lowcost = 0;//lowcost数组值为0表示该下标对应顶点已经并入集合
for(i = 0; i < G.vexNum - 1; i++)//n个顶点最小生成树共n-1条边
{
int j = 0;
int k = 0;
int min = INF;
//循环找寻最小权值
while(j < G.vexNum)
{
if(minEdge[j].lowcost != 0 && minEdge[j].lowcost < min)
{
min = minEdge[j].lowcost;
k = j;
}
j++;
}
printf("(%d, %d)%d-->", minEdge[k].adjvex, k, minEdge[k].lowcost);
minEdge[k].lowcost = 0;//将lowcost数组值置0表示该下标对应顶点已经并入集合
//更新lowcost数组值,若新点位k的邻接点有最小权值边则替换
for(j = 0; j < G.vexNum; j++)
{
if(minEdge[j].lowcost != 0 && G.arc[k][j] < minEdge[j].lowcost)
{
minEdge[j].lowcost = G.arc[k][j];
minEdge[j].adjvex = k;
}
}
}
}
