实验四

实验四  图的基本操作

 

 

一、题目

编制一个演示用邻接矩阵和邻接表存储结构实现的图的深度优先遍历和广度优先遍历算法的程序。另附扩展实现（1:有向图2:无向图3:有向网4:无向网） 4种类型的图的（1.邻接矩阵，2.邻接表，3.深度优先搜索，4.广度优先搜索，5.最小生成树，6.拓扑排序，7.关键路径，8.从某个源点到其余各顶点的最短路径，9.每一对顶点之间的最短路径）图的9种实现程序。（附源代码于尾页//程序1 //程序2 /*扩展实现源代码*/）

二、需求分析      

本程序在Windows环境下用用Visual C++编写，完成程序1和程序2的实现：

程序1

void CreatMatrix(adjmatrix GA)       // 建立图的邻接矩阵

void DfsMatrix(adjmatrix GA,int v)  // 从初始点v出发深度优先遍历邻接矩阵GA表示的图

void BfsMatrix(adjmatrix GA,int v)  // 从初始点v出发广度优先遍历邻接矩阵GA表示的图

程序2

void CreatAdjlist(AdjList GL) //建立图的邻接表

void DfsAdjlist(AdjList GL,int v) //从初始点v出发深度优先遍历邻接表GL表示的图

void BfsAdjlist(AdjList GL,int v) //从初始点v出发广度优先遍历邻接表GL表示的图

 

三、概要设计

程序1

/* 定义邻接矩阵类型 */

typedef int adjmatrix[n+1][n+1];

程序2

/* 邻接表的结点类型 */

typedef struct arc

{

int adjvex;

    struct arc *next;}ArcNode;

typedef struct VexNode

{

int vertex;

    ArcNode *firstarc;

}VerNode;

typedef VerNode AdjList[MAXNODE];

三、详细设计

分别对程序1和程序2进行编码设计如下:

//程序1

#include <stdio.h>

#define n 5

#define MAXSIZE 10     //广度优先遍历时所使用的队列的最大容量

#define MaxNum 10000   //定义一个最大数

// 定义邻接矩阵类型

typedef int  adjmatrix[n+1][n+1];  // 0号单元没用

int visited[n+1];                  // 0号单元没用

int arcnum;                        //边的个数

//建立图的邻接矩阵

//程序2

#include <stdio.h>

#include <malloc.h>

#define MAXNODE 10

#define NULL 0

typedef struct arc

{

     int adjvex;

    struct arc *next;

}ArcNode;

typedef struct VexNode

{

     int vertex;

 ArcNode *firstarc;

}VerNode;

typedef VerNode AdjList[MAXNODE];

int visited[MAXNODE];

int vexnum,arcnum;

// 建立图的邻接表

2)图的基本操作如下：

//程序1

//建立图的邻接矩阵

void CreatMatrix(adjmatrix GA)

//从初始点v出发深度优先搜索邻接矩阵GA表示的图

void DfsMatrix(adjmatrix GA,int v)

//从初始点v出发广度优先搜索邻接矩阵GA表示的图

void BfsMatrix(adjmatrix GA,int v)

//程序2

// 建立图的邻接表

void creatgraph(AdjList GL)

　　　　void dfs(AdjList G,int v)

// 从初始点v出发深度优先遍历邻接表GL表示的图

void DfsAdjlist(AdjList GL,int v)

//从初始点v出发广度优先遍历邻接表GL表示的图

void BfsAdjlist(AdjList GL,int v)

四、测试结果

1.程序1：

图中有5个顶点

请输入边的个数(限制在1到10的范围内):6

请输入图的所有边(一条边的两个端点中间用,分隔): ,

1,2 2,3 2,5 3,4 4,5 5,1

请输入深度优先遍历的开始结点:1

深度优先遍历序列是:1,2,3,4,5,

请输入广度优先遍历的开始结点:1

广度优先遍历序列是:1 2 5 3 4 Press any key to continue

2.程序2：

请输入顶点个数和边的个数:5 6

请输入顶点(顶点用整型数代表):

1 2 3 4 5

请输入图的所有边(一条边的两个端点中间用,分隔): ,

