🎯要点
- 🎯简要图分析：🖊百科信息网络图 | 🖊企业和政府关联图 | 🖊共同购买或共同推荐产品关系图 | 🖊自然语言分析不同文化关系网 | 🖊心理创伤和类型网络属性。
- 🎯复杂图：🎯埃尔多斯-雷尼模型：🖊有向图、无向图、完整图、随机图、检查图是否连通，检查模型生成随机图连通的概率。🎯小世界图模型：🖊制作环形晶格，瓦茨-斯特罗加茨图、计算给定节点的局部聚类系数、计算所有节点对之间的路径长度、使用给定参数生成瓦茨-斯特罗加茨图并返回一对（平均路径长度、聚类系数）、广度优先搜索算法查找可达节点、迪杰斯特拉算法寻找最短路径。🎯无标度网络模型：🖊构建一瓦茨-斯特罗加茨图，其节点数和平均度与社交网络相同、生成巴拉巴西-阿尔伯特模型、查看度分布、累计分布。🎯元胞自动机模型：🖊零维和一维元胞自动机模型、使用“互相关”更快地更新模型、表示一维元胞自动机。🎯物理模型：🖊反应扩散模型、渗透模型、分形模型、渗滤模型中的分形。🎯自组织临界性模型：🖊沙堆、长尾分布、分形几何、光谱密度。🎯基于代理的模型：🖊谢林模型、糖景模型、生命有限的糖景模型、波浪式迁徙模型。🎯堵塞模型：🖊交通阻塞。🎯生物演化模型：🖊适应度景观、适应度分布、生存差异，合作演化。
- 🎯图数据分析：🎯物种食物链网：🖊邻接矩阵数据 | 🖊有向网络统计计算 | 🖊链网无向图度 | 🖊绘制直方图 | 🖊计算聚类系数 | 🖊生成领结图 | 🖊 广度优先搜索算法计算无向图距离。🎯全球贸易图 | 🎯互联网基础设施图 | 🎯万维网和社交结构图 | 🎯金融结构图 | 🎯图学习
🍇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
