实验六  图的综合应用 邻接矩阵

一、实验目的

1.掌握图的基本操作—遍历；

2.掌握图的应用。

二、实验内容

对给定的输入内容，完成实验任务。

输入顶点集：

​​​​​​​1 2 3 4 5 6 7 8

输入边的集合：

1  2
1  3
2  4
2  5
4  8
5  8
3  6
3  7
6  7

（1）创建一个图（可用邻接矩阵或邻接表的方式进行存储）；

（2）输入选项：0或1，0为DFS，1为BFS；

（3）分别输出DFS和BFS两种遍历序列。

---

头文件及宏定义：

#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef char ElemType;
typedef int Bool;
typedef struct
{
    ElemType data[MAXSIZE];//顶点表
    int adjmatrix[MAXSIZE][MAXSIZE];//邻接矩阵
    int Vertexes,Edges;//顶点数与边数
}Graph;
typedef struct
{
    int *base;
    int front;
    int rear;
}cycleQueue;

Bool visited[MAXSIZE];//访问标志数组（全局变量） 

子函数声明：

void CreateGraph(Graph *);//创建邻接矩阵 
void PrintGraph(Graph);//输出邻接矩阵
void DFSTravels(Graph);//深度优先遍历 （递归） 
void DFS(Graph,int);//深度优先遍历过程
void BFSTravels(Graph);//广度优先遍历（队列循环操作） 
void InitQueue(cycleQueue *);//初始化队列 
void InsertQueue(cycleQueue *,int);//行列号入队 
void DeleteQueue(cycleQueue *,int *);//行列号出队 
Status QueueEmpty(cycleQueue);//队列判空 空返回TRUE 非空返回FALSE 

子函数主体：

void CreateGraph(Graph *G)
{
    int i,j,k;
    printf("请输入顶点数与边数：n");
    scanf("%d %d",&G->Vertexes,&G->Edges);
    printf("请输入顶点：n");
    for(i=0;iVertexes;i++)
    {
        getchar();
        scanf("%c",&G->data[i]);
    }

    for(i=0;iVertexes;i++)//初始化邻接矩阵
    {
        for (j=0;j Vertexes;j++)
        {
            G->adjmatrix[i][j]=0;
        }
    }

    printf("请输入边Vi Vj：n");
    for(k=0;kEdges;k++)
    {
        scanf("%d %d",&i,&j);
        G->adjmatrix[i-1][j-1]=1;
    }
}

void DFSTravels(Graph G)
{
	printf("n深度优先遍历结果：n");
    int i;
    for (i=0;ibase=(int *)malloc(MAXSIZE*sizeof(int));
    if(!q->base)
    {
        printf("内存分配失败！n");
        exit(0);
    }
    q->front=q->rear=0;
}

void InsertQueue(cycleQueue *q,int e)
{
    //队列不可能满！
    q->base[q->rear]=e;
    q->rear=(q->rear+1)%MAXSIZE;
}

void DeleteQueue(cycleQueue *q,int *e)
{
    *e=q->base[q->front];
    q->front=(q->front+1)%MAXSIZE;
}

Status QueueEmpty(cycleQueue q)
{
    if(q.front==q.rear)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

void BFSTravels(Graph G)
{
	printf("n广度优先遍历结果：n");
    int i,j;
    cycleQueue Q;
    InitQueue(&Q);

    for(i=0;i 
主函数：
 
int main(void)
{
    int choice;
    Graph *G=(Graph *) malloc(sizeof (Graph));
    printf("|———————★———————|n");
    printf("|      ☆☆☆欢迎使用☆☆☆    |n");
    printf("|  该程序以邻接矩阵创建有向图  |n");
    printf("|     现在来创建一张有向图     |n");
    printf("|  Powered by CaptainUniverse_ |n");
    printf("|———————————————|n");
    CreateGraph(G);
    PrintGraph(*G);

    while (1)
    {
    	putchar('n');
        printf("|———————★———————|n");
        printf("|      ☆☆☆继续操作☆☆☆    |n");
        printf("|------0.深度优先遍历该图------|n");
        printf("|------1.广度优先遍历该图------|n");
        printf("|------2.退出------------------|n");
        printf("|            请选择            |n");
        printf("|  Powered by CaptainUniverse_ |n");
        printf("|———————————————|n");
        scanf("%d",&choice);
        if(!choice)
        {
            DFSTravels(*G);
        }
        else if(choice==1)
        {
            BFSTravels(*G);
        }
        else if(choice==2) 
        {
        	printf("n听我说谢谢你，因为有你，温暖了四季！n");
            printf("n感谢您的使用！n");
            return 0;
        }
    }
}
 

写在最后：
 
等我有时间再写以邻接表建立图。