實驗四

實驗四  圖的基本操作

院 、系

 海師計教系

 班級

計本二班

學   号

 200624101101

 姓名

 楊振平

完成日期

 2007-11-19  

源程式名

1.      cpp和222.cpp和圖.cpp

一、題目

編制一個示範用鄰接矩陣和鄰接表存儲結構實作的圖的深度優先周遊和廣度優先周遊算法的程式。另附擴充實作（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表示的圖

三、概要設計

/* 定義鄰接矩陣類型 */

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

/* 鄰接表的結點類型 */

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 <malloc.h>

#define MAXNODE 10

#define NULL 0

     int adjvex;

    struct arc *next;

}ArcNode;

     int vertex;

 ArcNode *firstarc;

int visited[MAXNODE];

int vexnum,arcnum;

// 建立圖的鄰接表

2)圖的基本操作如下：

void CreatMatrix(adjmatrix GA)

//從初始點v出發深度優先搜尋鄰接矩陣GA表示的圖

void DfsMatrix(adjmatrix GA,int v)

//從初始點v出發廣度優先搜尋鄰接矩陣GA表示的圖

void BfsMatrix(adjmatrix GA,int v)

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,5,4,3,2,

廣度優先周遊序列是: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

3

請輸入出發點編号:1

鄰接表為:

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

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

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

從第1點出發深度優先搜尋周遊序列:   1->

4

從第1點出發廣度優先搜尋周遊序列:

五、調試分析

調試中發現5個頂點6條邊的無向圖中

由于對稱使得深度優先周遊和廣度優先周遊都産生了

兩種：即2和5對稱的兩種結果

對于算法來說調試有時候可以檢驗算法

使算法的精神得以驅動程式這個軀體

附加程式的調試最不簡單原因是程式比較龐大

六、 源程式（帶注釋）

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;

     }

}

     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);

 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];

    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("請輸入廣度優先周遊的開始結點:");

  printf("廣度優先周遊序列是:");

  BfsMatrix(GA,v);

     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;

        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;

  }

      int i;

      visited[i]=0;

 if(!visited[v])

      dfs(GL,v);

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

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

 rear=(rear+1)%MAXNODE;

      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;

    }

  AdjList GL;

  creatgraph(GL);

  DfsAdjlist(GL,v);

  BfsAdjlist(GL,v);