1、學(xué)院名稱專業(yè)班級實驗成績學(xué)生姓名學(xué)號實驗日期課程名稱數(shù)據(jù)結(jié)構(gòu)實驗題目3 圖一、實驗?zāi)康呐c要求熟悉圖的存儲結(jié)構(gòu)，掌握有關(guān)算法的實現(xiàn)，了解圖在計算機科學(xué)及其他工程技術(shù)中的應(yīng)用。二、主要儀器設(shè)備Cfree三、實驗內(nèi)容和原理 問題描述采用鄰接表存儲結(jié)構(gòu)，編寫一個求無向圖的連通分量個數(shù)的算法。輸入圖頂點的個數(shù)，和以各個頂點為弧尾的所有弧，并以-1結(jié)束輸入。輸出連通分量的個數(shù)。存儲結(jié)構(gòu)圖采用鄰接矩陣的方式存儲。算法的基本思想用到深度優(yōu)先搜索，先從任意一個頂點開始進行深度優(yōu)先搜索，搜索完后，連通分量個數(shù)增1。然后再從沒有遍歷過的頂點找一個出來進行深度優(yōu)先搜索，搜索完后，連通分量個數(shù)增1。一直到所有的頂點都被

2、遍歷過。參考源程序#include<stdio.h>#include<malloc.h>int n;struct VNode /頂點 int position;struct VNode* next;struct ArcNode /弧int mark;struct VNode* first;void DFS(struct ArcNode* v,struct ArcNode* w) /深度優(yōu)先搜索struct VNode* L;w->mark=1;L=w->first;while(L!=NULL)if(v+(L->position)->mark=0)

3、DFS(v,(v+L->position); /遞歸調(diào)用L=L->next;int main()int i,j,k;int num=0;struct ArcNode* p;struct VNode* temp;struct VNode* flag;printf("n請輸入頂點個數(shù) n：");scanf("%d",&n);while(n<1)printf("你輸入的值不合理，請重新輸入：n");scanf("%d",&n);p=(struct ArcNode*)malloc(n*si

4、zeof(struct ArcNode);/*說明：1.Vi表示第i個頂點，它在表中的位置為i-1，如V3在表中的位置為2; 2.如果輸入以V1為弧尾的所有弧(假設(shè)存在弧<V1,V3>和<V1,V2>) 則輸入：2 1 -1(只需輸入弧頭的位置，并用-1表示結(jié)束)*/for(i=0;i<n;i+) /創(chuàng)建無向圖printf("n請輸入以V%d為弧尾的所有弧，并以-1結(jié)束輸入n",i+1);scanf("%d",&k); if(k=-1)pi.mark=0;pi.first=NULL;elsetemp=(struct

5、VNode*)malloc(sizeof(struct VNode);temp->position=k;temp->next=NULL;pi.first=temp;pi.mark=0;flag=temp;scanf("%d",&k);while(k!=-1)temp=(struct VNode*)malloc(sizeof(struct VNode);temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf("%d",&k); i=0;while(pi.mark=0) /計算連通分量的個數(shù)DFS(p,(p+i);num+;i=0;while(pi.mark!=0&&i<n)i+;printf("此圖的連通分量個數(shù)為：%dn",num);system("pause");return 0; 五、實驗結(jié)果與分析習(xí)題1：這題主要還是用到深度優(yōu)先搜索，先從任意一個頂點開始進行深度優(yōu)先搜索，搜索完后，連通分量個數(shù)增1。然后再從沒有遍歷過的頂點找一個出來進行深度優(yōu)先搜索，搜索完后，連通分量個數(shù)增1。一直到所有的頂點都被遍歷過。