首页 > 代码库 > 图的深度优先搜索 递归和非递归实现 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;
};
输出：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。