首页 > 代码库 > 图的深度优先搜索 递归和非递归实现 c++版本

图的深度优先搜索 递归和非递归实现 c++版本

本文参考了李春葆版本的数据结构上机指导,但是原版是c代码,

本文用了c++实现,并且修复了深度优先搜索非递归的一个bug。

graph.cpp文件:

#include "graph.h"
#include <queue>
#include <stack>
int visited[MAXV ];
MGraph ::MGraph(int A[100][10], int nn , int ee)
{
                e= ee ;
                n= nn ;
                 for (int i=0;i<n;i++)
                {
                                 for (int j=0;j<n;j++)
                                                edges[i][j]= A [i][j];
                }
}

void MGraph ::DispMat( MGraph g )
{
                 int i,j;
                 for (i=0;i<g .n;i++)
                {
                                 for (j=0;j<g .n;j++)
                                                cout<< g .edges[i][j]<<"       " ;
                                cout<<endl;
                }

}


ALGragh ::ALGragh(int a[ MAXV][10], int n , int e)
{
                 ALGragh ::n=n ;
                 ALGragh ::e=e ;
                 for (int i=0;i< n;i++)
                {
                                adjlist[i].firstarc= NULL ;
                }
                 for (int i=0;i< n;i++)
                                 for (int j= n-1;j>=0;j--)
                                {
                                                 if (a [i][j]!=0)
                                                {     //作用域里面,必须动态分配。直接写ArcNode p(adjlist[i].firstarc,j,a[i][j])会被析构
                                                                 ArcNode *p=new ArcNode (adjlist[i].firstarc,j, a [i][j]);
                                                                adjlist[i].firstarc=p;
                                                }
                                }
}

void ALGragh ::DispAdj( ALGragh * G )
{
                 ArcNode *p;
                 for (int i=0;i< G->n;i++)
                {
                                p= G ->adjlist[i].firstarc; //p指向第一条边
                                 if (p!=NULL )
                                                cout <<i<<":  " ;
                                 while (p!=NULL )
                                {
                                                cout<<(p->adjvex)<< "  " ;//输出终点
                                                p=p->nextarc;     //指向下一条边
                                }
                                cout<<endl;
                }
}


void ALGragh ::DFS( int v, int flag) //深度优先搜索 递归
{
                 if (flag )
                {
                                memset(visited,0, sizeof (visited));
                                 flag =0;
                }

                 if (v >=n || v<0)
                {
                                cout<< "error point!" ;
                                 return ;
                }
                visited[ v ]=1;
                cout<< v <<"  " ;
                 ArcNode *p=adjlist[v ].firstarc;
                 while (p!=NULL )
                {
                                 if (!visited[p->adjvex])
                                                DFS(p->adjvex, flag );
                                p=p->nextarc;
                }
}

