🍠Python元胞自动机沙堆糖景堵塞模型图学习

关键词

Python | 图论 | 网络 | 关联图 | 关系 | 自然语言处理 | 心里创伤 | 有向图 | 无向图 | 随机图 | 随机图 | 概率 | 小世界 | 晶格 | 节点 | 聚类系数 | 路径长度 | 算法 | 网络模型 | 元胞自动机 | 物理 | 谢林模型 | 糖景模型 | 堵塞模型 | 生物演化模型 | 适应度 | 矩阵 | 图学习 | 数学 | 统计

Python元胞自动机沙堆糖景堵塞模型图学习 | Notion亚图跨际 on Notion

🏈指点迷津 | Brief

🎯要点

1. 🎯简要图分析：🖊百科信息网络图 | 🖊企业和政府关联图 | 🖊共同购买或共同推荐产品关系图 | 🖊自然语言分析不同文化关系网 | 🖊心理创伤和类型网络属性。

2. 🎯复杂图：🎯埃尔多斯-雷尼模型：🖊有向图、无向图、完整图、随机图、检查图是否连通，检查模型生成随机图连通的概率。🎯小世界图模型：🖊制作环形晶格，瓦茨-斯特罗加茨图、计算给定节点的局部聚类系数、计算所有节点对之间的路径长度、使用给定参数生成瓦茨-斯特罗加茨图并返回一对（平均路径长度、聚类系数）、广度优先搜索算法查找可达节点、迪杰斯特拉算法寻找最短路径。🎯无标度网络模型：🖊构建一瓦茨-斯特罗加茨图，其节点数和平均度与社交网络相同、生成巴拉巴西-阿尔伯特模型、查看度分布、累计分布。🎯元胞自动机模型：🖊零维和一维元胞自动机模型、使用“互相关”更快地更新模型、表示一维元胞自动机。🎯物理模型：🖊反应扩散模型、渗透模型、分形模型、渗滤模型中的分形。🎯自组织临界性模型：🖊沙堆、长尾分布、分形几何、光谱密度。🎯基于代理的模型：🖊谢林模型、糖景模型、生命有限的糖景模型、波浪式迁徙模型。🎯堵塞模型：🖊交通阻塞。🎯生物演化模型：🖊适应度景观、适应度分布、生存差异，合作演化。

3. 🎯图数据分析：🎯物种食物链网：🖊邻接矩阵数据 | 🖊有向网络统计计算 | 🖊链网无向图度 | 🖊绘制直方图 | 🖊计算聚类系数 | 🖊生成领结图 | 🖊 广度优先搜索算法计算无向图距离。🎯全球贸易图 | 🎯互联网基础设施图 | 🎯万维网和社交结构图 | 🎯金融结构图 | 🎯图学习

🍇Python广度优先搜索和深度优先搜索算法

💦广度优先搜索算法

给定一个图，其中每条边的权重为 0 或 1。图中还给出了源顶点。找到从源顶点到所有其他顶点的最短路径。

查找附近节点的一种简单方法称为 0-1 BFS。 它不是用布尔数组标记访问过的节点，而是在每一步检查条件。 它使用双端队列来存储节点。 如果边的权重为 0，则将该节点插入到队列的前面。 但如果边的权重为 1，则该节点位于后面。

该方法与Dijkstra算法类似。 它根据相邻节点更新到节点的最短距离。 仅当节点的距离可以通过前一个节点的距离来改善时，该节点才会被添加到队列中。 这有助于找到到达节点的最佳路径。

这种方式在很多情况下效果很好。 当从线上取一个点时（如 Dijkstra 的方式），这意味着该点的剩余权重最小。 如果存在权重为 0 的下一个点，则它与刚刚选取的点的距离相同。 但如果下一个点的权重为 1，那么它现在是该行中所有点中距离最远的点。 这是因为所有其他点要么直接连接到当前点，要么连接到已经占用的点。

 from sys import maxsize as INT_MAX
 from collections import deque
 ​
 V = 9
 ​
 class node:
     def __init__(self, to, weight):
 ​
         self.to = to
         self.weight = weight
 ​
 edges = [0] * V
 for i in range(V):
     edges[i] = []
 ​
 ​
 def zeroOneBFS(src: int):
 ​
     dist = [0] * V
     for i in range(V):
         dist[i] = INT_MAX
 ​
     Q = deque()
     dist[src] = 0
     Q.append(src)
 ​
     while Q:
         v = Q[0]
         Q.popleft()
 ​
         for i in range(len(edges[v])):
 ​
             if (dist[edges[v][i].to] > 
                 dist[v] + edges[v][i].weight):
                 dist[edges[v][i].to] = dist[v] + edges[v][i].weight
 ​
                 if edges[v][i].weight == 0:
                     Q.appendleft(edges[v][i].to)
                 else:
                     Q.append(edges[v][i].to)
 ​
     for i in range(V):
         print(dist[i], end = " ")
     print()
 ​
 def addEdge(u: int, v: int, wt: int):
     edges[u].append(node(v, wt))
     edges[u].append(node(v, wt))
 ​
 if __name__ == "__main__":
 ​
     addEdge(0, 1, 0)
     addEdge(0, 7, 1)
     addEdge(1, 7, 1)
     addEdge(1, 2, 1)
     addEdge(2, 3, 0)
     addEdge(2, 5, 0)
     addEdge(2, 8, 1)
     addEdge(3, 4, 1)
     addEdge(3, 5, 1)
     addEdge(4, 5, 1)
     addEdge(5, 6, 1)
     addEdge(6, 7, 1)
     addEdge(7, 8, 1)
 ​
     src = 0
     zeroOneBFS(src)
 ​

输出

 0 0 1 1 2 1 2 1 2 

💦深度优先搜索算法

给定一个有向图，对于给定图中的所有顶点对 (u, v)，找出一个顶点 v 是否可以从另一个顶点 u 到达。 这里的可达性意味着从顶点u到v存在一条路径。可达性矩阵称为图的传递闭包。

上图的传递闭包是:

 1 1 1 1
 1 1 1 1
 1 1 1 1
 0 0 0 1

 from collections import defaultdict
  
 class Graph:
  
     def __init__(self,vertices):
         self.V = vertices
  
         self.graph = defaultdict(list)
  
         self.tc = [[0 for j in range(self.V)] for i in range(self.V)]
  
     def addEdge(self, u, v):
         self.graph[u].append(v)
  
     def DFSUtil(self, s, v):
 ​
         if(s == v):
             if( v in self.graph[s]):
               self.tc[s][v] = 1
         else:
             self.tc[s][v] = 1
  
         for i in self.graph[v]:
             if self.tc[s][i] == 0:
                 if s==i:
                    self.tc[s][i]=1
                 else:
                    self.DFSUtil(s, i)
  
     def transitiveClosure(self):
 ​
         for i in range(self.V):
             self.DFSUtil(i, i)
         
         print(self.tc)
  
 g = Graph(4)
 g.addEdge(0, 1)
 g.addEdge(0, 2)
 g.addEdge(1, 2)
 g.addEdge(2, 0)
 g.addEdge(2, 3)
 g.addEdge(3, 3)
  
 g.transitiveClosure()
 ​

输出

 Transitive closure matrix is 
 1 1 1 1 
 1 1 1 1 
 1 1 1 1 
 0 0 0 1