数据结构：图子系统.doc

/*
*题目：编写按键盘输入的数据建立图的邻接矩阵存储
* 编写图的深度优先遍历程序
* 编写图的广度优先遍历程序
* 设计一个选择式菜单形式如下：
* 图 子 系 统
* ***********************************
* * 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 DFSTraverse(pGraph *G);
void BFSTraverse(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)
{
case 1:
createCraph(&G);
printf("图的邻接矩阵存储成功\n\n");
break;
case 2:
DFSTraverse(&G);
break;
case 3:
BFSTraverse(&G);
break;
case 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 DFSTraverse(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 BFSTraverse(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])
{
visited[j] = 1;
inQueue(&Q, j);
}
}
}
}

void initQueue(grQueue *Q) //队列初始化
{
Q->front = Q->rear = 0;
Q->count = 0;
}

int queueEmpty(grQueue *Q) //队列判空
{
return Q->count == 0;
}

int queueFull(grQueue *Q) //队列判满
{
return Q->count == QUEUEMAX;
}

int outQueue(grQueue *Q) //出队
{
int temp;

if (queueEmpty(Q))
{
printf("队列为空。");
return -1;
}
else
{
temp = Q->queueData[Q->front]; //出队的元素
Q->count--;
Q->front = (Q->front+1)%QUEUEMAX;
return temp;
}
}

void inQueue(grQueue *Q, int i) //入队
{
if (queueFull(Q))
{
printf("队列已满。");
return;
}
else
{
Q->count++; //数目增加
Q->queueData[Q->rear] = i; //入队
Q->rear = (Q->rear+1)%QUEUEMAX; //队尾指针移动
}
}