實驗6無向圖中求兩點間的所有簡單路徑

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

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

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

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

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

6、1、順序表的具體實現(xiàn)如下： template（在本問題，elem為string） class alist private: int maxsize;/順序表的最大長度 int listsize;/ 順序表的實際長度 int fence;/指向當(dāng)前位置 elem * listarray;/存儲順序表元素的數(shù)組public: alist(int size=defaultlistsize)/構(gòu)造一個由用戶指定最大長度的空順序表 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/右邊長度 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、圖的具體實現(xiàn)如下：class graphprivate:int numvertex,numedge;/存儲頂點數(shù)和邊數(shù)int *matrix;/指向鄰接矩陣的指針int *mark; /指向訪問標(biāo)記數(shù)組的指針public:graph(int numvert)/實現(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()/獲取頂點個數(shù)return numvertex;int e()/獲取邊的個數(shù)return numedge;int first(int v) /訪問所給頂點的第一個鄰居int i;for(i=0;i

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

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

12、ind(l,n,city2);其中find函數(shù)即實現(xià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)前位置的元素值與所要找的頂點值相同return i;/則返回當(dāng)前位置所在的位置elsel.next();/若不同，則在向右移一位再做判斷4、 對圖進行深度優(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è)v為頂點數(shù)，e為邊數(shù)，（1）由于順序表用來存儲頂點，順序隊列用來存儲入度為0的頂點，所以它們的空間代價都為（|v|）；而鄰接矩陣的空間代價為（|v|2），故總的空間代價為（|v|2）。（2）由于順序表的添加操作的時間復(fù)雜度為（1），故將所有結(jié)點存入順序表的時間復(fù)雜度為（|v|）；在對無向圖進行深度優(yōu)先時，dfs從兩個方向處理每條邊，每個頂點都必須被訪問，而且只能訪問一次，故總的時間復(fù)雜度為（|v|+|e|）。輸入和輸出的格式輸入：請輸入結(jié)點總數(shù)和邊數(shù): /提示 等待輸入 請輸入城市

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

16、八、程序#include#includeusing namespace std;#define elem string class alist private: int maxsize;/順序表的最大長度 int listsize;/ 順序表的實際長度 int fence;/指向當(dāng)前位置 elem * listarray;/存儲順序表元素的數(shù)組public: alist(int size)/構(gòu)造一個由用戶指定最大長度的空順序表 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/右邊長度 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