📄 flood fill.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0060)http://ace.delos.com/usacotext/s=1.2.1.0/a=mDx8aVs8FYS/flood -->
<HTML><HEAD><TITLE>Flood Fill</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META content="MSHTML 5.00.3502.5390" name=GENERATOR></HEAD>
<BODY background="flood fill.files/bg3.jpg"><IMG height=118
src="flood fill.files/cow1.jpg" width=742>
<CENTER><B><FONT size=4>Flood Fill</FONT></B></CENTER>
<H4>Sample Problem: Connected Fields</H4>
<P>Farmer John's fields are broken into fields, with paths between some of them.
Unfortunately, some fields are not reachable from other fields via the paths.
<P>Define a <I>superfield</I> is a collection of fields that are all reachable
from each other. Calculate the number of superfields.
<H4>The Abstraction</H4>
<P>Given: a undirected graph
<P>The <I>component</I> of a graph is a maximal-sized (though not necessarily
maximum) subgraph which is connected.
<P>Calculate the component of the graph. <BR><IMG
src="flood fill.files/flood1.gif"><BR>This graph has three components: {1,4,8},
{2,5,6,7,9}, and {3}.
<H4>The Algorithm: Flood Fill</H4>
<P>Flood fill can be performed three basic ways: depth-first, breadth-first, and
breadth-first scanning. The basic idea is to find some node which has not been
assigned to a component and to calculate the component which contains. The
question is how to calculate the component.
<P>In the depth-first formulation, the algorithm looks at each step through all
of the neighbors of the current node, and, for those that have not been assigned
to a component yet, assigns them to this component and recurses on them.
<P>In the breadth-first formulation, instead of recursing on the newly assigned
nodes, they are added to a queue.
<P>In the breadth-first scanning formulation, every node has two values:
component and visited. When calculating the component, the algorithm goes
through all of the nodes that have been assigned to that component but not
visited yet, and assigns their neighbors to the current component.
<P>The depth-first formulation is the easiest to code and debug, but can require
a stack as big as the original graph. For explicit graphs, this is not so bad,
but for implicit graphs, such as the problem presented has, the numbers of nodes
can be very large.
<P>The breadth-formulation does a little better, as the queue is much more
efficient than the run-time stack is, but can still run into the same problem.
Both the depth-first and breadth-first formulations run in N + M time, where N
is the number of vertices and M is the number of edges.
<P>The breadth-first scanning formulation, however, requires very little extra
space. In fact, being a little tricky, it requires no extra space. However, it
is slower, requiring up to N*N + M time, where N is the number of vertices in
the graph.
<H4>Pseudocode for Breadth-First Scanning</H4>
<P>This code uses a trick to not use extra space, marking nodes to be visited as
in component -2 and actually assigning them to the current component when they
are actually visited. <BR><TT><FONT
size=2><BR># component(i) denotes the<BR># component that node i is in<BR> 1 function flood_fill(new_component) <BR><BR> 2 do<BR> 3 num_visited = 0<BR> 4 for all nodes i<BR> 5 if component(i) = -2<BR> 6 num_visited = num_visited + 1<BR> 7 component(i) = new_component<BR> 8 for all neighbors j of node i<BR> 9 if component(j) = nil<BR>10 component(j) = -2<BR>11 until num_visited = 0 <BR><BR>12 function find_components <BR><BR>13 num_components = 0<BR>14 for all nodes i<BR>15 component(node i) = nil<BR>16 for all nodes i<BR>17 if component(node i) is nil<BR>18 num_components =<BR> num_components + 1<BR>19 component(i) = -2<BR>20 flood_fill(component<BR> num_components)<BR></FONT></TT>
<P>Running time of this algorithm is O(<I>N <SUP>2</SUP></I>), where <I>N</I> is
the numbers of nodes. Every edge is traversed twice (once for each end-point),
and each node is only marked once.
<H4>Execution Example</H4>
<P>Consider the graph from above. <BR><IMG
src="flood fill.files/flood1.gif"><BR>
<P>The algorithm starts with all nodes assigned to no component.
<P>Going through the nodes in order first node not assigned to any component yet
is vertex 1. Start a new component (component 1) for that node, and set the
component of node 1 to -2 (any nodes not shown are unassigned).
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle><B>1</B></TD>
<TD align=middle><B>-2</B></TD></TR></TBODY></TABLE></CENTER>
<P>Now, in the <TT>flood_fill</TT> code, the first time through the <TT>do</TT>
loop, it finds the node 1 is assigned to component -2. Thus, it reassigns it to
component 1, signifying that it has been visited, and then assigns its neighbors
(node 4) to component -2.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle><B>1</B></TD>
<TD align=middle><B>1</B></TD></TR>
<TR>
<TD align=middle><B>4</B></TD>
<TD align=middle><B>-2</B></TD></TR></TBODY></TABLE></CENTER>
<P>As the loop through all the nodes continues, it finds that node 4 is also
assigned to component -2, and processes it appropriately as well.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>4</B></TD>
<TD align=middle><B>1</B></TD></TR>
<TR>
<TD align=middle><B>8</B></TD>
<TD align=middle><B>-2</B></TD></TR></TBODY></TABLE></CENTER>
<P>Node 8 is the next to be processed.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>8</B></TD>
<TD align=middle><B>1</B></TD></TR></TBODY></TABLE></CENTER>
<P>Now, the <TT>for</TT> loop continues, and finds no more nodes that have not
been assigned yet. Since the <TT>until</TT> clause is not satisfied (
<TT>num_visited</TT> = 3), it tries again. This time, no nodes are found, so the
function exits and component 1 is complete.
<P>The search for unassigned nodes continues, finding node 2. A new component
(component 2) is allocated, node 2 is marked as in component -2, and
<TT>flood_fill</TT> is called.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>2</B></TD>
<TD align=middle><B>-2</B></TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>8</TD>
<TD align=middle>1</TD></TR></TBODY></TABLE></CENTER>
<P>Node 2 is found as marked in component -2, and is processed.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>2</TD>
<TD align=middle>2</TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>7</B></TD>
<TD align=middle><B>-2</B></TD></TR>
<TR>
<TD align=middle>8</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>9</B></TD>
<TD align=middle><B>-2</B></TD></TR></TBODY></TABLE></CENTER>
<P>Next, node 7 is processed.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>2</TD>
<TD align=middle>2</TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle><B>5</B></TD>
<TD align=middle><B>-2</B></TD></TR>
<TR>
<TD align=middle><B>7</B></TD>
<TD align=middle><B>2</B></TD></TR>
<TR>
<TD align=middle>8</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>9</TD>
<TD align=middle>-2</TD></TR></TBODY></TABLE></CENTER>
<P>Then node 9 is processed.
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD align=middle>Node</TD>
<TD align=middle>Component</TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>2</TD>
<TD align=middle>2</TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>1</TD></TR>
<TR>
<TD align=middle>5</TD>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -