???? 不想麻煩聲明函數,所以把實現寫到頭文件中了,只剩下一個cpp文件main.cpp.
??? 本程序實現了深度優先搜索非遞歸算法和單源最短路徑Bellman_Ford算法;
??? DFS用非遞歸效率高,因為輸入規模太大,遞歸讓我電腦吃不消,
?? Bellman_Ford算法可以處理負權值圖,這點比Dijkstra算法好.
1
/**//******************************************
2
?程序名稱:DFS和Bellman_Ford算法的實現
3?作者:pengkuny
4?主頁:http://m.shnenglu.com/pengkuny
5?郵箱:pengkuny@163.com
6?參考書籍:<<Introduction?to?Agrithms>>
7?完成日期:2006.11.30
8
******************************************/ ALGraph.h
?1/**//*?ALGraph.h?圖的鄰接表存儲表示?*/
?2
#ifndef?ALGRAPH_H
?3#define?ALGRAPH_H
?4
?5#include<iostream>
?6#include<cstdio>
?7#include<cmath>
?8#include<cstring>
?9
10using?namespace?std;
11
12#define?wuqiong?65535??????//初始權值無窮大
13
14typedef?enum?
{WHITE,GRAY,BLACK};
15
16typedef?struct?VNode?VNode;
17
18typedef?struct?ArcNode
19{
20
????int?????????adjvex;??/**//*?原頂點?*/
21????ArcNode*????next;????/**//*?指向下一條弧的指針?*/
22????long????????weight;??/**//*?權值?*/
23}ArcNode;????????????????????/**//*?表結點?*/
24
25
26typedef?struct?VNode
27{????
28????int????????adjvex;???????????/**//*?頂點序號????*/
29????int???????????color;????????????/**//*?頂點顏色????*/
30????long????????d;???????????????/**//*?頂點最初DFS發現時間?;?兼作Dijkstra算法中當前最短路徑?*/
31????long????????f;???????????????/**//*?頂點最終DFS結束時間?*/
32????VNode?*?????father;
33????ArcNode?*???next;?????????/**//*?第一個表結點的地址,指向第一條依附該頂點的弧的指針?*/
34}VNode,*?AdjList?;?/**//*?頭結點?*/
35
36
37typedef?struct
38{
39????AdjList?vertices;????????????????/**//*?表結點指針(一個頭結點數組)?*/
40????int?????vexnum,arcnum;???????????/**//*?圖的當前頂點數和弧數?*/
41}ALGraph;
42??
43
44#endif//ALGRAPH_H Stack.h: 棧的表示,DFS使用棧非遞歸
?1/**//*?Stack.h?圖的鄰接表存儲表示?*/
?2#ifndef?STACK_H
?3#define?STACK_H
?4
?5#include?"ALGraph.h"
?6
?7#include<iostream>
?8#include<cstdio>
?9#include<cmath>
10#include<cstring>
11
12using?namespace?std;
13
14typedef?struct??LinkList
15{
16????VNode?*??data;????//棧中只保存圖頂點指針
17????LinkList?*?next;??//下一個頂點
18}LinkList;
19
20typedef?struct??Stack
21{
22????LinkList?*?top;
23}Stack;
24
25
26void?InitStack(Stack?&S)
27{
28????S.top?=?NULL;
29}
30
31bool?Empty(Stack?S)
32{
33????if?(S.top?==?NULL)
34????{
35????????return?true;
36
????}
37????return?false;
38}
39
40void?Push(Stack?&S,?VNode*?k)
41{
42
43????LinkList?*?p?=?new?LinkList;
44????p->data?=?k;
45????p->next?=?S.top;
46????S.top?=?p;
47}
48
49VNode*?GetTop(Stack&?S)
50{
51????return?S.top->data;
52}
53
54VNode*?Pop(Stack&?S)
55{
56????LinkList*?p?=?S.top;//保存棧頂指針
57????VNode*?q;
58????if(Empty(S))
59????{
60????????cout<<"Stack?underflow.";??//下溢
61????????exit(1);
62????}
63
64????S.top?=?p->next;??//將棧頂結點從鏈上摘下
65
66????q?=?p->data;//回收棧空間,不可以寫成q=p;delete?p;return?q->data;
67????delete?p;???//因為delete?p之后,p所指的空間已不可用
68
69????return?q;
70}
71
72
73#endif//STACK_H CTimer.h:CTimer類,計時功能,單位毫秒
?1#ifndef?CTIMER_H
?2#define?CTIMER_H
?3
?4#include?"Windows.h"
?5
?6class???CTimer???
?7{???
?8public:???
?9????CTimer()?
10????{
11????????QueryPerformanceFrequency(&m_Frequency);//取CPU頻率
12????}???
13????void?Start()
14????{
15????????QueryPerformanceCounter(&m_StartCount);//開始計數
16????}???
17????double?End()?
18????{
19????????LARGE_INTEGER???CurrentCount;
20????????QueryPerformanceCounter(&CurrentCount);//終止計數
21????????return?
22????????????double(CurrentCount.QuadPart-m_StartCount.QuadPart)*1000/(double)m_Frequency.QuadPart;
23????????
24????}???
25private:???
26????LARGE_INTEGER???m_Frequency;???
27????LARGE_INTEGER???m_StartCount;???
28};
29
30#endif//CTIMER_H??? CreateALGraph.h: 創建鄰接圖G
??1#include?"ALGraph.h"
??2
??3void?CreateALGraph(ALGraph&?G,long?vexnum,?long?arcnum)
??4{
??5????int?i,j,m,n;
??6????bool?flag?=?false;//檢查邊是否已存在
??7????int?*?weight?=?new?int[arcnum];
??8????for(i?=?0;?i?<?G.arcnum;?i++)
??9????{
?10????????weight[i]?=?0;??//初始權值為零????
?11????}
?12
?13????AdjList?vertices?=?new?VNode[vexnum]?;?//動態分配頭結點數組
?14????ArcNode*?p?=?NULL;?
?15????ArcNode*?q?=?NULL;?
?16????srand(NULL);
?17????
?18????G.vexnum?=?vexnum;
?19????G.arcnum?=?arcnum;
?20????for(i=0;?i<G.vexnum;?i++)
?21????{
?22????????vertices[i].adjvex?=?i;?????//?頂點序號
?23????????vertices[i].color?=?WHITE;??//?頂點顏色???
?24????????vertices[i].d?=?0;???//?頂點最初DFS發現時間?;?兼作Bellman_Ford算法中當前最短路徑?
?25????????vertices[i].f?=?0;??????????//?頂點最終DFS結束時間?
?26????????vertices[i].father?=?NULL;??//訪問路徑上的父結點
?27????????vertices[i].next?=?NULL;????//表結點指針,叫做firstarc似乎更合適,也更好控制,懶得改了
?28????}
?29????G.vertices?=?vertices;
?30????
?31????
?32????for(i?=?0;?i?<?G.arcnum;?i++)//隨機產生arcnum條邊
?33????{
?34????????weight[i]?=?rand()%1000?;//-?200;?//適當加一些負權值邊
?35????????if?(weight[i]?==?0)
?36????????{
?37????????????weight[i]++;//不能讓權值為零,否則等于沒有添加邊
?38????????}
?39????}
?40????
?41????for(i?=?0;?i?<?G.arcnum;?i++)//打亂數組
?42????{?
?43????????j?=?rand()%G.arcnum?;//隨機選取數組下標,注意整除的是數組大小
?44????????if?(j>=0?&&?j<G.arcnum)?
?45????????{
?46????????????int?exchange=weight[i];
?47????????????weight[i]=weight[j];
?48????????????weight[j]=exchange;????
?49????????}
?50????}
?51????
?52????
?53????i?=?0;
?54????j?=?0;
?55????while?(2*i+1?<?G.vexnum)//先將V-1條邊分配,為保證圖是連通的,按完全二叉樹結構產生邊
?56????????//當然這樣產生的邊不夠隨機性
?57????{???????????
?58????????p?=?new?ArcNode;????
?59????????p->adjvex?=?2*i+1;
?60????????p->weight?=?weight[j++];
?61????????p->next?=?NULL;???????????
?62????????G.vertices[i].next?=?p;//k尚無鄰接點,p作為第一個鄰接點
?63????????
?64????????if?(2*i+2?<?G.vexnum)
?65????????{
?66????????????q?=?p;
?67????????????p->next?=?new?ArcNode;//動態分配表結點
?68????????????p?=?p->next;
?69????????????p->adjvex?=?2*i+2;
?70????????????p->weight?=?weight[j++];
?71????????????p->next?=?NULL;
?72????????????G.vertices[i].next->next?=?p;
?73????????}
?74????????else
?75????????????break;//V-1條邊分配完畢
?76????????
?77????????i++;
?78????}
?79????
?80????
?81????for(i?=?G.vexnum-1;?i?<?G.arcnum;?)//將剩下的邊分配出去
?82????{
?83????????flag?=?false;
?84????????
?85????????m?=?rand()%G.vexnum;?//隨機弧尾序號
?86????????n?=?rand()%G.vexnum;?//隨機弧頭序號
?87????????while?(m?==?n)???????//不考慮指向自身的結點
?88????????{
?89????????????n?=?rand()%G.vexnum;
?90????????}
?91????????
?92????????if?(G.vertices[m].next?!=?NULL)????????????
?93????????{
?94????????????p?=?G.vertices[m].next;
?95????????}
?96????????else??//k尚無鄰接點
?97????????{
?98????????????p?=?NULL;
?99????????????q?=?NULL;
100????????}
101????????
102????????while?(p?!=?NULL)
103????????{
104????????????if?(p->adjvex?==?n)
105????????????{
106????????????????flag?=?true;//邊已經存在
107????????????????break;
108????????????}
109????????????else//繼續往下找
110????????????{
111????????????????q?=?p;
112????????????????p?=?p->next;
113????????????}
114????????}
115????????
116????????if?(!flag)//Vm→Vn的邊本不存在
117????????{
118????????????p?=?new?ArcNode;
119????????????
120????????????p->adjvex?=?n;
121????????????p->weight?=?weight[i];
122????????????p->next?=?NULL;
123????????????if?(q!=NULL)?
124????????????{
125????????????????q->next?=?p;
126????????????}
127????????????else
128????????????????G.vertices[m].next?=?p;
129????????????
130????????????i++;//僅當成功分配一條邊才i++;?本循環存在死循環的可能,即永遠碰巧都分配不出去
131????????????//考慮復雜度和出錯的概率,姑且不管它.
132????????}
133????}
134
135????delete?[]?weight;
136}
137
138
139
140void?ShowGraph(ALGraph?G)???//打印創建后的圖
141{
142????for(int?i=0;?i<G.vexnum;?i++)
143????{
144????????ArcNode?*?p?=?G.vertices[i].next;
145????????cout<<"source?V"<<G.vertices[i].adjvex<<":";
146????????while(p!=NULL)
147????????{
148????????????cout<<"??V"<<p->adjvex;
149????????????cout<<"(w:?"<<p->weight<<")";
150????????????p=p->next;
151????????}
152????????cout<<endl;
153
154????}
155} ClearUp.h: 銷毀圖G,回收工作
?1#include?"ALGraph.h"
?2
?3void?ClearUp(ALGraph?&G)//銷毀圖G
?4{
?5????ArcNode*?p?=?NULL;????
?6????ArcNode*?q?=?NULL;
?7????int?i;
?8????for(i=0;?i<G.vexnum;?i++)??//回收表結點
?9????{????
10????????p?=?G.vertices[i].next;
11????????while?(p?!=?NULL)?
12????????{
13????????????q?=?p->next;
14????????????delete?p;
15????????????p?=?q;????????????
16????????}
17????}
18
19????delete?[]?G.vertices;?????//回收頭結點
20????G.vertices?=?NULL;
21????G.arcnum?=?0;
22????G.vexnum?=?0;
23} DFS.h: 深度優先遍歷
?1#include?"ALGraph.h"
?2#include?"Stack.h"
?3
?4void?DFSVisit(ALGraph&?G,?VNode&?s,?int&?time);
?5
?6void?DFS(ALGraph&?G)
?7{
?8????int?time?=?0;????
?9????for(int?i=0;?i<G.vexnum;?i++)??//初始化
10????{
11????????G.vertices[i].color?=?WHITE;
12????????G.vertices[i].father?=?NULL;
13????}
14????
15????for(i=0;?i<G.vexnum;?i++)?????//深度優先遍歷
16????{
17????????if?(G.vertices[i].color?==?WHITE)?
18????????????DFSVisit(G,?G.vertices[i],?time);
19????}
20}
21
22void?DFSVisit(ALGraph&?G,?VNode&?s,?int&?time)??/**//*從s出發深度優先搜索圖G*/
23{
24????Stack?S;
25????ArcNode?*?p;?
26????VNode*?k;//出棧頂點序號
27????VNode*?t;
28????
29????InitStack(S);??/**//*初始化空棧*/
30????
31????s.color?=?GRAY;
32????time?=?time?+1;
33????s.d?=?time;
34????Push(S,?&s);?
35????while(!Empty(S))
36????{?
37????????t?=?GetTop(S);??//彈出棧頂,返回棧頂元素地址
38
39????????for(p=t->next;?p?&&?G.vertices[p->adjvex].color!=WHITE;?p=p->next);
40????????//找到第一個白色鄰接點
41????????if(p?==?NULL)//t的所有鄰接點都已訪問
42????????{
43????????????k?=?Pop(S);
44????????????k->color?=?BLACK;
45????????????time?=?time+1;
46????????????k->f?=?time;//結束時間
47????????}
48????????else//繼續深度訪問
49????????{
50????????????Push(S,&G.vertices[p->adjvex]);
51????????????G.vertices[p->adjvex].father?=?t;
52????????????G.vertices[p->adjvex].color?=?GRAY;
53????????????time?=?time+1;
54????????????G.vertices[p->adjvex].d?=?time;//入棧之時即發現之時d
55????????}
56????}
57} Bellman_Ford算法
?1#include?"ALGraph.h"
?2
?3void?Initialize_Single_Source(ALGraph&?G,VNode&?s)//初始化
?4{
?5????for(int?i=0;?i<G.vexnum;?i++)
?6????{
?7????????G.vertices[i].father?=?NULL;
?8????????G.vertices[i].d?=?wuqiong;????
?9????}
10????s.d?=?0;
11}
12
13void?Relax(VNode&?v,?VNode&?w,?ArcNode?*?p)//Relax操作,更新最短路徑
14{
15????if?(w.d?>?v.d+?p->weight)
16????{
17????????w.d?=?v.d+?p->weight;
18????????w.father?=?&v;
19????}
20}
21
22bool?Bellman_Ford(ALGraph&?G,?VNode&?s)
23{
24????ArcNode?*?p;
25????int?i;
26????
27????Initialize_Single_Source(G,?s);
28
29????for?(int?j=0;?j<G.vexnum-1;?j++)//V-1趟Relax
30????{
31????????for(i=0;?i<G.vexnum;?i++)//沿著頭結點
32????????{
33????????????for?(p=G.vertices[i].next;?p!=NULL;?p=p->next)//沿著表結點
34????????????{????????????
35????????????????Relax(G.vertices[i],?G.vertices[p->adjvex],?p);
36????????????}
37????????}
38????}
39
40????//判斷是否有負回路
41????for(i=0;?i<G.vexnum;?i++)//沿著頭結點
42????{
43????????for?(p=G.vertices[i].next;?p!=NULL;?p=p->next)//沿著表結點
44????????{
45????????????if?(G.vertices[p->adjvex].d?>?G.vertices[i].d+?p->weight)?
46????????????{
47????????????????cout<<"圖中有負權值回路."<<endl;
48????????????????return?false;
49????????????}
50????????}
51????}
52
53????return?true;????????????????
54}
55
56void?PrintPath(ALGraph?G,?VNode?s,?VNode?v)//遞歸打印最短路徑
57{????
58????if?(v.father?!=?NULL)
59????{
60????????PrintPath(G,?s,?*v.father);
61????????cout<<"v"<<v.adjvex<<"→";
62????}
63????else
64????????cout<<"v"<<s.adjvex<<"→";????
65}
66
67void?ShortestPath(ALGraph?G,?VNode?s)
68{
69????int?i=0;
70????cout<<"頂點為v0,v1,v2,……,v"<<G.vexnum-1<<endl;
71????cout<<"從源點v"<<s.adjvex<<"到其它所有頂點的最短距離:"<<endl;
72????for(i=0;?i<G.vexnum;?i++)//沿著頭結點
73????{
74????????cout<<"到頂點v"<<i<<":??";
75????????PrintPath(G,?s,?G.vertices[i]);
76????????cout<<endl;
77????}
78}
79
80void?DFSPath(ALGraph?G,?VNode?s)//打印DFS各頂點的發現時間和結束時間d/f;
81{
82????int?i=0;
83????for(i=0;?i<G.vexnum;?i++)//沿著頭結點
84????{
85????????//PrintPath(G,?s,?*k);
86????????cout<<"v"<<G.vertices[i].adjvex<<":"<<G.vertices[i].d<<"?/?"
87????????????<<G.vertices[i].f<<"??顏色:"<<G.vertices[i].color;
88????????cout<<endl;
89????}
90} main函數:對不同輸入規模計時分析算法性能
?1#include?"ALGraph.h"
?2#include?"DFS.h"
?3#include?"CreateALGraph.h"
?4#include?"Bellman_Ford.h"
?5#include?"ClearUp.h"
?6#include?"CTimer.h"
?7
?8#include<iostream>
?9#include<cstdio>
10#include<cmath>
11#include<cstring>
12
13
14int?main()
15
16{
17????//輸入規模
18????const?int?NUM1[6]?=?{1000,2500,5000,7500,10000,15000};
19????const?int?RATE1[4]?=?{pow(2,2),pow(2,4),pow(2,6),pow(2,8)};
20????const?int?NUM2[6]?=?{200,400,800,1200,1600,2000};
21????const?int?RATE2[5]?=?{pow(2,2),pow(2,3),pow(2,4),pow(2,5),pow(2,6)};
22????
23????ALGraph?G;??????????//圖G
24????CTimer?timer;???????//計數器
25????int?i,j;?????????
26????double?runningtime;?//運行時間(毫秒/ms)
27????long?vexnum;????????//圖頂點數
28????long?arcnum;????????//圖邊數
29????
30????for(i=0;?i<6;?i++)//DFS運行時間分析
31????{????
32????????cout<<"/********************************/"<<endl;
33????????for(j=0;j<4;?j++)
34????????{
35????????????vexnum?=?NUM1[i];
36????????????arcnum?=?NUM1[i]*RATE1[j];
37????????????CreateALGraph(G,?vexnum,?arcnum);//創建圖
38????????????timer.Start();?????????????//計時開始
39????????????DFS(G);????????????
40????????????runningtime?=?timer.End();//計時結束
41????????????cout<<"????"<<runningtime<<"ms"<<endl;???????????????
42//????????????DFSPath(G,?*G.vertices);
43????????????ClearUp(G);
44????????}????
45????}
46????
47????for(i=0;?i<6;?i++)//Bellman_Ford最短路徑算法運行時間分析
48????{????
49????????cout<<"/********************************/"<<endl;????????
50????????for(j=0;j<5;?j++)????????{
51????????????vexnum?=?NUM2[i];
52????????????arcnum?=?NUM2[i]*RATE2[j];
53????????????CreateALGraph(G,?vexnum,?arcnum);
54//????????????ShowGraph(G);??????????????//打印原始圖
55????????????timer.Start();?????????????//計時開始
56????????????Bellman_Ford(G,?*G.vertices);
57????????????runningtime?=?timer.End();//計時結束
58????????????cout<<"????"<<runningtime<<"ms"<<endl;
59//????????????ShortestPath(G,?*G.vertices);//打印源點v0到各頂點的最短路徑
60????????????ClearUp(G);
61????????}
62????}
63????
64????
65????return?0;
66}
posted on 2006-12-02 10:34
哈哈 閱讀(1585)
評論(2) 編輯 收藏 引用