Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

graph - Algorithm to find the total number of connected sets in a matrix

i wanted to know which algorithm should i apply here. Would a DFS do?

Given a 2–d matrix. Find the total number of connected sets in that matrix.

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions (i.e. N, W, E, S, NE, NW, SE, SW direction). A cell is not a neighbor of itself.

For example:

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

number of connected sets is 3

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

number of connected set is 9.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I don't think you will need to think of it as a general graph problem and apply any algorithm such as BFS or DFS.

You will need to do three scans of the matrix.

scan 1:

start from the top

  1. give every number each 1 with 1..n, in you example the first row would after that step would look like

    1 0 0 2

  2. go to the next line and for every 1 in the row check if the neighbor to your left is non-0
    • if non-0 take on the value to the left
    • if 0 check for non-0 neighbors in the previous line and take on the value of the left most one
    • if all of those are 0 that simply add 1 to the maximum number given so far
  3. repeat 2 until last line has been processed

and your example should look like follows

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

scan 2:

start from the bottom check if each neighbor has the same number as the left most neighbor as well as the same number as the neighbor in the row below it

basically if you have a matrix like this

1 0 2

1 0 2

0 1 0

to check ensure that a set has really the same number

scan 3:

count the number of unique non-0 entries in the matrix


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...