檢查所有瓷磚是否連接

Question

嗨！我有一個有趣的問題。

我已經在HTML畫布上繪製的一系列六邊形的（忽略點）

對於每個六邊形我有它的X和其中心的y座標，這就是我如何識別它們。

我存儲在數組中，其中我存儲六邊形

function Hexagon() 
    { 
     this.shape 
     this.x 
     this.y 
    } 

六邊形稱爲六邊形我具有與鑑於這種給定的六邊形

function get_adjacent_hexagons(hexagon) 
{ 
    var x = hexagon.x 
    var y = hexagon.y 
    var adjacents = [] 
    for(var i=0; i<editor_hexagons.length; i++) 
    { 
     if(editor_hexagons[i].x === x && editor_hexagons[i].y == y - (2*s)) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
     if(editor_hexagons[i].x === x && editor_hexagons[i].y == y + (2*s)) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
     if(editor_hexagons[i].x === x - (s*1.5) && editor_hexagons[i].y == y - s) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
     if(editor_hexagons[i].x === x - (s*1.5) && editor_hexagons[i].y == y + s) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
     if(editor_hexagons[i].x === x + (s*1.5) && editor_hexagons[i].y == y - s) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
     if(editor_hexagons[i].x === x + (s*1.5) && editor_hexagons[i].y == y + s) 
     { 
      adjacents.push(editor_hexagons[i]) 
     } 
    } 
    return adjacents 
} 

的所有相鄰六邊形返回一個對象的函數信息，是否有可能做一個算法來檢查是否所有的六邊形都連接

這就是說，如果沒有六邊形或一組六邊形？

例如，在圖片中提供了它們都已連接。

----- -----編輯

這似乎是工作

function check_connection() 
{ 
    visited = [] 
    visit_hexagon(hexagons[0]) 
} 

function visit_hexagon(hexagon) 
{ 
    var not_visited = true 
    for(var i=0; i<visited.length; i++) 
    { 
     if(visited[i] === hexagon) 
     { 
      not_visited = false 
      break 
     } 
    } 
    if(not_visited) 
    { 
     visited.push(hexagon) 
     var adjacents = get_adjacent_hexagons(hexagon) 
     for(var i=0; i<adjacents.length; i++) 
     { 
      visit_hexagon(adjacents[i]) 
     } 
    } 
} 

Answer 1

首先將您的節點（六邊形）組織爲一個圖形結構，其中每個節點都具有對其所連接的其他節點的引用。將所有節點標記爲「未訪問」。從任意節點開始，執行breadth或depth第一次搜索，標記您發現爲「已訪問」的每個節點。如果在此之後有任何未標記爲「已訪問」的節點，則圖形沒有完全連接。

Answer 2

是。由於您可以找到相鄰的六邊形，因此可以在地圖上創建所有六邊形的圖形。然後，您可以簡單地從圖中的單個節點開始執行廣度優先搜索，然後檢查搜索結束後是否找到了所有節點。詳細請參閱：https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Computational_aspects