BFS backtracking - случай изолированных кластеров - PullRequest
Новая
       35

BFS backtracking - случай изолированных кластеров

0 голосов
/ 04 мая 2020

Я написал псевдокод для BFS для возврата, чтобы увидеть, является ли график двумя раскрашиваемыми или нет. Теперь я хочу включить случай, когда граф может быть не связан, то есть, что могут быть изолированные кластеры (в этом случае студентов). Каков наилучший способ добиться этого? Я думаю, что мне нужно l oop по каждому компоненту на графике, но я не знаю, правильно ли это и как это должно быть записано в коде 

# node = student
# edges = relation
function insert_edge(adj[], node i,node j, visited, color) 
   adj[node i] add node j
   adj[node j] add node i 

function bipartite_graph(adj[], node j,visited, color)
   for each node i in adj[node j]
      if node i not visited 
         mark node i as visited  
         color of i != color of j
         if not bipartite_graph (adj, node i, visited, color)
            return false 
       else if color of i == color of j
          return false 
    return true

function main()
   Initialize number of vertices
   Initialize vector adjacency list adj
   Initialize vector visited
   Initialize vector color
   Insert edges to graph

   Mark source node with color
   Mark source node as visited

   if bipartite_graph (adj[], node j,visited, color)
      return "Yes"
   else do 
      return "No"
...