第六章部分例题双向bfs邻接表和邻接矩阵实现-白红宇

第六章部分例题双向bfs邻接表和邻接矩阵实现

阅读量：5255 次

发布时间：2019-06-14

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

Idealpath 双向bfs输出颜色,邻接矩阵实现

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
           6 #include 
          
            7 8 using namespace std; 9 10 const int maxn=10000; 11 const int inf=1000000; 12 int G[maxn][maxn]; 13 int d[maxn]; 14 int vis[maxn]; 15 queue
           
             q; 16 map
            
              ma; 17 int path[maxn]; 18 int m,n; 19 20 void init() 21 { 22 for(int i=0;i
             
              >l1>>l2>>rgb; 26 27 //cout<
              
               <<" "<
               
                <
                
                 0) 49 if(!vis[i]) 50 { 51 d[i]=d[node]+1; 52 53 q.push(i); 54 vis[i]=1; 55 } 56 } 57 58 } 59 60 61 void p_bfs(int dst) 62 { 63 memset(vis,0,sizeof(vis)); 64 65 q.push(1); 66 67 while(!q.empty()) 68 { 69 int node=q.front(); 70 q.pop(); 71 72 if(node==dst) break; 73 74 for(int i=1;i<=n;i++) 75 if(G[node][i]>0) 76 if(d[i]==d[node]-1) 77 { 78 int index=d[1]-d[node]; 79 if(path[index]==0) path[index]=G[node][i]; 80 else path[index]=min(path[index],G[node][i]); 81 82 q.push(i); 83 } 84 } 85 86 for(int i=0;i
                 
                  >n; 96 cin>>m; 97 98 //cout<<"m:"<
                  
                   <<" "<<"n:"<
                   
                    <
                    
                     >j;104 105 bfs(j);106 107 //printf("d1:%d d2:%d d3:%d d4:%d d5:%d\n",d[1],d[2],d[3],d[4],d[5]);108 109 //printf("G[5][2]=%d G[5][1]=%d G[4][1]=%d G[2][1]=%d G[2][3]=%d G[1][3]=%d\n",G[5][2],G[5][1],G[4][1],G[2][1],G[2][3],G[1][3]);110 111 p_bfs(j);112 113 114 printf("\n");115 116 return 0;117 }

邻接表实现最短距离

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 8 using namespace std; 9 10 const int maxn=100000+10; 11 const int inf=1000000; 12 vector
           
             v; 13 int d[maxn]; 14 int vis[maxn]; 15 queue
            
              q; 16 vector
             
               G[maxn]; 17 int m,n; 18 19 void init() 20 { 21 for(int i=1;i<=n;i++) 22 G[i].clear(); 23 24 for(int i=0;i
              
               >l1>>l2; 28 29 //cout<
               
                <<" "<
                
                 <
                 
                  >n; 99 cin>>m;100 101 103 init();104 105 int j;106 cin>>j;107 108 bfs(j);113 114 p_bfs(j);115 116 117 printf("\n");118 119 return 0;120 }