数据结构实验报告

实验：图的遍历

一、实验目的：

1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表

2、掌握图的构造方法

3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法

4、掌握图的深度优先遍历和广度优先原理

二、实验内容：

1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。

2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图

3、深度优先遍历第一步中构造的图G，输出得到的节点序列

4、广度优先遍历第一部中构造的图G，输出得到的节点序列

三、实验要求：

1、无向图中的相关信息要从终端以正确的方式输入；

2、具体的输入和输出格式不限；

3、算法要具有较好的健壮性，对错误操作要做适当处理；

4、程序算法作简短的文字注释。

四、程序实现及结果：

1、邻接矩阵：

#include <stdio.h>

#include <malloc.h>

#define VERTEX_MAX 30  

#define MAXSIZE 20

typedef struct

{

    int arcs[VERTEX_MAX][VERTEX_MAX];      

    int vexnum,arcnum;   

} MGraph;

void creat_MGraph1(MGraph *g)

{   int i,j,k;

    int n,m;

    printf("请输入顶点数和边数:"); 

    scanf("%d%d",&n,&m);

    g->vexnum=n;

    g->arcnum=m;

    for (i=0;i<n;i++)       

      for (j=0;j<n;j++)

         g->arcs[i][j]=0;

    while(1)       

    {

              printf("请输入一条边的两个顶点：\n");

        scanf("%d%d",&i,&j);

              if(i==-1 || j==-1)

              break;

              else if(i==j || i>=n || j>=n)

              {

                     printf("输入错误,请重新输入！\n");

              }

              else

              {

                     g->arcs[i][j]=1;

            g->arcs[j][i]=1;

              }

       

    }

}

void printMG(MGraph *g)

{

  int i,j;

  for (i=0;i<g->vexnum;i++)

  {for (j=0;j<g->vexnum;j++)

   printf(" %d",g->arcs[i][j]);

   printf("\n");

   }

  printf("\n");

}

main()

{

  int i,j;

  int fg;

  MGraph *g1;

  g1=(MGraph *)malloc(sizeof(MGraph));

  printf("1:创建无向图的邻接矩阵\n\n");

  creat_MGraph1(g1);  

  printf("\n此图的邻接矩阵为：\n");

  printMG(g1);

}

2、邻接链表:

#include<stdio.h>

#include<malloc.h>

#define MAX_SIZE 10

typedef struct node{

   int vertex;

   struct node *next;

}node,adjlist[MAX_SIZE];

adjlist g; 

int visited[MAX_SIZE+1];

int que[MAX_SIZE+1];

void creat()

{

   int n,e;

   int i;

   int start,end;

   node *p,*q,*pp,*qq;

   printf("输入无向图的顶点数和边数:");

   scanf("%d%d",&n,&e);

   for(i = 1; i <= n ; i++)

   {

          visited[i] = 0;

          g[i].vertex = i;

          g[i].next = NULL;

   }

   printf("依次输入边:\n");

   for(i = 1; i <= e ; i++)

   {

          scanf("%d%d",&start,&end);

          p=(node *)malloc(sizeof(node));

          p->vertex = end;

          p->next = NULL;

          q = &g[start];

          while(q->next)

                 q = q->next;

          q->next = p;

       p1=(node *)malloc(sizeof(node));

          p1->vertex = start;

          p1->next = NULL;

          q1 = &g[end];

       while(qq->next)

                 q1 = q1->next;

          q1->next = p1;

   }

}

void bfs(int vi)

{

       int front,rear,v;

       node *p;

       front =0;            

       rear = 1;

       visited[vi] = 1;

       que[0] = vi;     

       printf("%d ",vi);

       while(front != rear)

       {

              v = que[front];

              p = g[v].next;

              while(p)       

              {

                     if(!visited[p->vertex])

                     {

                            visited[p->vertex]= 1;

                            printf("%d ",p->vertex);

                            que[rear++] = p->vertex;

                     }

                     p = p->next;

              }

              front++;

       }

}

int main()

{

       creat();

       bfs(1);

       printf("\n");

       return 0;

}

                       

五．实验心得与体会：

(1)通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储

(2)深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。

(3)实验过程中，总体来说还算顺畅，但在编写过程中，要养成良好的编程习惯，以免出错后浪费大量的时间在查错上。