1,2 2,3 2,5 3,4 4,5 5,1

请输入深度优先遍历的开始结点:1

深度优先遍历序列是:1,5,4,3,2,

请输入广度优先遍历的开始结点:1

广度优先遍历序列是:1 5 2 4 3 Press any key to continue

3.扩展程序：

请输入图的类型(1:有向图 2:无向图 3:有向网 4:无向网):2

请输入顶点数,边数(逗号隔开):3,3

第1个顶点的信息:

11

第2个顶点的信息:

22

第3个顶点的信息:

33

第1条边的两个顶点的编号:(逗号隔开)1,2

第2条边的两个顶点的编号:(逗号隔开)2,3

第3条边的两个顶点的编号:(逗号隔开)3,1

 

请选择图的实现:

1__邻接矩阵

2__邻接表

3__深度优先搜索

4__广度优先搜索

5__最小生成树

6__拓扑排序

7__关键路径

8__从某个源点到其余各顶点的最短路径

9__每一对顶点之间的最短路径

10__退出......

1

邻接矩阵:

vertex     1   2   3

   1       0   1   1

   2       1   0   1

   3       1   1   0

 

请选择图的实现:

1__邻接矩阵

2__邻接表

3__深度优先搜索

4__广度优先搜索

5__最小生成树

6__拓扑排序

7__关键路径

8__从某个源点到其余各顶点的最短路径

9__每一对顶点之间的最短路径

10__退出......

3

请输入出发点编号:1

邻接表为:

[1,1]=>[3,0]-->[2,0]-->^

[2,2]=>[3,0]-->[1,0]-->^

[3,3]=>[1,0]-->[2,0]-->^

 

从第1点出发深度优先搜索遍历序列:   1->

请选择图的实现:

1__邻接矩阵

2__邻接表

3__深度优先搜索

4__广度优先搜索

5__最小生成树

6__拓扑排序

7__关键路径

8__从某个源点到其余各顶点的最短路径

9__每一对顶点之间的最短路径

10__退出......

4

请输入出发点编号:1

邻接表为:

[1,1]=>[3,0]-->[2,0]-->^

[2,2]=>[3,0]-->[1,0]-->^

[3,3]=>[1,0]-->[2,0]-->^

 

从第1点出发广度优先搜索遍历序列:

五、调试分析

调试中发现5个顶点6条边的无向图中

由于对称使得深度优先遍历和广度优先遍历都产生了

两种：即2和5对称的两种结果

对于算法来说调试有时候可以检验算法

使算法的精神得以驱动程序这个躯体

附加程序的调试最不简单原因是程序比较庞大

六、 源程序（带注释）

//程序1

#include <stdio.h>

#define n 5

#define MAXSIZE 10     //广度优先遍历时所使用的队列的最大容量

#define MaxNum 10000   //定义一个最大数

// 定义邻接矩阵类型

typedef int  adjmatrix[n+1][n+1];  // 0号单元没用

int visited[n+1];                  // 0号单元没用

int arcnum;                        //边的个数

//建立图的邻接矩阵

void CreatMatrix(adjmatrix GA)

{

int i,j,k;

  printf("图中有%d个顶点/n",n);

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

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

    if(i==j) GA[i][j]=0;     //对角线的值置为0

    else GA[i][j]=MaxNum;    //其它位置的值初始化为一个最大数

 printf("请输入边的个数(限制在1到10的范围内):");

 scanf("%d",&arcnum);

 printf("请输入图的所有边(一条边的两个端点中间用,分隔): , /n");

 for(k=1;k<=arcnum;k++)

     {scanf("%d,%d",&i,&j);     //读入边的信息

      GA[i][j]=1;             

      GA[j][i]=1;

     }

}

//从初始点v出发深度优先搜索邻接矩阵GA表示的图

void DfsMatrix(adjmatrix GA,int v)

{

     int j;

  visited[v]=1;  printf("%d,",v);

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

   if(v!=j&&GA[v][j]!=MaxNum&&!visited[j])

        DfsMatrix(GA,j);

}

//从初始点v出发广度优先搜索邻接矩阵GA表示的图

void BfsMatrix(adjmatrix GA,int v)

