本文共 748 字，大约阅读时间需要 2 分钟。

DFS,BFS

代码显示为输出连通集

算法时间复杂度:

采用邻接表存储图:DFS和BFS都为O(N+E)采用邻接矩阵存储:DFS和BFS都为O(N^2);

数据结构设计

/// @brief 顶点/// @param adjacencyList 邻接表struct vertex{    int id;    vector
   
     adjacencyList;};vector
    
      visited(N,false);vector
     
       vertexList(N);
     
    
   

DFS

void dfs(int s,vector
   
    &visited,vector
    
     &path,vector
     
      vertexList){    vector
      
        v = vertexList[s].adjacencyList;    for (int i=0; i
      
     
    
   

BFS

void bfs(int s,vector
   
    &visited,vector
    
     &path,vector
     
      vertexList){    queue
      
       q;    q.push(s);    while (!q.empty())     {        int cur = q.front();        q.pop();        vector
       
         v = vertexList[cur].adjacencyList;        for (int i=0; i
       
      
     
    
   

转载地址：http://cehji.baihongyu.com/