最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 【每日一题】一组相连的1形成一个岛(图)

    c语言无向图连通分量_c语言 无重复随机数_c语言math.h 无

    给定一个布尔矩阵,求岛屿的数量。一组连接的 1 形成一个岛。例如,以下矩阵包含 5 个岛屿:

    c语言 无重复随机数_c语言math.h 无_c语言无向图连通分量

    在进入问题之前,让我们了解什么是连接组件。无向图的连通分量是一个子图,其中每两个顶点通过一条路径相互连接,并且不与子图外的其他顶点相连。

    所有顶点相互连接的图只有一个连通分量,由整个图组成。这种只有一个连通分量的图称为强连通图。

    通过在每个组件上应用 DFS() 可以轻松解决此问题。在每个 DFS() 调用中,都会访问一个组件或一个子图。我们将在下一个未访问的组件上调用 DFS。对 DFS() 的调用次数给出了连接组件的数量。也可以使用 BFS。

    什么是岛?

    一组连接的 1 形成一个岛。例如,下面的矩阵包含 4 个岛

    二维矩阵中的一个单元可以连接到 8 个相邻的单元。所以不像标准的 DFS() 我们递归地调用所有相邻的顶点c语言无向图连通分量,这里我们只能递归地调用 8 个相邻的顶点。我们会跟踪已访问过的 1c语言无向图连通分量,以便不再访问它们。

    c语言 无重复随机数_c语言math.h 无_c语言无向图连通分量

    参考:

    源代码:

    using System;
    using System.Text;
    using System.Collections;
    using System.Collections.Generic;
    namespace Legalsoft.Truffer.Algorithm
    {
    	public partial class Graph
    	{
    		private bool IsSafe(int row, int col, bool[,] visited)
    		{
    			int ROW = Matrix.GetLength(0);
    			int COL = Matrix.GetLength(1);
    			return (row >= 0) && (row = 0) && (col < COL) && (M[row, col] == 1 && !visited[row, col]);
    		}
    		private void DFS_Islands(int row, int col, bool[,] visited)
    		{
    			int ROW = Matrix.GetLength(0);
    			int COL = Matrix.GetLength(1);
    			int[] rowNbr = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
    			int[] colNbr = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
    			visited[row, col] = true;
    			for (int k = 0; k < 8; ++k)
    			{
    				if (IsSafe(row + rowNbr[k], col + colNbr[k], visited))
    				{
    					DFS_Islands(row + rowNbr[k], col + colNbr[k], visited);
    				}
    			}
    		}
    		public int Count_Islands()//int[,] M)
    		{
    			int ROW = Matrix.GetLength(0);
    			int COL = Matrix.GetLength(1);
    			bool[,] visited = new bool[ROW, COL];
    			int count = 0;
    			for (int i = 0; i < ROW; ++i)
    			{
    				for (int j = 0; j < COL; ++j)
    				{
    					if (Matrix[i, j] == 1 && !visited[i, j])
    					{
    						DFS_Islands(i, j, visited);
    						++count;
    					}
    				}
    			}
    			return count;
    		}
    	}
    	public static partial class GraphDrives
    	{
    		public static string Count_Islands()
    		{
    			int[,] M = new int[,] {
    				{ 1, 1, 0, 0, 0 },
    				{ 0, 1, 0, 0, 1 },
    				{ 1, 0, 0, 1, 1 },
    				{ 0, 0, 0, 0, 0 },
    				{ 1, 0, 1, 0, 1 }
    			};
    			Graph g = new Graph(M);
    			g.AdjacencyMatrix();
    			return ("Number of islands is: " + g.Count_Islands());
    		}
    	}
    }
    

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 【每日一题】一组相连的1形成一个岛(图)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论