/*
*题目：编写按键盘输入的数据建立图的邻接矩阵存储
* 编写图的深度优先遍历程序
* 编写图的广度优先遍历程序
* 设计一个选择式菜单形式如下：
* 图 子 系 统
* ***********************************
* * 1------更新邻接矩阵 *
* * 2------深度优先遍历 *
* * 3------广度优先遍历 *
* * 0------ 返 回 *
* ***********************************
* 请选择菜单号（0--3）：
*/
#include <stdio.h>蒙太古
#include <stdlib.h>
#define GRAPHMAX 30
#define QUEUEMAX 30
typedef struct //图的邻接表的结构体
{
char value[GRAPHMAX]; //记录图中的点值
int data[GRAPHMAX][GRAPHMAX]; //记录图中的边的关系
int n, e; //记录图中的点的个数及边的个数
}pGraph;
typedef struct //队列结构体
{
int queueData[QUEUEMAX];
int front, rear, count; //队头，队尾，数目
}grQueue;
void createCraph(pGraph *G);
void DFSTraver(pGraph *G);
void BFSTraver(pGraph *G);
void DFS(pGraph *G, int i);
妖狐御魂void BFS(pGraph *G, int i);
void initQueue(grQueue *Q);
int queueEmpty(grQueue *Q);
int queueFull(grQueue *Q);
雷伊日记int outQueue(grQueue *Q);
void inQueue(grQueue *Q, int i);
int visited[GRAPHMAX]; //用于标志性的数组（全局变量）
void main()
{
pGraph G;
int choice, i, j, k = 1;
printf("建立一个有向图的邻接矩阵表示\n");
createCraph(&G);
printf("已建立一个图的邻接矩阵存储\n\n");
for (i = 0; i<G.n; i++)
{
for(j = 0; j<G.n; j++)
{
printf("%5d", G.data[i][j]);
}
printf("\n");
}
while (k)
{
printf("\n 图 子 系 统\n");
printf("***********************************\n");
printf("* 1------更新邻接矩阵 *\n");逐梦人
printf("* 2------深度优先遍历 *\n");
printf("* 3------广度优先遍历 *\n");
printf("* 0------ 返 回 *\n");
printf("***********************************\n");
printf("请选择菜单号（0--3）：");
fflush(stdin);
scanf("%d", &choice);
switch(choice)
{
ca 1:
createCraph(&G);
printf("图的邻接矩阵存储成功\n\n");
break;
ca 2:
DFSTraver(&G);
break;
ca 3:
BFSTraver(&G);
break;
ca 0:
k = 0;
break;
default:
printf("输入错误，请重新输入。");
getchar();
k = 1;
break;
}
}
}
void createCraph(pGraph *G) //建立邻接表
{
int i, j, k;月明星稀的意思
教研活动主持稿 char ch1, ch2;
printf("请输入定点数，边数（格式如3,3）:");
scanf("%d,%d",&(G->n), &(G->e));
for(i = 0; i < G->n; i++) //输入顶点值
{乘坐电梯的礼仪
getchar();
printf("请输入第%d顶点的值：", i+1);
scanf("%c", &(G->value[i]));
}
//初始化邻接表
for (i = 0; i<G->n; i++)
{
for (j = 0; j<G->n; j++)
{
G->data[i][j] = 0;
}
}
for (k = 0; k < G->e; k++)
{
getchar();
printf("请输入第%d条边的顶点值（格式4,5）：", k+1);
scanf("%c,%c", &ch1, &ch2);
//构建邻接表
for (i = 0; i<G->n; i++)
{
if (ch1 == G->value[i])
{
for (j = 0; j<G->n; j++)
{
if (ch2 == G->value[j])
{
G->data[i][j] = 1;
}
}
}
}
}
}
//深度遍历
void DFSTraver(pGraph *G)
{
int i;
形容友情深厚的成语 for (i = 0; i < G->n; i++)
{
visited[i] = 0;
}
for (i = 0; i < G->n;i++)
{
if (!visited[i])
{
DFS(G, i);
}
}
}
//广度遍历
void BFSTraver(pGraph *G)
{
int i;
for (i = 0; i < G->n; i++)
{
visited[i] = 0;
}
for (i = 0; i < G->n;i++)
{
if (!visited[i])
{
BFS(G, i);
}
}
}
void DFS(pGraph *G, int i)
{
int j;
printf("深度优先遍历序列：%c\n", G->value[i]);
visited[i] = 1;
for (j = 0; j<G->n; j++)
{
if (G->data[i][j] == 1&&!visited[j])
{
DFS(G, j);
}
}
}
void BFS(pGraph *G, int i)
{
int k, j;
grQueue Q;
initQueue(&Q); //初始化
visited[i] = 1;
inQueue(&Q, i);
while (!queueEmpty(&Q))
{
k = outQueue(&Q);
printf("广度优先遍历序列：%c\n", G->value[k]);
for (j = 0; j<G->n; j++)
{
if (G->data[k][j] == 1&&!visited[j])
{
