實(shí)驗(yàn)6無(wú)向圖中求兩點(diǎn)間的所有簡(jiǎn)單路徑

1、實(shí)驗(yàn)6無(wú)向圖中求兩點(diǎn)間的所有簡(jiǎn)單路徑計(jì)科二班 宋瑞霞 20100810217一、需求分析1、用無(wú)向圖表示高速公路網(wǎng)，其中頂點(diǎn)表示城市，邊表示城市之間的高速公路。設(shè)計(jì)一個(gè)找路程序，獲取兩個(gè)城市之間的所有簡(jiǎn)單路徑。2、由用戶通過(guò)鍵盤輸入：（1）結(jié)點(diǎn)總數(shù)，（2）結(jié)點(diǎn)的城市編號(hào)（4位長(zhǎng)的數(shù)字，例如電話區(qū)號(hào)，長(zhǎng)沙是0731），（3）連接城市的高速公路（用高速公路連接的兩個(gè)城市編號(hào)標(biāo)記），（4）要求取所有簡(jiǎn)單路徑的兩個(gè)城市編號(hào)。不對(duì)非法輸入做處理，即假設(shè)輸入都是合法的。3、輸出：將所有路徑（有城市編號(hào)組成）輸出到dos界面上。4、測(cè)試數(shù)據(jù)：輸入：6 8（結(jié)點(diǎn)數(shù)和邊數(shù)） 0001 0002 0003 000

2、4 0005 0006（結(jié)點(diǎn)的城市編號(hào)） 0001 0003（連接城市間的高速公路） 0001 0005 0002 0006 0003 0002 0003 0004 0003 0006 0004 0006 0005 0006 0001 0002(要求取所有簡(jiǎn)單路徑的兩個(gè)城市編號(hào))輸出：0001 0003 0002（兩個(gè)城市間的所有簡(jiǎn)單路徑） 0001 0003 0006 00020001 0003 0004 0006 0002 0001 0005 0006 00020001 0005 0006 0003 00020001 0005 0006 0004 0003 0002二、概要設(shè)計(jì)抽象數(shù)據(jù)類型

3、根據(jù)對(duì)問(wèn)題的分析，要用無(wú)向圖表示高速公路網(wǎng)，其中頂點(diǎn)表示城市，邊表示城市之間的高速公路。所以要建立一個(gè)圖來(lái)實(shí)現(xiàn)。圖的adt設(shè)計(jì)如下：數(shù)據(jù)元素：包括一個(gè)頂點(diǎn)集合和一個(gè)邊集合數(shù)據(jù)關(guān)系：網(wǎng)狀關(guān)系基本操作： graph(int numvert) /構(gòu)造圖結(jié)構(gòu) virtual int n() =0; /獲取頂點(diǎn)的個(gè)數(shù) virtual int first(int ) =0; /訪問(wèn)所給頂點(diǎn)的第一個(gè)鄰居virtual int next(int ,int ) =0; /訪問(wèn)當(dāng)前鄰居的下一個(gè)鄰居virtual void setedge(int ,int ) =0; /建立所給兩頂點(diǎn)之間的邊virtual voi

4、d setmark(int v,int val) =0; /給頂點(diǎn)做標(biāo)記virtual int getmark(int v) =0; /獲取頂點(diǎn)是否已做標(biāo)記算法的基本思想首先，根據(jù)輸入的結(jié)點(diǎn)總數(shù)構(gòu)建一個(gè)線性表，將輸入的城市編號(hào)即頂點(diǎn)依次添加到線性表中；然后就是在圖的二維數(shù)組中存入邊即連接兩個(gè)城市間的高速公路，這步操作首先要找到兩個(gè)城市即兩個(gè)頂點(diǎn)在線性表中的位置如m和n，然后再在二維數(shù)組相應(yīng)的位置(m,n)上存入1建立該條邊；最后當(dāng)所有的邊都存入圖中后，由于深度優(yōu)先的結(jié)果是沿著圖的某一分支搜索直至末端，然后回溯，在沿著另一條分支搜索，依次類推，故對(duì)圖進(jìn)行深度優(yōu)先搜索，即可得到兩個(gè)城市間的簡(jiǎn)單路徑

5、。程序的流程程序由四個(gè)模塊組成：1、 輸入模塊：輸入圖的頂點(diǎn)和邊；2、 構(gòu)建模塊：用線性表存儲(chǔ)頂點(diǎn)，用二維數(shù)組存儲(chǔ)邊，構(gòu)建圖結(jié)構(gòu)；3、 處理模塊：對(duì)圖進(jìn)行深度優(yōu)先搜索；4、 輸出模塊：將深度優(yōu)先搜索后得到的所有簡(jiǎn)單路徑輸出到dos界面上。三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型該問(wèn)題需要輸入4位長(zhǎng)的數(shù)字表示的城市編號(hào)，為了能夠存儲(chǔ)，采用c+語(yǔ)言中的字符串string來(lái)定義變量線性表中的元素類型，數(shù)組的大小為4。根據(jù)用鄰接矩陣表示法來(lái)實(shí)現(xiàn)圖的相關(guān)知識(shí)，要先建立一個(gè)線性表來(lái)存儲(chǔ)頂點(diǎn)，由于結(jié)點(diǎn)總數(shù)即圖的頂點(diǎn)數(shù)已知，則線性表的長(zhǎng)度已知，故用順序表實(shí)現(xiàn)比較好，因?yàn)轫樞虮硎穷A(yù)先分配一段連續(xù)的存儲(chǔ)空間，而且沒(méi)有結(jié)構(gòu)性開(kāi)銷。

