实验5 图的操作

实验5 图的操作

一、实验目的

1. 熟悉图的存储结构；

2．熟悉图的创建操作；

3．熟悉图的遍历操作。

三、实验要求

1．．每个同学必须独立完成；

2．程序中的开头部分必须对本程序的总体功能进行注释；程序中每个函数段必须要有注释说明该函数的功能或作用；

3．上机进行调试和修改并填写实验报告；

4．实验报告中的源程序必须调试通过。

5．在体会中描述如下内容：

（1）对算法与程序的区别上的体会。

（2）本次实验过程的体会，是否自己独立完成？最大的困难是什么？自己准备如何解决这个困难？

6．提交实验报告（报告中包含关键源代码）

实验内容

1、用邻接表结构实现如图所示无向图的存储；

2、在第1步骤基础上实现该无向图的深度优先遍历；输出遍历序列；

3、在第1步骤基础上实现该无向图的广度优先遍历；输出遍历序列；

 

 

 

参考代码：

 

#include "stdio.h"
#include "conio.h"
#define MaxVertexNum 100
#define MAXSIZE 100
typedef struct
{
    int data[MAXSIZE];
    int front;
    int rear;
}SeqQueue;
typedef char VertexType;
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxVertexNum];
typedef char elemtype;
/*边结点*/
typedef struct node
{
    int adjvex;/*邻接点域*/
    struct node *nextedge;/*链域*/
}EdgeNode;
/*顶点表结点*/
typedef struct vnode
{
    VertexType vertex; /*顶点域*/
    EdgeNode *firstedge; /*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*/
/*
    对于简单的应用，无须定义此类型，可直接使用AdjList类型
*/
typedef struct
{
    AdjList adjlist;/*邻接表*/
    int n,e;        /*当前结点数和边数*/
    int kind;       /*图的种类标志*/
}ALGraph;
/*建立无向图的邻接表*/
void CreateALGraPh(ALGraph *G1)
{
    int i,j,k;
    EdgeNode *s;
    /*读入顶点数和边数*/
    printf("please input vertices: ");
    scanf("%d",&G1->n);getchar();
    printf("please input Vertex edge number: ");
    scanf("%d",&G1->e);getchar();

    /*建立顶点表*/
    for(i=0;i<G1->n;i++)
    {
        printf("please input the %dth Vertex\n",i+1);
        scanf("%c",&G1->adjlist[i].vertex);getchar(); /*读入顶点信息*/
        G1->adjlist[i].firstedge=NULL;    /*边表置为空表*/
    }
    printf("Please enter no to chart the relationship between vertices.the style is vi,vj\n\n ");
    /*建立边表*/
    for(k=0;k<G1->e;k++)
    {
        printf("the %dth is: ",k+1);
        scanf("%d,%d",&i,&j);            /*读入边(vi,vj)的顶点对序号*/
        s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/
        s->adjvex=j;/*邻接点序号为j*/
        s->nextedge=G1->adjlist[i].firstedge;
        G1->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/

        s=(EdgeNode *)malloc(sizeof(EdgeNode));
        s->adjvex=i;/*邻接点序号为i*/
        s->nextedge=G1->adjlist[j].firstedge;
        G1->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/
    }
}
/*邻接表表示的深度优先遍历*/
void DFS(ALGraph *G1,int i)
{

    EdgeNode *p;
    printf("%c ",G1->adjlist[i].vertex);/*访问顶点vi*/
    visited[i]=TRUE;/*标记vi已访问*/
    p=G1->adjlist[i].firstedge;   /*取vi边表的头指针*/
    while(p)
    {
        if(!visited[p->adjvex]) /*若vi尚未被访问，则以vj为出发点向纵深搜索*/
        {
           DFS(G1,p->adjvex);
        }
        p=p->nextedge;/*找vi的下一邻接点*/
    }

}
/*邻接表表示的广度优先遍历*/
void BFS(ALGraph *G,int k)
{
    int i;
    SeqQueue *Q;
    EdgeNode *p;
    /*初始队列*/
    Q=(SeqQueue *)malloc(sizeof(SeqQueue));
    Q->front=Q->rear=0;

    printf("%c ",G->adjlist[k].vertex);
    visited[k]=TRUE;

    /*入队*/
    Q->data[Q->rear]=k;
    Q->rear=(Q->rear+1)%MAXSIZE;
    Q->rear++;

    while(Q->rear)
    {
        i=Q->data[Q->front];
        Q->front=(Q->front+1)%MAXSIZE;
        Q->rear--;

        p=G->adjlist[i].firstedge;
        while(p)
        {
            if(!visited[p->adjvex])
            {
                printf("%c ",G->adjlist[p->adjvex].vertex);
                visited[p->adjvex]=TRUE;
                Q->data[Q->rear]=p->adjvex;
                Q->rear=(Q->rear+1)%MAXSIZE;
                Q->rear++;

            }
            p=p->nextedge;
        }
    }
}
executeBFS(ALGraph *G)
{
    int i;
    for(i=0;i<G->n;i++)/*将图G的所有顶点设置未访问过标记 */
        visited[i]=FALSE;
    for(i=0;i<G->n;i++)/*对图G调用bfs函数进行广度优先搜索*/
        if(!visited[i])
            BFS(G,i);
}
main()
{
    ALGraph *G1;
    int i;
    CreateALGraPh(&G1);
    printf("DFS\n");
    DFS(&G1,0);
    printf("\nBFS\n");
    executeBFS(&G1);
    getch();
}