{

 int i,k,j,Q[MAXSIZE],front=0,rear=0;

 for(i=1;i<=n;i++) visited[i]=0;

 visited[v]=1;

 printf("%d ",v);

 rear=(rear+1)%MAXSIZE;                 //开始遍历的顶点入队列

 Q[rear]=v;

 while(front!=rear)

 {

  front=(front+1)%MAXSIZE;           //队头元素出队

  k=Q[front];

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

    if((!visited[j])&&(GA[k][j]==1))//访问与队头元素邻接的还未被访问的结点

     {

         visited[j]=1;          

        printf("%d ",j);

        rear=(rear+1)%MAXSIZE;

        Q[rear]=j;

    }//endif

 }//endwhile

}

void main()

{

  adjmatrix GA;

  int v;

  CreatMatrix(GA);

  printf("请输入深度优先遍历的开始结点:");

  scanf("%d",&v);

  printf("深度优先遍历序列是:");

  DfsMatrix(GA,v);

  printf("/n");

  printf("请输入广度优先遍历的开始结点:");

  scanf("%d",&v);

  printf("广度优先遍历序列是:");

  BfsMatrix(GA,v);

}

//程序2

#include <stdio.h>

#include <malloc.h>

#define MAXNODE 10

#define NULL 0

typedef struct arc

{

     int adjvex;

    struct arc *next;

}ArcNode;

typedef struct VexNode

{

     int vertex;

 ArcNode *firstarc;

}VerNode;

typedef VerNode AdjList[MAXNODE];

int visited[MAXNODE];

int vexnum,arcnum;

// 建立图的邻接表

void creatgraph(AdjList GL)

{

     int i,j,k;

    ArcNode *p;

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

    scanf("%d%d",&vexnum,&arcnum);

    printf("请输入顶点(顶点用整型数代表):/n");

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

     {

        scanf("%d",&GL[i].vertex);

       GL[i].firstarc=NULL;

     }

 printf("请输入图的所有边(一条边的两个端点中间用,分隔): , /n");

 for(k=1;k<=arcnum;k++)

     {

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

       if(i&&j)

        {

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

           p->adjvex=j;p->next=GL[i].firstarc;GL[i].firstarc=p;

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

           p->adjvex=i;p->next=GL[j].firstarc; GL[j].firstarc=p;

        }

     }

 }

void dfs(AdjList G,int v)

{

     ArcNode *q;

  if(!visited[v])

       printf("%d,",G[v].vertex);

  visited[v]=1;

  q=G[v].firstarc;

  while(q!=NULL)

  {

       if(!visited[q->adjvex])

           dfs(G,q->adjvex);

      q=q->next;

  }

}

// 从初始点v出发深度优先遍历邻接表GL表示的图

void DfsAdjlist(AdjList GL,int v)

{

      int i;

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

      visited[i]=0;

 if(!visited[v])

      dfs(GL,v);

}

//从初始点v出发广度优先遍历邻接表GL表示的图

void BfsAdjlist(AdjList GL,int v)

{

     int k,i,Q[MAXNODE],front=0,rear=0;

    ArcNode *p;

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

      visited[i]=0;

 visited[v]=1;

 printf("%d ",GL[v].vertex);

 rear=(rear+1)%MAXNODE;

 Q[rear]=v;

 while(front!=rear)

 {

      front=(front+1)%MAXNODE;

     k=Q[front];

     p=GL[k].firstarc;

  while(p!=NULL)

    {

       if(!visited[p->adjvex])

       {

           visited[p->adjvex]=1;

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

          rear=(rear+1)%MAXNODE;

          Q[rear]=p->adjvex;

       }

      p=p->next;

    }

  }

}

void main()

{

  AdjList GL;

  int v;

  creatgraph(GL);

  printf("请输入深度优先遍历的开始结点:");

  scanf("%d",&v);

  printf("深度优先遍历序列是:");

  DfsAdjlist(GL,v);

  printf("/n");

  printf("请输入广度优先遍历的开始结点:");

  scanf("%d",&v);

  printf("广度优先遍历序列是:");

  BfsAdjlist(GL,v);

}