6、1、順序表的具體實(shí)現(xiàn)如下： template（在本問(wèn)題，elem為string） class alist private: int maxsize;/順序表的最大長(zhǎng)度 int listsize;/ 順序表的實(shí)際長(zhǎng)度 int fence;/指向當(dāng)前位置 elem * listarray;/存儲(chǔ)順序表元素的數(shù)組public: alist(int size=defaultlistsize)/構(gòu)造一個(gè)由用戶指定最大長(zhǎng)度的空順序表 maxsize =size; listsize=fence=0; listarray= new elem maxsize; bool append(const elem &

7、item)/添加 if(listsize=maxsize) return false; else listarraylistsize+=item; return true; int rightlength() const/右邊長(zhǎng)度 return listsize-fence; bool getvalue(ielem& it) const/獲取當(dāng)前位置的元素值，若右邊為空，返回false if(rightlength()=0) return false; else it=listarrayfence; return true; void setstart()/將當(dāng)前位置置0 fence=0; v

8、oid next()/右移一位 if(fencelistsize) fence+; ;2、圖的具體實(shí)現(xiàn)如下：class graphprivate:int numvertex,numedge;/存儲(chǔ)頂點(diǎn)數(shù)和邊數(shù)int *matrix;/指向鄰接矩陣的指針int *mark; /指向訪問(wèn)標(biāo)記數(shù)組的指針public:graph(int numvert)/實(shí)現(xiàn)鄰接矩陣int i,j;numvertex=numvert;numedge=0;mark=new intnumvert;for(i=0;inumvertex;i+)/初始化標(biāo)記數(shù)組marki=0;matrix=(int*) new int*num

