DFS算法，BFS算法遍历图

喜欢ヅ旅行 2022-05-14 23:05 262阅读 0赞

前提：所有图的实现我都只用了邻接矩阵进行图的存储

DFS算法遍历图

//图的遍历之深度优先搜索
    #include<iostream>
    #define MAX 1000
    #define TRUE 1
    #define ERROR 0
    using namespace std;
    
    class Graph
    {
    private:
    	int n;  //结点个数的平方
    	int m;  //节点的个数
    	int *graph;
    	int *visited;
    public:
    	Graph(int n1)
    	{
    		n=n1*n1;
    		m=n1;
    		graph=new int [n];
    		visited=new int [n1];
    	}
    	void Set_Data()
    	{
    		//memset(visited,0,sizeof(visited));//指针开辟的数组不能用这个函数初始化，只能对静态的数组初始化
    		cout<<"请输入图的关系矩阵,不可达或自身到自身的则为0，能到达的两点为1,请按这种方式输入关系矩阵:"<<endl;
    		int i,j;
    		for(i=0;i<m;i++)
    			for(j=0;j<m;j++)
    				cin>>graph[i*m+j];
    		for(i=0;i<m;i++)
    			visited[i]=0;
    	}
    	int dfs(int v,int s)
    	{
    		int w=0;
    		s++;
    		Output(v,s);
    		visited[v]=1;
    		for(;w<m;w++)
    			if(!visited[w]&&graph[v*m+w]==1)s=dfs(w,s);
    			return s;
    	}
    	void Output(int v,int s)
    	{
    		if(s==m)cout<<v;
    		else
    		cout<<v<<"->";
    	}
    	void dfs_Graph()
    	{
    		int i,s=0;
    		for(i=0;i<m;i++)
    			if(!visited[i])s=dfs(i,s);
    	}
    };
    int main()
    {
    	int n;
    	cout<<"输入图的顶点数为:";
    	cin>>n;
    	Graph a(n);
    	a.Set_Data();
    	cout<<"深度优先搜索的序列为:";
    	a.dfs_Graph();
    	cout<<endl;
    	return 0;
    }

BFS算法遍历图（用队列实现，我用的是循环队列）

#include<iostream>
    #define Length 10
    #define ERROR 0
    #define TRUE 1
    using namespace std;
    
    class XU_DL
    {
    private:
    	int *item;
    	int front;
    	int rear;
    	int maxlength;
    public:
    	XU_DL(int length=Length) //对队列的初始化
    	{
    		if(length<Length)length=Length;
    		item=new int [length];
    		maxlength=length;
    		front=0;
    		rear=0;
    	}
    	~XU_DL()  //析构函数销毁队列
    	{
    		delete [] item;
    	}
    	void ClearXU_DL()  //清空队列
    	{
    		front=rear=0;
    	}
    	int Getlength() //获得长度
    	{
    		if(rear==front) 	return ERROR;
    		return ((rear-front)+maxlength)%maxlength;
    	}
    	int Inser(int e)  //插入数据e
    	{
    		if((rear+1)%maxlength==front)return ERROR;  //队满时的判断语句
    		rear=(rear+1)%maxlength;
    		item[rear]=e;
    		return TRUE;
    	}
    	int Gethand()  //获得队头元素,并删除该数
    	{
    		int e;
    		if(rear==front)return ERROR;  //队列为空事的判断语句
    		e=item[(front+1)%maxlength];
    		front++;
    		return e;
    	}
    	int Deletedate(int e)  //获取数据并删除该数
    	{
    		if(rear==front)return ERROR; //队列为空
    		front=(front+1)%maxlength;
    		e=item[front];
    		return TRUE;
    	}
    	void Output()
    	{
    		if(front==rear){cout<<"The queue is null!"<<endl;return;}
    		cout<<"The queue length is :"<<Getlength()<<endl;
    		cout<<"The queue's content is :";
    		for(int i=1;i<Getlength();i++)
    			cout<<item[i]<<"->";
    		cout<<item[i]<<endl;
    	}
    	int Output1(int s,int m)
    	{
    		int temp;
    		temp=Gethand();
    		if(s==m)cout<<temp;
    		else
    			cout<<temp<<"->";
    		return temp;
    	}
    };
    class Graph:public XU_DL 
    {
    private:
    	int n;  //结点个数的平方
    	int m;  //节点的个数
    	int *graph;
    	int *visited;
    public:
    	Graph(int n1)
    	{
    		n=n1*n1;
    		m=n1;
    		graph=new int [n];
    		visited=new int [n1];
    	}
    	void Set_Data()
    	{
    		//memset(visited,0,sizeof(visited));
    		cout<<"请输入图的关系矩阵,不可达或自身到自身的则为0，能到达的两点为1,请按这种方式输入关系矩阵:"<<endl;
    		int i,j;
    		for(i=0;i<m;i++)
    			for(j=0;j<m;j++)
    				cin>>graph[i*m+j];
    		for(i=0;i<m;i++)
    			visited[i]=0;
    	}
    	void bfs(int v)   //把以某个点的所有相邻的点都包含进去了
    	{
    		int i;bool frag(false);
    		ClearXU_DL();
    		frag=true;
    		while(frag)
    		{
    			Inser(v);
    			visited[v]=1;
    			for(i=v;i<m;i++)
    				if((visited[i]==0)&&graph[v*m+i]==1){Inser(i);visited[i]=1;}
    			for(i=0;i<m;i++)
    			{
    				if(visited[i]==1)frag=false;
    				else
    				{
    					frag=true;
    					v=i;
    					break;
    				}
    			}
    		}
    		Output();
    	}
    	void bfs1(int v)  //front的值会改变
    	{
    		int i,j,s=0;
    		bool frag(false);
    		ClearXU_DL();
    		frag=true;
    		while(frag)
    		{
    			Inser(v);
    			visited[v]=1;
    			while(Getlength()!=0)
    			{
    				s++;
    				i=Output1(s,m);
    				for(j=0;j<m;j++)
    					if((visited[j]==0)&&graph[i*m+j]==1)
    					{
    						Inser(j);
    						visited[j]=1;
    					}
    			}
    			for(i=0;i<m;i++)
    			{
    				if(visited[i]==1)frag=false;
    				else
    				{
    					frag=true;
    					v=i;
    					break;
    				}
    			}
    		}
    		cout<<endl;
    	}
    };
    int main()
    {	int n;
    	cout<<"输入图的顶点数为:";
    	cin>>n;
    	Graph a(n);
    	a.Set_Data();
    	cout<<"广度优先搜索的序列为:";
    	a.bfs1(0);
    	return 0;
    }