[알고리즘] graph cycle 여부 판단 알고리즘 (undirected 용)

[알고리즘] graph cycle 여부 판단 알고리즘 (undirected 용)

 

 

bool graph_check_cycle_for_undirected(     item_t *items,     uint32 n,     uint32 start_idx,     graph_vertex_pair &min_pair     ) {     bool is_cycle = false;     uint32 j;     queue<long> que;     map<long, long> que_map;     std::map<long, long>::iterator it;       uint32 pos, distance;     adj_node_t *adj_node;     list_node_t *node;       min_pair.start_vertex = min_pair.dest_vertex = 0;     min_pair.weight = GT_MAX_INT_VAL;       for (j = 0; j < n; j++) {         items[j].visited  = false;         items[j].distance = 0;     }       que.push(start_idx);     items[start_idx].distance = 0;     que_map.insert(std::pair<long, long>(start_idx, start_idx));       while (!que.empty()) {         j = que.front();         que.pop();         que_map.erase(j);           distance = items[j].distance;         items[j].visited = true;           if (RET_TYPE_FAILURE == items[j].adj_list->get_head_position(&pos))             continue;           while (1) {             node = items[j].adj_list->get_next(&pos);             if (NULL == node) break;               adj_node = (adj_node_t *)node->data;             int k = item_find_slot(items, adj_node->vertex->name, n);               if (false == items[k].visited) {                 items[k].distance = distance + 1;                   if (min_pair.weight > adj_node->edge.getWeight())                     _graph_set_pair(min_pair, j, k, adj_node->edge.getWeight());                   it = que_map.find(k);                 if (it != que_map.end()) {                     is_cycle = true;                 }                   que.push(k);                 que_map.insert(std::pair<long, long>(k, k));             }         }     }   return is_cycle; }