#include<stdio.h>
typedef int VertexType;
typedef int EdgeType;
#define MaxVex 100
#define TRUE 1
#define INFINITY 0
#define FALSE 0
typedef int Bool;
Bool visited[MaxVex];
typedef struct
{
VertexType Vexs[MaxVex];
EdgeType Edge[MaxVex][MaxVex];
int numV;
int numE;
}MGraph;
//创建无向图的邻接矩阵
void CreateMGraph(MGraph *G)
{
int vi, vj, e;
printf("请输入图的顶点数和边数(顶点数 边数):");
scanf("%d%d", &G->numV, &G->numE);
for(int i = 0; i < G->numV; i++)
{
for (int j = 0; j < G->numV; j++)
{
if (i == j)
{
G->Edge[i][j] = 0;//将顶点与自身的权值初始化为0
}
else
{
G->Edge[i][j] = INFINITY;//将顶点与其他顶点的权值初始化为Infinity
}
}
}
for ( i = 0; i < G->numV; i++)
{
printf("请输入第%d个顶点的值:", i + 1);
scanf("%d", &G->Vexs[i]);
}
printf("\n");
for (int k = 0; k < G->numE; ++k)
{
int i, j;
printf("请输入边的信息(顶点 顶点 权值):");
scanf("%d%d%d", &vi, &vj, &e);
for (i = 0; i < G->numV; i++)
{
if (G->Vexs[i] == vi)
{
break;//找出顶点的在数组中的位置
}
}
for (j = 0; j < G->numV; j++)
{
if (G->Vexs[j] == vj)
{
break;
}
}
G->Edge[i][j] = e;
G->Edge[j][i] = e;
}
}
//输出无向图的邻接矩阵
void ShowpGraph(MGraph G)
{
printf("\n邻接矩阵为:\n");
printf("\t");
for (int i = 0; i < G.numV; ++i)
{
printf("%6d", G.Vexs[i]);
}
printf("\n");
for ( i = 0; i < G.numV; ++i)
{
printf("\n%8d", G.Vexs[i]);
for (int j = 0; j < G.numV; ++j)
{
if (G.Edge[i][j] == INFINITY)
{
printf("%6s", "∞");
}
else
{
printf("%6d", G.Edge[i][j]);
}
}
printf("\n");
}
}
//图的深度优先遍历
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
printf("%c ", G.Vexs[i]);
for (j=0; j < G.numE; j++)
{
if (G.Edge[i][j]!=INFINITY && !visited[j])
DFS(G, j);
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i=0;i<G.numE;i++)
{
visited[i] = FALSE;
}
for (i=0; i<G.numE; ++i)
{
if (!visited[i])
DFS(G, i);
}
}
//图的广度优先
void BFSTraverse(MGraph *G)
{
int i, j;
for (i=0; i<G->numE; ++i)
visited[i] = FALSE;
for (i=0; i<G->numE; ++i)
{
if (!visited[i])
{
visited[i] = TRUE;
printf("%c ", G->Vexs[i]);
while (!G)
{
for (j=0; j<G->numE; ++j)
{
if (!visited[j] && G->Edge[i][j]!=INFINITY)
{
visited[j] = TRUE;
printf("%c ", G->Vexs[j]);
}
}
}
}
}
}
int main()
{
MGraph G;
CreateMGraph(&G);
ShowpGraph(G);
printf("\n图的深度优先遍历为: ");
DFSTraverse(G);
printf("\n图的广度优先遍历为: ");
BFSTraverse(&G);
}
你有很多变量未定义就使用了:
运行后,
在命令行输入
5空格8回车
改了好几个地方, 运行结果:
#include<stdio.h>
typedef int VertexType;
typedef int EdgeType;
#define MaxVex 100
#define TRUE 1
#define INFINITY 0
#define FALSE 0
typedef int Bool;
Bool visited[MaxVex];
typedef struct
{
VertexType Vexs[MaxVex];
EdgeType Edge[MaxVex][MaxVex];
int numV;
int numE;
}MGraph;
//创建无向图的邻接矩阵
void CreateMGraph(MGraph *G)
{
int vi, vj, e;
printf("请输入图的顶点数和边数(顶点数 边数):");
scanf("%d%d", &G->numV, &G->numE);
for(int i = 0; i < G->numV; i++)
{
for (int j = 0; j < G->numV; j++)
{
if (i == j)
{
G->Edge[i][j] = 0;//?????????????0
}
else
{
G->Edge[i][j] = INFINITY;//???????????????Infinity
}
}
}
for ( int i = 0; i < G->numV; i++)
{
printf("请输入第%d个顶点的值:", i + 1);
scanf("%d", &G->Vexs[i]);
}
printf("\n");
for (int k = 0; k < G->numE; ++k)
{
int i, j;
printf("请输入边的信息(顶点 顶点 权值):");
scanf("%d%d%d", &vi, &vj, &e);
for (i = 0; i < G->numV; i++)
{
if (G->Vexs[i] == vi)
{
break;//????????????
}
}
for (j = 0; j < G->numV; j++)
{
if (G->Vexs[j] == vj)
{
break;
}
}
G->Edge[i][j] = e;
G->Edge[j][i] = e;
}
}
//输出无向图的邻接矩阵
void ShowpGraph(MGraph G)
{
printf("\n邻接矩阵为:\n");
printf("\t");
for (int i = 0; i < G.numV; ++i)
{
printf("%6d", G.Vexs[i]);
}
printf("\n");
for ( int i = 0; i < G.numV; ++i)
{
printf("\n%8d", G.Vexs[i]);
for (int j = 0; j < G.numV; ++j)
{
if (G.Edge[i][j] == INFINITY)
{
printf("%6s", "8");
}
else
{
printf("%6d", G.Edge[i][j]);
}
}
printf("\n");
}
}
//图的深度优先遍历
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
printf("%c ", G.Vexs[i]);
for (j=0; j < G.numE; j++)
{
if (G.Edge[i][j]!=INFINITY && !visited[j])
DFS(G, j);
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i=0;i<G.numE;i++)
{
visited[i] = FALSE;
}
for (i=0; i<G.numE; ++i)
{
if (!visited[i])
DFS(G, i);
}
}
//图的广度优先
void BFSTraverse(MGraph *G)
{
int i, j;
for (i=0; i< G->numE; ++i)
visited[i] = FALSE;
for (i=0; i< G->numE; ++i)
{
if (!visited[i])
{
visited[i] = TRUE;
printf("%c ", G->Vexs[i]);
while (!G)
{
for (j=0; j< G->numE; ++j)
{
if (!visited[j] && G->Edge[i][j]!=INFINITY)
{
visited[j] = TRUE;
printf("%c ", G->Vexs[j]);
}
}
}
}
}
}
int main()
{
MGraph G;
CreateMGraph(&G);
ShowpGraph(G);
printf("\n图的深度优先遍历为:");
DFSTraverse(G);
printf("\n图的广度优先遍历为: ");
BFSTraverse(&G);
}