単一始点最短経路 (重みなし)
2006.04.26 22:51 グラフ 探索

001 #define MAX 1000 002 int size; 003 int adjMatrix[MAX][MAX]; // graph structure 004 005 void breadthFirstSearch( int source ){ 006 queue< int > Q; 007 bool visited[MAX]; 008 int dist[MAX]; 009 int pi[MAX]; 010 011 for ( int i = 0; i < size; i++ ) { 012 visited[i] = false; 013 dist[i] = INT_MAX; 014 } 015 int currentNode = source; 016 017 Q.push( currentNode ); 018 visited[currentNode] = true; 019 dist[currentNode] = 0; 020 pi[currentNode] = -1; 021 022 while ( !Q.empty() ){ 023 currentNode = Q.front(), Q.pop(); 024 025 for ( int nextNode = 0; nextNode < size; nextNode++ ){ 026 if ( !adjMatrix[currentNode][nextNode] ) continue; 027 if ( !visited[nextNode] ){ 028 visited[nextNode] = true; 029 dist[nextNode] = dist[currentNode] + 1; 030 pi[nextNode] = currentNode; 031 Q.push( nextNode ); 032 } 033 } 034 } 035 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |