🍠Python种群邻接矩阵彗星风筝进化图算法

Python | 生物 | 种群 | 进化图 | 图论 | 概率 | 算法 | 莫兰生死过程

Python种群邻接矩阵彗星风筝进化图算法 | 亚图跨际viadean on Notion

🏈指点迷津 | Brief

🎯要点

🎯生成种群进化时间和概率数据 | 🎯力导向算法绘图 | 🎯彗星风筝图算法 | 🎯绕行图算法 | 🎯广义星形图算法 | 🎯耦合星图算法 | 🎯启发式基因算法

📜进化图用例

📜Python和C++骨髓细胞进化解析数学模型

🍪语言内容分比

🍇Python连通无向图

无向图的特征：

• 无向图中的边本质上是双向的。

• 在无向图中，不存在“父”或“子”顶点的概念，因为没有到边的方向。

• 无向图可能包含环，环是将顶点连接到自身的边。

• 每个顶点的度数与与其连接的边的总数相同。

无向图的应用：

• 社交网络：无向图用于建模社交网络，其中人们由节点表示，他们之间的连接由边表示。

• 交通流优化：交通流优化使用无向图来模拟道路网络上的车辆流量。图的顶点表示交叉路口或路段，边表示它们之间的连接。该图可用于优化交通流量和规划交通基础设施。

• 网站分析：无向图可用于分析互联网上网页之间的链接。每个网页由一个顶点表示，网页之间的每个链接由一条边表示。

给定一个无向图，任务是逐行打印所有连接的分量。

输出

 0 1 2
 3 4

算法是：

• 将所有顶点初始化为未访问过。

• 对每个顶点 v 执行以下操作：

  • 如果之前没有访问过v，则调用深度优先遍历。并打印换行符以在新行中打印每个分量

    • 将 v 标记为已访问并打印 v。

    • 对于v的每一个相邻的u，如果u没有被访问过，则递归调用深度优先遍历。

代码实现：

 class Graph:
 ​
     def __init__(self, V):
         self.V = V
         self.adj = [[] for i in range(V)]
 ​
     def DFSUtil(self, temp, v, visited):
         visited[v] = True
         temp.append(v)
         for i in self.adj[v]:
             if visited[i] == False:
                 temp = self.DFSUtil(temp, i, visited)
         return temp
 ​
     def addEdge(self, v, w):
         self.adj[v].append(w)
         self.adj[w].append(v)
 ​
     def connectedComponents(self):
         visited = []
         cc = []
         for i in range(self.V):
             visited.append(False)
         for v in range(self.V):
             if visited[v] == False:
                 temp = []
                 cc.append(self.DFSUtil(temp, v, visited))
         return cc
 ​
 if __name__ == "__main__":
 ​
     g = Graph(5)
     g.addEdge(1, 0)
     g.addEdge(2, 1)
     g.addEdge(3, 4)
     cc = g.connectedComponents()
     print("Following are connected components")
     print(cc)
 ​

输出：

 Following are connected components 
 0 1 2 
 3 4 

使用不相交集并集算法：

• 声明一个大小为 V 的数组 arr[]，其中 V 是节点总数。

• 对于数组 arr[] 的每个索引 i，该值表示第 i 个顶点的父节点是谁。

• 将每个节点初始化为其自身的父节点，然后在将它们添加在一起时相应地更改其父节点。

• 从0到V遍历节点：

  • 对于作为其父节点的每个节点，启动该算法。

  • 打印该不相交集合的节点，因为它们属于一个分量。

 import collections
 ​
 class ConnectedComponents:
 def merge(self, parent, x):
     if parent[x] == x:
     return x
     return self.merge(parent, parent[x])
 ​
 def connectedComponents(self, n, edges):
 ​
     parent = [i for i in range(n)]
     for x in edges:
     parent[self.merge(parent, x[0])] = self.merge(parent, x[1])
     ans = 0
 ​
     for i in range(n):
     if parent[i] == i:
         ans += 1
 ​
     for i in range(n):
     parent[i] = self.merge(parent, parent[i])
     m = collections.defaultdict(list)
     for i in range(n):
     m[parent[i]].append(i)
     for it in m.items():
     l = it[1]
     print(" ".join([str(x) for x in l]))
     
     return ans
 ​
 if __name__ == "__main__":
 n = 5
 edges = [[0, 1], [2, 1], [3, 4]]
 print("Following are connected components:")
 ans = ConnectedComponents().connectedComponents(n, edges)

输出：

 Following are connected components:
 0 1 2 
 3 4