不想麻烦声明函数,所以把实现写到头文件中了,只剩下一个cpp文件main.cpp.
本程序实现了深度优先搜索非递归算法和单源最短路径Bellman_Ford算法;
DFS用非递归效率高,因为输入规模太大,递归让我电脑吃不消,
Bellman_Ford算法可以处理负权值图,这点比Dijkstra算法好.
1
/**//******************************************
2
程序名称:DFS和Bellman_Ford算法的实现
3 作者:pengkuny
4 主页:http://www.cppblog.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
哈哈 阅读(1579)
评论(2) 编辑 收藏 引用