DFS和Bellman_Ford算法的代码实现
     不想麻烦声明函数,所以把实现写到头文件中了,只剩下一个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 哈哈 阅读(1570) 评论(2)  编辑 收藏 引用

评论:
# re: DFS和Bellman_Ford算法的代码实现 2008-07-20 16:24 | woer
Bellman里面如果图是不联通的呢？
这个都没有处理  回复  更多评论
  
# re: DFS和Bellman_Ford算法的代码实现 2009-02-17 22:01 | yangtao
good!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 哈哈