void ALGragh ::DFS1( int v//深度优先搜索 非递归
{
                memset(visited,0, sizeof (visited));
                 if (v >=n || v<0)
                {
                                cout<< "error point!" ;
                                 return ;
                }
                 stack <ArcNode *> s;
                visited[ v ]=1;
                cout<< v <<"  " ;
                 ArcNode *q;
                s.push(adjlist[ v ].firstarc);
                 while (!s.empty())
                {
                                q=s.top(); //s.pop();
                                 while (q!=NULL )
                                {
                                                 if (!visited[q->adjvex])
                                                {
                                                                visited[q->adjvex]=1;
                                                                cout<<q->adjvex<< "  " ;      
                                                                s.push(adjlist[q->adjvex].firstarc); //定点进栈
                                                                 break ;
                                                }
                                                 else
                                                {
                                                                q=q->nextarc;        //与当前结点相连的边都访问了(即往该结点走不下去了)     该节点出栈
                                                                 if (q==NULL )
                                                                                s.pop();
                                                }
                                }
                }
}


void ALGragh ::BFS( int v//广度优先搜索
{
                memset(visited,0, sizeof (visited));
                 if (v >=n || v<0)
                {
                                cout<< "error point!" ;
                                 return ;
                }
                 queue <int > q;
                 ArcNode *p;
                q.push( v );
                visited[ v ]=1;
                cout<< v <<"  " ;
                 while (!q.empty())
                {
                                 v =q.front(); q.pop();
                                p=adjlist[ v ].firstarc;
                                 while (p!=NULL )
                                {
                                                 if (!visited[p->adjvex])
                                                {
                                                                visited[p->adjvex]=1;
                                                                cout<<p->adjvex<< "  " ;
                                                                q.push(p->adjvex);
                                                }
                                                p=p->nextarc;
                                }              
                }
}

main.cpp文件:

#include "graph.h"
int main()
{
                 ////////-------图的遍历算法----//////////
                 /*int A[100][6]={
                                {0,5,0,7,0,0},
                                {0,0,4,0,0,0},
                                {8,0,0,0,0,9},
                                {0,0,5,0,0,6},
                                {0,0,0,5,0,0},
                                {3,0,0,0,1,0}
                };*/
                 int A[100][10]={
                                0,1,1,1,0,0,0,0,0,0,
                                1,0,0,1,0,1,1,1,1,0,
                                0,1,0,1,1,1,0,0,0,0,
                                0,0,0,0,0,1,0,0,0,0,
                                0,1,1,1,0,1,0,0,0,0,
                                0,1,0,0,0,0,0,0,0,0,
                                0,1,1,1,0,0,0,1,1,0,
                                0,0,1,1,1,1,1,0,1,0,
                                0,0,1,1,0,0,0,0,0,0,
                                0,0,1,0,0,0,0,0,1,0
                };
                MGraph g(A,10,10);                                                              //图的邻接矩阵类型
                ALGragh G(A,10,10);                                                            //图的临界表类型
                g.DispMat(g);
                G.DispAdj(&G);
                G.DFS(0,1); cout<<endl;
                G.DFS1(0); cout<<endl;

graph.h文件:

#include "C++global.h"//图的数据结构
typedef int InfoType;
#define MAXV 100   //最大顶点个数

//------------------------------------//
//-----------用邻接矩阵存储-------------//
class VertexType     //顶点类型
{
private :
                 int no;      //顶点编号
                 InfoType info; //顶点的其他信息;
};
class MGraph     //图的定义
{
public :    
                 void DispMat(MGraph g);
                MGraph(){n=0;e=0;memset(edges,0, sizeof (edges));}
                MGraph( int A[100][10],int n, int e);
private :
                 int edges[MAXV ][ MAXV]; //邻接矩阵
                 int n,e;               //顶点数,弧数
                 VertexType vexs[MAXV ]; //图的邻接矩阵类型。
};


//------------------------------------//
//------------------------------------//
//------------用临界表存储-------------//
class VNode ;
class ArcNode             //弧结点结构类
{
                 friend class   ALGragh;
                 //friend class VNode;
public :
                ArcNode(){}
                ArcNode( ArcNode *next , int adj, int i)
                {              adjvex= adj ;            nextarc= next;        info= i ;    }
                
private :
                 int adjvex;         
                 ArcNode *nextarc;    //指向下一条弧的指针
                 InfoType info;       //弧先关信息,这里存放权值
};

class VNode {               //头结点类
                 //friend class ArcNode;
                 friend class   ALGragh;
private :
                 int data;              //顶点信息
                 ArcNode *firstarc;     //指向第一条弧
};

typedef VNode AdjList[ MAXV ]; //AdjList是临界表类型

class   ALGragh {     //图的临界表类型
public :
                ALGragh();
                ALGragh( int a[MAXV ][10], int n, int e );
                 void DispAdj(ALGragh *G);
                 void DFS(int v, int flag);
                 void DFS1(int v); //深度优先 非递归
                 void BFS(int v);
private :
                 AdjList adjlist;     //邻接表
                 int n,e;
};


输出: