图的深度优先搜索与广度优先搜索

刺骨的言语ヽ痛彻心扉 2022-08-02 11:57 243阅读 0赞

无向图的深度优先搜索与广度优先搜索

#include "stdafx.h"
    #include<vector>
    #include<iostream>
    
    using namespace std;
    
    #define N 9
    typedef struct{
    	int vexnum, arcnum;
    	char vexs[N];
    	int matirx[N][N];
    }graph;
    
    graph g;
    int a[N] = { 0 };
    
    // 初始化图数据  
    // 0---1---2---3---4---5---6---7---8---  
    // A---B---C---D---E---F---G---H---I---  
    void initiate_graph()
    {
    	// A-B, A-D, A-E
    	g.matirx[0][1] = 1;
    	g.matirx[1][0] = 1;
    	g.matirx[0][3] = 1;
    	g.matirx[3][0] = 1;
    	g.matirx[0][4] = 1;
    	g.matirx[4][0] = 1;
    	// B-C  
    	g.matirx[1][2] = 1;
    	g.matirx[2][1] = 1;
    	// C-F  
    	g.matirx[2][5] = 1;
    	g.matirx[5][2] = 1;
    	// D-E, D-G  
    	g.matirx[3][4] = 1;
    	g.matirx[4][3] = 1;
    	g.matirx[3][6] = 1;
    	g.matirx[6][3] = 1;
    	// E-F, E-H  
    	g.matirx[4][5] = 1;
    	g.matirx[5][4] = 1;
    	g.matirx[4][7] = 1;
    	g.matirx[7][4] = 1;
    	// F-H, F-I  
    	g.matirx[5][7] = 1;
    	g.matirx[7][5] = 1;
    	g.matirx[5][8] = 1;
    	g.matirx[8][5] = 1;
    	// G-H  
    	g.matirx[6][7] = 1;
    	g.matirx[7][6] = 1;
    	// H-I  
    	g.matirx[7][8] = 1;
    	g.matirx[8][7] = 1;
    
    }
    
    //深度优先搜寻，递归实现
    void DFS(int k)
    {
    	a[k] = 1;//标记为已经访问过
    	int mm = 0;
    	while (mm < N)
    	{
    		if (g.matirx[k][mm] == 1)
    		{
    			if (a[mm] != 1)
    			{
    				cout << "[" << k << "]" << "[" << mm << "]" << endl;
    				DFS(mm);
    			}
    		}
    		mm++;
    	}
    }
    
    
    
    void BFS()
    {
    	vector<int>vec;
    	vector<int>aa;
    	int k = 0;
    	vec.push_back(0);
    	a[0] = 1;
    	while (vec.size() != 0)
    	{
    		while (k < vec.size())
    		{
    			cout << vec[k] << endl;
    			int mm = 0;
    			//a[vec[k]] = 1;
    			while (mm < N)
    			{
    				if (g.matirx[vec[k]][mm] == 1)
    				{
    					if (a[mm] != 1)
    					{
    						aa.push_back(mm);
    						a[mm] = 1;
    					}
    				}
    				mm++;
    			}
    			k++;
    		}
    		vec = aa;
    		k = 0;
    		aa.clear();
    	}
    
    }
    
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	initiate_graph();
    	//DFS(0);
    	BFS();
    	system("pause");
    	return 0;
    }