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

Python | 生物 | 种群 | 进化图[^1] | 图论 | 概率 | 算法 | 莫兰生死过程[^2]

{% embed url="https://viadean.notion.site/Python-880edcbeba7d407aa55f3035f42ff4a4" %}

{% content-ref url="../zhi-dian-mi-jin-brief" %}
[zhi-dian-mi-jin-brief](../zhi-dian-mi-jin-brief)
{% endcontent-ref %}

### 🎯要点

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

### 📜进化图用例

📜[Python和C++骨髓细胞进化解析数学模型](python-he-c++-gu-sui-xi-bao-jin-hua-jie-xi-shu-xue-mo-xing)

### 🍪语言内容分比

{% @mermaid/diagram content="pie title 语言分比
 "Python":90
 "Shell":20
 "C":10" %}

{% @mermaid/diagram content="pie title 内容分比
 "生物基因":90
 "算法":30
 "图论":40
 "无向、无权重图":50
 "种群进化":10
 "数学概率":10" %}

### 🍇Python连通无向图

无向图的特征：

* 无向图中的边本质上是双向的。
* 在无向图中，不存在“父”或“子”顶点的概念，因为没有到边的方向。
* 无向图可能包含环，环是将顶点连接到自身的边。
* 每个顶点的度数与与其连接的边的总数相同。

{% @mermaid/diagram content="flowchart LR
A((1))---B((0))---C((3))---D((4))
A---E((2))---B" %}

无向图的应用：

* 社交网络：无向图用于建模社交网络，其中人们由节点表示，他们之间的连接由边表示。
* 交通流优化：交通流优化使用无向图来模拟道路网络上的车辆流量。图的顶点表示交叉路口或路段，边表示它们之间的连接。该图可用于优化交通流量和规划交通基础设施。
* 网站分析：无向图可用于分析互联网上网页之间的链接。每个网页由一个顶点表示，网页之间的每个链接由一条边表示。

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

{% @mermaid/diagram content="flowchart LR
 A((1))---B((0)) & C((2))
 D((3))---E((4))" %}

输出

```
 0 1 2
 3 4
```

算法是：

* 将所有顶点初始化为未访问过。
* 对每个顶点 v 执行以下操作：
  * 如果之前没有访问过v，则调用深度优先遍历。并打印换行符以在新行中打印每个分量
    * 将 v 标记为已访问并打印 v。
    * 对于v的每一个相邻的u，如果u没有被访问过，则递归调用深度优先遍历。

代码实现：

```python
 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遍历节点：
  * 对于作为其父节点的每个节点，启动该算法。
  * 打印该不相交集合的节点，因为它们属于一个分量。

```python
 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 
```

[^1]: 进化图论是图论、概率论和数学生物学交叉领域的研究。进化图论是一种研究拓扑如何影响种群进化的方法。底层拓扑可以显著影响进化过程的结果，这一点在 Erez Lieberman、Christoph Hauert 和 Martin Nowak 的一篇论文中得到了最清晰的体现。

[^2]: 莫兰过程或莫兰模型是生物学中用来描述有限种群的简单随机过程。该过程以帕特里克·莫兰 (Patrick Moran) 的名字命名，他于 1958 年首次提出了该模型。它可用于模拟增加多样性的过程（例如突变）以及减少多样性的效应（例如遗传漂变和自然选择）。该过程可以描述恒定大小 N 的有限种群中的概率动态，其中两个等位基因 A 和 B 正在竞争主导地位。这两个等位基因被认为是真正的复制因子（即复制自身的实体）