9、vertex;/構(gòu)造鄰接矩陣for(i=0;inumvertex;i+)matrixi=new intnumvertex;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)matrixij=0;graph()/析構(gòu)函數(shù)delete mark;for(int i=0;inumvertex;i+)delete matrixi;delete matrix;int n()/獲取頂點(diǎn)個(gè)數(shù)return numvertex;int e()/獲取邊的個(gè)數(shù)return numedge;int first(int v) /訪問(wèn)所給頂點(diǎn)的第一個(gè)鄰居int i;for(i=0;i

10、numvertex;i+)if(matrixvi!=0)return i;return i;int next(int v1,int v2) /訪問(wèn)當(dāng)前鄰居的下一個(gè)鄰居int i;for(i=v2+1;inumvertex;i+)if(matrixv1i!=0)return i;return i;void setedge(int v1,int v2) /無(wú)向圖中建立所給兩頂點(diǎn)之間的邊if(matrixv1v2=0)numedge+;matrixv1v2=1;matrixv2v1=1;void setmark(int v,int val) /給頂點(diǎn)做標(biāo)記markv=val;int getmark(

11、int v) /獲取頂點(diǎn)是否已做標(biāo)記return markv;算法的具體步驟1、定義順序表l、圖g，還有存儲(chǔ)課程名的字符串string city，city1，city2，輸入頂點(diǎn)個(gè)數(shù)n和邊數(shù)m。2、輸入頂點(diǎn)city并將輸入的頂點(diǎn)依次存入順序表l中。for(int i=0;icity;l.append(city);3、輸入有路連接的兩個(gè)城市編號(hào)，即相互間存在邊的兩個(gè)頂點(diǎn)，找到這兩個(gè)頂點(diǎn)在線性表中的位置，然后在圖的二維數(shù)組相應(yīng)的位置上存入1建立該條邊。通過(guò)一個(gè)循環(huán)將所有的邊都建完，完成圖的存儲(chǔ)。for(int i=0;icity1city2; g.setedge(find(l,n,city1),f

12、ind(l,n,city2);其中find函數(shù)即實(shí)現(xiàn)找到頂點(diǎn)在線性表中的位置的功能，具體如下：int find(alist l,int n,int& city)int i;string city1;l.setstart();for(i=0;in;i+)l.getvalue(city1);/獲取當(dāng)前位置的元素值if(city1=city)/若當(dāng)前位置的元素值與所要找的頂點(diǎn)值相同return i;/則返回當(dāng)前位置所在的位置elsel.next();/若不同，則在向右移一位再做判斷4、 對(duì)圖進(jìn)行深度優(yōu)先搜索int addr100;int num=-1;void dfs(graph& g,int v,

13、alist& l,int d) g.setmark(v,1);if (v = d) for(int i=0;i=num;i+) printout(l,addri); cout ; coutendl;g.setmark(d,0);num-;return;for (int w = g.first(v);w g.n();w = g.next(v,w)if (g.getmark(w) = 0) addr+num=w;dfs(g,w,l,d); num-;g.setmark(v,0);其中的輸出函數(shù)為：void printout(alist l,int v)l.setstart();string s;

14、for(int i=0;iv;i+)l.next();l.getvalue(s);couts ;算法的時(shí)空分析 設(shè)v為頂點(diǎn)數(shù)，e為邊數(shù)，（1）由于順序表用來(lái)存儲(chǔ)頂點(diǎn)，順序隊(duì)列用來(lái)存儲(chǔ)入度為0的頂點(diǎn)，所以它們的空間代價(jià)都為（|v|）；而鄰接矩陣的空間代價(jià)為（|v|2），故總的空間代價(jià)為（|v|2）。（2）由于順序表的添加操作的時(shí)間復(fù)雜度為（1），故將所有結(jié)點(diǎn)存入順序表的時(shí)間復(fù)雜度為（|v|）；在對(duì)無(wú)向圖進(jìn)行深度優(yōu)先時(shí)，dfs從兩個(gè)方向處理每條邊，每個(gè)頂點(diǎn)都必須被訪問(wèn)，而且只能訪問(wèn)一次，故總的時(shí)間復(fù)雜度為（|v|+|e|）。輸入和輸出的格式輸入：請(qǐng)輸入結(jié)點(diǎn)總數(shù)和邊數(shù): /提示 等待輸入 請(qǐng)輸入城市

15、編號(hào): /提示 等待輸入 請(qǐng)輸入有路連接的兩個(gè)城市的編號(hào): /提示 等待輸入請(qǐng)輸入要求取所有簡(jiǎn)單路徑的兩個(gè)城市編號(hào): /提示 等待輸入輸出：這兩個(gè)城市間的所有簡(jiǎn)單路徑為：/提示 輸出結(jié)果的位置四、調(diào)試分析 大部分是語(yǔ)法錯(cuò)誤，看著錯(cuò)誤提示都改過(guò)來(lái)了，今天又學(xué)到點(diǎn)新知識(shí)，就是如果執(zhí)行的界面沒(méi)關(guān)的話，連接時(shí)會(huì)出現(xiàn)錯(cuò)誤。五、測(cè)試結(jié)果六、用戶使用說(shuō)明1、本程序的運(yùn)行環(huán)境為dos操作系統(tǒng)2、運(yùn)行程序時(shí)提示輸入結(jié)點(diǎn)總數(shù)和邊數(shù) 城市編號(hào)有路連接的兩個(gè)城市的編號(hào)要求取所有簡(jiǎn)單路徑的兩個(gè)城市編號(hào)輸出：兩個(gè)城市間的所有簡(jiǎn)單路徑七、實(shí)驗(yàn)心得這次實(shí)驗(yàn)感覺(jué)好難啊，搞了一天的預(yù)習(xí)報(bào)告，結(jié)果就得了1分，那種感覺(jué)真的好難受的！

16、八、程序#include#includeusing namespace std;#define elem string class alist private: int maxsize;/順序表的最大長(zhǎng)度 int listsize;/ 順序表的實(shí)際長(zhǎng)度 int fence;/指向當(dāng)前位置 elem * listarray;/存儲(chǔ)順序表元素的數(shù)組public: alist(int size)/構(gòu)造一個(gè)由用戶指定最大長(zhǎng)度的空順序表 maxsize =size; listsize=fence=0; listarray= new elem maxsize; bool append(const elem

17、 & item)/添加 if(listsize=maxsize) return false; else listarraylistsize+=item; return true; bool remove()/刪除 elem it; if(rightlength()=0) return false; it=listarray fence; for(int i=fence;ilistsize-1;i+) listarrayi= listarrayi+1; listsize-; return true; int rightlength() const/右邊長(zhǎng)度 return listsize-fen

18、ce; bool getvalue(elem& it) const/獲取當(dāng)前位置的元素值，若右邊為空，返回false if(rightlength()=0) return false; else it=listarrayfence; return true; void setstart()/將當(dāng)前位置置0 fence=0; void next()/右移一位 if(fence=0)&(pos=0)& (pos=listsize); ;class graphprivate:int numvertex,numedge;int *matrix;int *mark;public:graph(int nu

19、mvert)int i,j;numvertex=numvert;numedge=0;mark=new intnumvert;for(i=0;inumvertex;i+)marki=0;matrix=(int*) new int*numvertex;for(i=0;inumvertex;i+)matrixi=new intnumvertex;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)matrixij=0;graph()delete mark;for(int i=0;inumvertex;i+)delete matrixi;delete matrix;

20、int n()return numvertex;int e()return numedge;int first(int v)int i;for(i=0;inumvertex;i+)if(matrixvi!=0)return i;return i;int next(int v1,int v2)int i;for(i=v2+1;inumvertex;i+)if(matrixv1i!=0)return i;return i;void setedge(int v1,int v2)matrixv1v2=1;matrixv2v1=1;void setmark(int v,int val)markv=val;int getmark(int v)return markv;int find(alist l,int n,string s)int i;string s1;l.setstart();for(i=0;in;i+)l.getvalue(s1);if(s1=s)return i;elsel.next();void