C++笔记2 | 图的优先遍历

图的深度优先遍历

算法思想：
第一步:顶点vi出发，访问，标记，找邻接顶点vi1
第二步:vi1出发，DFS访问和它邻接的所有顶点
第三步:转到第一步 ，直到所有和vi邻接的顶点全部被访问
第四步:继续选取图中其他未被访问顶点作为起始顶点，转第一步

　void dfs(int i)                           //图用数组模拟邻接表存储，访问点i
　{
　　 visited[i] = true;                           //标记为已访问
　　 for (int j = 1; j <= num[i]; j++)    //遍历与i相关联的所有未访问过的顶点
　　    if (!visited[g[i][j]])
　　       dfs(g[i][j]); 
　}

int main()
{
       ……
       memset(visited,false,sizeof(visited));
       for (int i = 1; i <= n; i++)                  //每一个点都作为起点尝试访问，因为不是从任何
                                                           //一点开始都能遍历整个图的，例如下图。
             if (!visited[i])
                 dfs(i);
       ……
       return 0;
}

以3为起点根本不能遍历整个图

图的广度优先遍历

算法思想：
第一步:顶点vi出发，访问
第二步:访问vi的所有邻接顶点
第三步:转第一步，分别以vi邻接的顶点进行遍历
第四步:继续选取图中未被访问顶点作为起始顶点，转第一步，直到全部遍历全部顶点

void bfs(int i)
{  
	int j,k,open,closed;
	memset(q,0,sizeof(q));
	open=0;closed=1;q[1]=i; 
	cout<<i<<" ";
	 visited[i]=1; 	
	 while(open<closed){
	           open++;k=q[open]; 
	           for(j=1;j<=n;j++)		 				    if((a[k][j]==1)&&(visited[j]==0)){
		         visited[j]=1; 
		         closed++;  
		         q[closed]=j;
		    }
   	  }
}