六度空间
用python语言描述六度空间理论你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。（20世纪60年代每个心理学家斯坦利*米尔格拉姆提出）
六度空间理论的出现使得人们对于人际关系网络的威力有了新的认识。但为什么偏偏是"六度"，而不是"七度""八度"或者"千百度"呢？
这可能要从人际关系网络的另外一个特征﹣-"150定律"来寻找解释。"150定律"指出，人类智力允许一个人维持稳定社交关系的人数上限是148人，四舍五入大约是150人。这样我们可以对六度空间理论做如下数学解释（并非数学证明）:若每个人平均认识150人，其六度便是150=11390625000000，消除一些重复的结点，也远远超过了整个地球人口的若干倍。
如果需要使用BFS等遍历或者队列：
from abc import ABCMeta, abstractmethod, abstractproperty
import sys
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkQueue:
def __init__(self):
self.front = None# 队首指针
self.rear = None# 队尾指针
def clear(self):
'''将队列置空'''
self.front = None
self.rear = None
def isEmpty(self):
'''判断队列是否为空'''
return self.front is None
def length(self):
'''返回队列的数据元素个数'''
p = self.front
i = 0
while p is not None:
p = p.next
i += 1
return i
def peek(self):
'''返回队首元素'''
if self.isEmpty():
return None
else:
return self.front.data
def offer(self, x):
'''将数据元素x插入到队列成为队尾元素'''
s = Node(x, None)
if not self.isEmpty():
self.rear.next = s
else:
self.front = s
self.rear = s
def poll(self):
'''将队首元素删除并返回其值'''
if self.isEmpty():
return None
p = self.front
self.front = self.front.next
if p == self.rear:# 删除结点为队尾结点时需要修改rear
self.rear = None
return p.data
def display(self):
'''输出队列中的所有元素'''
p = self.front
while p is not None:
print(p.data, end=' ')
p = p.next
class IGraph(metaclass=ABCMeta):
@abstractmethod
def createGraph(self):
'''创建图'''
pass
@abstractmethod
def getVNum(self):
'''返回图中的顶点数'''
pass
@abstractmethod
def getENum(self):
'''返回图中的边数'''
pass
@abstractmethod
def getVex(self, i):
'''返回位置为i的顶点值'''
pass
@abstractmethod
def locateVex(self, x):
'''返回值为x的顶点位置'''
pass
@abstractmethod
def firstAdj(self, i):
'''返回结点的第一个邻接点'''
pass
@abstractmethod
def nextAdj(self, i, j):
'''返回相对于j的下一个邻接点'''
pass
class MGraph(IGraph):
# 图类别静态常量
GRAPHKIND_UDG = 'UDG'
GRAPHKIND_DG = 'DG'
GRAPHKIND_UDN = 'UDN'
GRAPHKIND_DN = 'DN'
def __init__(self, kind=None, vNum=0, eNum=0, v=None, e=None):
self.kind = kind# 图的种类
self.vNum = vNum# 图的顶点数
self.eNum = eNum# 图的边数
self.v = v# 顶点列表
self.e = e# 邻接矩阵
def createUDG(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 构造边集
for i in range(eNum):
a, b = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = self.e = 1
def createDG(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 构造边集
for i in range(eNum):
a, b = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = 1
def createUDN(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 初始化边集
for i in range(eNum):
a, b, w = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = self.e = w
def createDN(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 初始化边集
for i in range(eNum):
a, b, w = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = w
def locateVex(self, x):
for i in range(self.vNum):
if self.v == x:
return i
return -1
def firstAdj(self, i):
if i < 0 or i >= self.vNum:
raise Exception("第%s个顶点不存在" % i)
for j in range(self.vNum):
if self.e != 0 and self.e < sys.maxsize:
return j
return -1
def nextAdj(self, i, j):
if j == self.vNum - 1:
return -1
for k in range(j + 1, self.vNum):
if self.e != 0 and self.e < sys.maxsize:
return k
return -1
class VNode(object):
def __init__(self, data=None, firstNode=None):
self.data = data# 存放结点值
self.firstArc = firstNode# 第一条边
class ArcNode(object):
def __init__(self, adjVex, value, nextArc=None):
self.adjVex = adjVex# 边指向的顶点的位置
self.value = value# 边的权值
self.nextArc = nextArc# 指向下一条边
class ALGraph(IGraph):
# 图类别静态常量
GRAPHKIND_UDG = 'UDG'
GRAPHKIND_DG = 'DG'
GRAPHKIND_UDN = 'UDN'
GRAPHKIND_DN = 'DN'
def __init__(self, kind=None, vNum=0, eNum=0, v=None, e=None):
self.kind = kind# 图的种类
self.vNum = vNum# 图的顶点数
self.eNum = eNum# 图的边数
self.v = v# 顶点列表
self.e = e# 边信息
def createGraph(self):
if self.kind == self.GRAPHKIND_UDG:
self.createUDG()
elif self.kind == self.GRAPHKIND_DG:
self.createDG()
elif self.kind == self.GRAPHKIND_UDN:
self.createUDN()
elif self.kind == self.GRAPHKIND_DN:
self.createDN()
def createUDG(self):
'''创建无向图'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, 1)
self.addArc(v, u, 1)
def createDG(self):
'''创建有向图'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, 1)
def createUDN(self):
'''创建无向网'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b, w = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, w)
self.addArc(v, u, w)
def createDN(self):
'''创建有向网'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b, w = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, w)
def addArc(self, i, j, value):
'''插入边结点'''
arc = ArcNode(j, value)
arc.nextArc = self.v.firstArc
self.v.firstArc = arc
def firstAdj(self, i):
'''查找第一个邻接点'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个结点不存在" % i)
p = self.v.firstArc
if p is not None:
return p.adjVex
return -1
def nextAdj(self, i, j):
'''返回i相对于j的下一个邻接点'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个结点不存在" % i)
p = self.v.firstArc
while p is not None:
if p.adjVex == j:
break
p = p.nextArc
if p.nextArc is not None:
return p.nextArc.adjVex
return -1
def getVNum(self):
'''返回顶点数'''
return self.vNum
def getENum(self):
'''返回边数'''
return self.eNum
def getVex(self, i):
'''返回第i个顶点的值'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个顶点不存在" % i)
return self.v.data
def locateVex(self, x):
'''返回值为x的顶点的位置'''
for i in range(self.vNum):
if self.v.data == x:
return i
return -1
def getArcs(self, u, v):
'''返回顶点u到顶点v的距离'''
if u < 0 or u >= self.vNum:
raise Exception("第%s个结点不存在" % u)
if v < 0 or v >= self.vNum:
raise Exception("第%s个结点不存在" % v)
p = self.v.firstArc
while p is not None:
if p.adjVex == v:
return p.value
p = p.nextArc
return sys.maxsize
#######################################
def BFSTraverse(g):
global visited
# 建立访问标志数组
visited = * g.getVNum()
count = 0
# 以每个顶点作为起始顶点进行遍历
for i in range(g.getVNum()):
if not visited:
count += 1
print(f'第{count}个连通块:', end=' ')
BFS(g, i)
print()
def BFS(g, i):
# 建立辅助队列
q = LinkQueue()
# 将起点加入队列
q.offer(i)
while not q.isEmpty():
u = q.poll()
# 标记顶点已访问
visited = True
print(g.getVex(u), end=' ')
v = g.firstAdj(u)
while v != -1:
# 顶点未访问的邻接点入队
if not visited:
q.offer(v)
# 获取下一个邻接点
v = g.nextAdj(u, v)
########################################
v =
e = [(1, 2), (2, 3), (4, 5)]
g = ALGraph(ALGraph.GRAPHKIND_UDG, len(v), len(e), v, e)# 引用类的属性
g.createGraph()
BFSTraverse(g)
##############################################################
def DFSTraverse(g):
global visited
# 建立访问标志数组
visited = * g.getVNum()
# 以每个顶点作为起始顶点进行遍历
for i in range(g.getVNum()):
if not visited:
DFS(g, i)
def DFS(g, i):
visited = True
print(g.getVex(i), end=' ')
v = g.firstAdj(i)
while v > 0:
if not visited:
DFS(g, v)
v = g.nextAdj(i, v)
class CloseEdge(object):
def __init__(self, adjVex, lowCost):
self.adjVex = adjVex# 在结合U中的顶点的值
self.lowCost = lowCost# 到集合U的最小距离
class MiniSpanTree(object):
def PRIM(g, u):
'''从值为u的顶点出发构造最小生成树，返回由生成树边组成的二维数组'''
tree = [ for i in range(g.getVNum() - 1)]
count = 0
closeEdge = * g.getVNum()
k = g.locateVex(u)
for j in range(g.getVNum()):
if k != j:
closeEdge = CloseEdge(u, g.getArcs(k, j))
closeEdge = CloseEdge(u, 0)
for i in range(1, g.getVNum()):
k = MiniSpanTree.getMinMum(closeEdge)
tree = closeEdge.adjVex
tree = g.getVex(k)
count += 1
closeEdge.lowCost = 0
for j in range(g.getVNum()):
if g.getArcs(k, j) < closeEdge.lowCost:
closeEdge = CloseEdge(g.getVex(k), g.getArcs(k, j))
return tree
def getMinMum(closeEdge):
minvalue = sys.maxsize
v = -1
for i in range(len(closeEdge)):
if closeEdge.lowCost != 0 and closeEdge.lowCost < minvalue:
minvalue = closeEdge.lowCost
v = i
return v
class ShortestPath:
def Djikstra(g, v0):
# 存放最短路径,p表示从v0到v的最短路径中经过的第k个点
p = [([-1] * g.getVNum()) for i in range(g.getVNum())]
# 存放最短路径长度
D = * g.getVNum()
# 若已找到最短路径，finish为True
finish = * g.getVNum()
v0 = g.locateVex(v0)
for v in range(g.getVNum()):
D = g.getArcs(v0, v)
if D < sys.maxsize:
# 从起点直接可以到达
p = v0
p = v
p = v0# 起点本身可以直接到达
D = 0
finish = True
v = -1
for i in range(1, g.getVNum()):
minvalue = sys.maxsize
for w in range(g.getVNum()):
# 找出所有最短路径中的最小值
if not finish:
if D < minvalue:
v = w
minvalue = D
finish = True
# 更新当前的最短路径
for w in range(g.getVNum()):
if not finish and g.getArcs(v, w) < sys.maxsize and (minvalue + g.getArcs(v, w) < D):
D = minvalue + g.getArcs(v, w)
for k in range(g.getVNum()):
p = p
if p == -1:
p = w
break
dis = {g.getVex(i): D for i in range(g.getVNum())}
# 返回到各点最短路的字典与路径矩阵
return dis, p
def printDjikstraPath(g, v0, p):
# v0到各点的输出最短路径,即p到p直到p==-1
u = v0
v0 = g.locateVex(v0)
for i in range(g.getVNum()):
v = g.getVex(i)
print('%s->%s的最短路径为:' % (u, v), end=' ')
if p != -1:
print(g.getVex(p), end='')
for k in range(1, g.getVNum()):
if p == -1:
break
print('->%s' % g.getVex(p), end='')
print('，长度为：%s' % dis)
def Floyd(g):# 多源点最短路径
vNum = g.getVNum()
D = [ * vNum for i in range(vNum)]
p = [[-1] * vNum for i in range(vNum)]
for u in range(vNum):
for v in range(vNum):
D = g.getArcs(u, v) if u != v else 0
if D < sys.maxsize:
p = u
for k in range(vNum):
for i in range(vNum):
for j in range(vNum):
if D > D + D:
D = D + D
p = i
p = p
dis = {(g.getVex(u), g.getVex(v)): D for u in range(vNum) for v in range(vNum)}
return dis, p
def printFloydPath(g, p):
vNum = g.getVNum()
for u in range(vNum):
for v in range(vNum):
if u == v:
print('%s->%s的最短路径为: %s' % (g.getVex(u), g.getVex(v), g.getVex(u)))
continue
flag = True
path =
t = p]
while t != u:
if t == -1:
flag = False
break
path = + path
t = p
print('%s->%s的最短路径为:' % (g.getVex(u), g.getVex(v)), end=' ')
if flag:
print(g.getVex(u), end='')
for node in path:
print('->%s' % g.getVex(node), end='')
print()
v =
e = [(1, 2, 45), (1, 3, 15), (1, 5, 15),
(3, 1, 10), (2, 4, 20), (2, 5, 15),
(2, 6, 15), (3, 2, 10), (3, 4, 60),
(4, 2, 30), (4, 6, 20)]
g = ALGraph(ALGraph.GRAPHKIND_UDN, len(v), len(e), v, e)
g.createGraph()
dis, p = ShortestPath.Djikstra(g, 1)
ShortestPath.printDjikstraPath(g, 1, p)
def findInDegree(g):
indegree = * g.getVNum()
# 计算每个点的入度
for u in range(g.getVNum()):
v = g.firstAdj(u)
while v != -1:
indegree += 1
v = g.nextAdj(u, v)
return indegree
def topoSort(g):
count = 0
indegree = findInDegree(g)
s = LinkStack()
topo = []
for i in range(g.getVNum()):
# 入度为0的点入栈
if indegree == 0:
s.push(i)
while not s.isEmpty():
u = s.pop()
topo.append(u)
count += 1
# 对该点的每个邻接点的入度-1
v = g.firstAdj(u)
while v != -1:
indegree -= 1
if indegree == 0:
s.push(v)
v = g.nextAdj(u, v)
if count < g.getVNum():
return None
return
def topoOrder(g):
count = 0
indegree = findInDegree(g)
s = LinkStack()
t = LinkStack()# 记录拓扑顺序
ve = * g.getVNum()
for i in range(g.getVNum()):
# 入度为0的点入栈
if indegree == 0:
s.push(i)
while not s.isEmpty():
u = s.pop()
t.push(u)
count += 1
# 对该点的每个邻接点的入度-1
v = g.firstAdj(u)
while v != -1:
indegree -= 1
if indegree == 0:
s.push(v)
# 更新最早发生时间
if ve + g.getArcs(u, v) > ve:
ve = ve + g.getArcs(u, v)
v = g.nextAdj(u, v)
if count < g.getVNum():
return None, None
return ve, t
def criticalPath(g):
ve, t = topoOrder(g)
if ve is None:
return None
vl = ] * g.getVNum()
# 逆拓扑序求各顶点的vl值
while not t.isEmpty():
u = t.pop()
v = g.firstAdj(u)
while v != -1:
if vl - g.getArcs(u, v) < vl:
vl = vl - g.getArcs(u, v)
v = g.nextAdj(u, v)
# 输出关键活动
print("关键活动为：", end='')
for i in range(g.getVNum()):
if ve == vl:
print(g.getVex(i), end=' ')
print()
# 6.6
v = ['A', 'B', 'C', 'D', 'E', 'F']
e = [
('A', 'B', 7), ('A', 'C', 5), ('A', 'D', 1),
('B', 'D', 6), ('B', 'E', 3), ('C', 'D', 7),
('C', 'F', 2), ('D', 'E', 6), ('D', 'F', 4),
('E', 'F', 7)
]
g1 = ALGraph(ALGraph.GRAPHKIND_UDN, len(v), len(e), v, e)
g1.createGraph()
print(MiniSpanTree.PRIM(g1, 'A'))
使用以上的代码 你好！请问有什么问题我可以帮到你吗？
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2023-12-30 17:40
你好！请问有什么问题我可以帮到你吗？
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续 ...
用python语言描述六度空间理论
你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。（20世纪60年代每个心理学家斯坦利*米尔格拉姆提出）
六度空间理论的出现使得人们对于人际关系网络的威力有了新的认识。但为什么偏偏是"六度"，而不是"七度""八度"或者"千百度"呢？
这可能要从人际关系网络的另外一个特征﹣-"150定律"来寻找解释。"150定律"指出，人类智力允许一个人维持稳定社交关系的人数上限是148人，四舍五入大约是150人。这样我们可以对六度空间理论做如下数学解释（并非数学证明）:若每个人平均认识150人，其六度便是150=11390625000000，消除一些重复的结点，也远远超过了整个地球人口的若干倍。
如果需要使用BFS等遍历或者队列：
from abc import ABCMeta, abstractmethod, abstractproperty
import sys
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkQueue:
def __init__(self):
self.front = None# 队首指针
self.rear = None# 队尾指针
def clear(self):
'''将队列置空'''
self.front = None
self.rear = None
def isEmpty(self):
'''判断队列是否为空'''
return self.front is None
def length(self):
'''返回队列的数据元素个数'''
p = self.front
i = 0
while p is not None:
p = p.next
i += 1
return i
def peek(self):
'''返回队首元素'''
if self.isEmpty():
return None
else:
return self.front.data
def offer(self, x):
'''将数据元素x插入到队列成为队尾元素'''
s = Node(x, None)
if not self.isEmpty():
self.rear.next = s
else:
self.front = s
self.rear = s
def poll(self):
'''将队首元素删除并返回其值'''
if self.isEmpty():
return None
p = self.front
self.front = self.front.next
if p == self.rear:# 删除结点为队尾结点时需要修改rear
self.rear = None
return p.data
def display(self):
'''输出队列中的所有元素'''
p = self.front
while p is not None:
print(p.data, end=' ')
p = p.next
class IGraph(metaclass=ABCMeta):
@abstractmethod
def createGraph(self):
'''创建图'''
pass
@abstractmethod
def getVNum(self):
'''返回图中的顶点数'''
pass
@abstractmethod
def getENum(self):
'''返回图中的边数'''
pass
@abstractmethod
def getVex(self, i):
'''返回位置为i的顶点值'''
pass
@abstractmethod
def locateVex(self, x):
'''返回值为x的顶点位置'''
pass
@abstractmethod
def firstAdj(self, i):
'''返回结点的第一个邻接点'''
pass
@abstractmethod
def nextAdj(self, i, j):
'''返回相对于j的下一个邻接点'''
pass
class MGraph(IGraph):
# 图类别静态常量
GRAPHKIND_UDG = 'UDG'
GRAPHKIND_DG = 'DG'
GRAPHKIND_UDN = 'UDN'
GRAPHKIND_DN = 'DN'
def __init__(self, kind=None, vNum=0, eNum=0, v=None, e=None):
self.kind = kind# 图的种类
self.vNum = vNum# 图的顶点数
self.eNum = eNum# 图的边数
self.v = v# 顶点列表
self.e = e# 邻接矩阵
def createUDG(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 构造边集
for i in range(eNum):
a, b = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = self.e = 1
def createDG(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 构造边集
for i in range(eNum):
a, b = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = 1
def createUDN(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 初始化边集
for i in range(eNum):
a, b, w = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = self.e = w
def createDN(self, vNum, eNum, v, e):
self.vNum = vNum
self.eNum = eNum
self.v = * vNum# 构造顶点集
for i in range(vNum):
self.v = v
self.e = [ * vNum] * vNum# 初始化边集
for i in range(eNum):
a, b, w = e
m, n = self.locateVex(a), self.locateVex(b)
self.e = w
def locateVex(self, x):
for i in range(self.vNum):
if self.v == x:
return i
return -1
def firstAdj(self, i):
if i < 0 or i >= self.vNum:
raise Exception("第%s个顶点不存在" % i)
for j in range(self.vNum):
if self.e != 0 and self.e < sys.maxsize:
return j
return -1
def nextAdj(self, i, j):
if j == self.vNum - 1:
return -1
for k in range(j + 1, self.vNum):
if self.e != 0 and self.e < sys.maxsize:
return k
return -1
class VNode(object):
def __init__(self, data=None, firstNode=None):
self.data = data# 存放结点值
self.firstArc = firstNode# 第一条边
class ArcNode(object):
def __init__(self, adjVex, value, nextArc=None):
self.adjVex = adjVex# 边指向的顶点的位置
self.value = value# 边的权值
self.nextArc = nextArc# 指向下一条边
class ALGraph(IGraph):
# 图类别静态常量
GRAPHKIND_UDG = 'UDG'
GRAPHKIND_DG = 'DG'
GRAPHKIND_UDN = 'UDN'
GRAPHKIND_DN = 'DN'
def __init__(self, kind=None, vNum=0, eNum=0, v=None, e=None):
self.kind = kind# 图的种类
self.vNum = vNum# 图的顶点数
self.eNum = eNum# 图的边数
self.v = v# 顶点列表
self.e = e# 边信息
def createGraph(self):
if self.kind == self.GRAPHKIND_UDG:
self.createUDG()
elif self.kind == self.GRAPHKIND_DG:
self.createDG()
elif self.kind == self.GRAPHKIND_UDN:
self.createUDN()
elif self.kind == self.GRAPHKIND_DN:
self.createDN()
def createUDG(self):
'''创建无向图'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, 1)
self.addArc(v, u, 1)
def createDG(self):
'''创建有向图'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, 1)
def createUDN(self):
'''创建无向网'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b, w = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, w)
self.addArc(v, u, w)
def createDN(self):
'''创建有向网'''
v = self.v
self.v = * self.vNum
for i in range(self.vNum):
self.v = VNode(v)
for i in range(self.eNum):
a, b, w = self.e
u, v = self.locateVex(a), self.locateVex(b)
self.addArc(u, v, w)
def addArc(self, i, j, value):
'''插入边结点'''
arc = ArcNode(j, value)
arc.nextArc = self.v.firstArc
self.v.firstArc = arc
def firstAdj(self, i):
'''查找第一个邻接点'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个结点不存在" % i)
p = self.v.firstArc
if p is not None:
return p.adjVex
return -1
def nextAdj(self, i, j):
'''返回i相对于j的下一个邻接点'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个结点不存在" % i)
p = self.v.firstArc
while p is not None:
if p.adjVex == j:
break
p = p.nextArc
if p.nextArc is not None:
return p.nextArc.adjVex
return -1
def getVNum(self):
'''返回顶点数'''
return self.vNum
def getENum(self):
'''返回边数'''
return self.eNum
def getVex(self, i):
'''返回第i个顶点的值'''
if i < 0 or i >= self.vNum:
raise Exception("第%s个顶点不存在" % i)
return self.v.data
def locateVex(self, x):
'''返回值为x的顶点的位置'''
for i in range(self.vNum):
if self.v.data == x:
return i
return -1
def getArcs(self, u, v):
'''返回顶点u到顶点v的距离'''
if u < 0 or u >= self.vNum:
raise Exception("第%s个结点不存在" % u)
if v < 0 or v >= self.vNum:
raise Exception("第%s个结点不存在" % v)
p = self.v.firstArc
while p is not None:
if p.adjVex == v:
return p.value
p = p.nextArc
return sys.maxsize
#######################################
def BFSTraverse(g):
global visited
# 建立访问标志数组
visited = * g.getVNum()
count = 0
# 以每个顶点作为起始顶点进行遍历
for i in range(g.getVNum()):
if not visited:
count += 1
print(f'第{count}个连通块:', end=' ')
BFS(g, i)
print()
def BFS(g, i):
# 建立辅助队列
q = LinkQueue()
# 将起点加入队列
q.offer(i)
while not q.isEmpty():
u = q.poll()
# 标记顶点已访问
visited = True
print(g.getVex(u), end=' ')
v = g.firstAdj(u)
while v != -1:
# 顶点未访问的邻接点入队
if not visited:
q.offer(v)
# 获取下一个邻接点
v = g.nextAdj(u, v)
########################################
v =
e = [(1, 2), (2, 3), (4, 5)]
g = ALGraph(ALGraph.GRAPHKIND_UDG, len(v), len(e), v, e)# 引用类的属性
g.createGraph()
BFSTraverse(g)
##############################################################
def DFSTraverse(g):
global visited
# 建立访问标志数组
visited = * g.getVNum()
# 以每个顶点作为起始顶点进行遍历
for i in range(g.getVNum()):
if not visited:
DFS(g, i)
def DFS(g, i):
visited = True
print(g.getVex(i), end=' ')
v = g.firstAdj(i)
while v > 0:
if not visited:
DFS(g, v)
v = g.nextAdj(i, v)
class CloseEdge(object):
def __init__(self, adjVex, lowCost):
self.adjVex = adjVex# 在结合U中的顶点的值
self.lowCost = lowCost# 到集合U的最小距离
class MiniSpanTree(object):
def PRIM(g, u):
'''从值为u的顶点出发构造最小生成树，返回由生成树边组成的二维数组'''
tree = [ for i in range(g.getVNum() - 1)]
count = 0
closeEdge = * g.getVNum()
k = g.locateVex(u)
for j in range(g.getVNum()):
if k != j:
closeEdge = CloseEdge(u, g.getArcs(k, j))
closeEdge = CloseEdge(u, 0)
for i in range(1, g.getVNum()):
k = MiniSpanTree.getMinMum(closeEdge)
tree = closeEdge.adjVex
tree = g.getVex(k)
count += 1
closeEdge.lowCost = 0
for j in range(g.getVNum()):
if g.getArcs(k, j) < closeEdge.lowCost:
closeEdge = CloseEdge(g.getVex(k), g.getArcs(k, j))
return tree
def getMinMum(closeEdge):
minvalue = sys.maxsize
v = -1
for i in range(len(closeEdge)):
if closeEdge.lowCost != 0 and closeEdge.lowCost < minvalue:
minvalue = closeEdge.lowCost
v = i
return v
class ShortestPath:
def Djikstra(g, v0):
# 存放最短路径,p表示从v0到v的最短路径中经过的第k个点
p = [([-1] * g.getVNum()) for i in range(g.getVNum())]
# 存放最短路径长度
D = * g.getVNum()
# 若已找到最短路径，finish为True
finish = * g.getVNum()
v0 = g.locateVex(v0)
for v in range(g.getVNum()):
D = g.getArcs(v0, v)
if D < sys.maxsize:
# 从起点直接可以到达
p = v0
p = v
p = v0# 起点本身可以直接到达
D = 0
finish = True
v = -1
for i in range(1, g.getVNum()):
minvalue = sys.maxsize
for w in range(g.getVNum()):
# 找出所有最短路径中的最小值
if not finish:
if D < minvalue:
v = w
minvalue = D
finish = True
# 更新当前的最短路径
for w in range(g.getVNum()):
if not finish and g.getArcs(v, w) < sys.maxsize and (minvalue + g.getArcs(v, w) < D):
D = minvalue + g.getArcs(v, w)
for k in range(g.getVNum()):
p = p
if p == -1:
p = w
break
dis = {g.getVex(i): D for i in range(g.getVNum())}
# 返回到各点最短路的字典与路径矩阵
return dis, p
def printDjikstraPath(g, v0, p):
# v0到各点的输出最短路径,即p到p直到p==-1
u = v0
v0 = g.locateVex(v0)
for i in range(g.getVNum()):
v = g.getVex(i)
print('%s->%s的最短路径为:' % (u, v), end=' ')
if p != -1:
print(g.getVex(p), end='')
for k in range(1, g.getVNum()):
if p == -1:
break
print('->%s' % g.getVex(p), end='')
print('，长度为：%s' % dis)
def Floyd(g):# 多源点最短路径
vNum = g.getVNum()
D = [ * vNum for i in range(vNum)]
p = [[-1] * vNum for i in range(vNum)]
for u in range(vNum):
for v in range(vNum):
D = g.getArcs(u, v) if u != v else 0
if D < sys.maxsize:
p = u
for k in range(vNum):
for i in range(vNum):
for j in range(vNum):
if D > D + D:
D = D + D
p = i
p = p
dis = {(g.getVex(u), g.getVex(v)): D for u in range(vNum) for v in range(vNum)}
return dis, p
def printFloydPath(g, p):
vNum = g.getVNum()
for u in range(vNum):
for v in range(vNum):
if u == v:
print('%s->%s的最短路径为: %s' % (g.getVex(u), g.getVex(v), g.getVex(u)))
continue
flag = True
path =
t = p]
while t != u:
if t == -1:
flag = False
break
path = + path
t = p
print('%s->%s的最短路径为:' % (g.getVex(u), g.getVex(v)), end=' ')
if flag:
print(g.getVex(u), end='')
for node in path:
print('->%s' % g.getVex(node), end='')
print()
v =
e = [(1, 2, 45), (1, 3, 15), (1, 5, 15),
(3, 1, 10), (2, 4, 20), (2, 5, 15),
(2, 6, 15), (3, 2, 10), (3, 4, 60),
(4, 2, 30), (4, 6, 20)]
g = ALGraph(ALGraph.GRAPHKIND_UDN, len(v), len(e), v, e)
g.createGraph()
dis, p = ShortestPath.Djikstra(g, 1)
ShortestPath.printDjikstraPath(g, 1, p)
def findInDegree(g):
indegree = * g.getVNum()
# 计算每个点的入度
for u in range(g.getVNum()):
v = g.firstAdj(u)
while v != -1:
indegree += 1
v = g.nextAdj(u, v)
return indegree
def topoSort(g):
count = 0
indegree = findInDegree(g)
s = LinkStack()
topo = []
for i in range(g.getVNum()):
# 入度为0的点入栈
if indegree == 0:
s.push(i)
while not s.isEmpty():
u = s.pop()
topo.append(u)
count += 1
# 对该点的每个邻接点的入度-1
v = g.firstAdj(u)
while v != -1:
indegree -= 1
if indegree == 0:
s.push(v)
v = g.nextAdj(u, v)
if count < g.getVNum():
return None
return
def topoOrder(g):
count = 0
indegree = findInDegree(g)
s = LinkStack()
t = LinkStack()# 记录拓扑顺序
ve = * g.getVNum()
for i in range(g.getVNum()):
# 入度为0的点入栈
if indegree == 0:
s.push(i)
while not s.isEmpty():
u = s.pop()
t.push(u)
count += 1
# 对该点的每个邻接点的入度-1
v = g.firstAdj(u)
while v != -1:
indegree -= 1
if indegree == 0:
s.push(v)
# 更新最早发生时间
if ve + g.getArcs(u, v) > ve:
ve = ve + g.getArcs(u, v)
v = g.nextAdj(u, v)
if count < g.getVNum():
return None, None
return ve, t
def criticalPath(g):
ve, t = topoOrder(g)
if ve is None:
return None
vl = ] * g.getVNum()
# 逆拓扑序求各顶点的vl值
while not t.isEmpty():
u = t.pop()
v = g.firstAdj(u)
while v != -1:
if vl - g.getArcs(u, v) < vl:
vl = vl - g.getArcs(u, v)
v = g.nextAdj(u, v)
# 输出关键活动
print("关键活动为：", end='')
for i in range(g.getVNum()):
if ve == vl:
print(g.getVex(i), end=' ')
print()
# 6.6
v = ['A', 'B', 'C', 'D', 'E', 'F']
e = [
('A', 'B', 7), ('A', 'C', 5), ('A', 'D', 1),
('B', 'D', 6), ('B', 'E', 3), ('C', 'D', 7),
('C', 'F', 2), ('D', 'E', 6), ('D', 'F', 4),
('E', 'F', 7)
]
g1 = ALGraph(ALGraph.GRAPHKIND_UDN, len(v), len(e), v, e)
g1.createGraph()
print(MiniSpanTree.PRIM(g1, 'A'))
使用以上的代码
urbanlife 发表于 2023-12-30 17:44
用python语言描述六度空间理论
你和任何一个陌生人之 ...
这段代码是一个用Python描述六度空间理论的示例，包括广度优先搜索（BFS）、深度优先搜索（DFS）、最小生成树（Prim算法）、
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2023-12-30 17:45
这段代码是一个用Python描述六度空间理论的示例，包括广度优先搜索（BFS）、深度优先搜索（DFS）、最小 ...
用python语言描述六度空间理论
你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。（20世纪60年代每个心理学家斯坦利*米尔格拉姆提出）
六度空间理论的出现使得人们对于人际关系网络的威力有了新的认识。但为什么偏偏是"六度"，而不是"七度""八度"或者"千百度"呢？
这可能要从人际关系网络的另外一个特征﹣-"150定律"来寻找解释。"150定律"指出，人类智力允许一个人维持稳定社交关系的人数上限是148人，四舍五入大约是150人。这样我们可以对六度空间理论做如下数学解释（并非数学证明）:若每个人平均认识150人，其六度便是150=11390625000000，消除一些重复的结点，也远远超过了整个地球人口的若干倍。
如果需要使用BFS等遍历或者队列：
尽量简单的证明 urbanlife 发表于 2023-12-30 17:53
用python语言描述六度空间理论
你和任何一个陌生人之 ...
六度空间理论的简单证明可以通过广度优先搜索（BFS）来进行。我们假设每个人平均认识150个人，然后使用BFS遍
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2023-12-30 17:54
六度空间理论的简单证明可以通过广度优先搜索（BFS）来进行。我们假设每个人平均认识150个人，然后使用 ...
给我具体的代码，BFS：
def BFSTraverse(g):
global visited
# 建立访问标志数组
visited = * g.getVNum()
count = 0
# 以每个顶点作为起始顶点进行遍历
for i in range(g.getVNum()):
if not visited:
count += 1
print(f'第{count}个连通块:', end=' ')
BFS(g, i)
print()
def BFS(g, i):
# 建立辅助队列
q = LinkQueue()
# 将起点加入队列
q.offer(i)
while not q.isEmpty():
u = q.poll()
# 标记顶点已访问
visited = True
print(g.getVex(u), end=' ')
v = g.firstAdj(u)
while v != -1:
# 顶点未访问的邻接点入队
if not visited:
q.offer(v)
# 获取下一个邻接点
v = g.nextAdj(u, v) urbanlife 发表于 2023-12-30 17:55
给我具体的代码，BFS：
def BFSTraverse(g):
gl ...
好的，以下是使用BFS进行六度空间理论的代码：
from queue import Queue
def find_six_degrees(network, start):
visited = set()# 存储已经访问过的人
distance = {}# 存储每个人与起始人的距离
queue = Queue()# 使用队列进行BFS遍历
queue.put((start, 0))# 将起始人加入队列
visited.add(start)# 标记起始人为已访问
while not queue.empty():
person, dist = queue.get()# 获取队列中的当前人物及其距离
distance = dist
if dist < 6:
# 遍历当前人物的所有邻居
for friend in network:
if friend not in visited:
visited.add(friend)# 标记邻居为已访问
queue.put((friend, dist + 1))# 邻居入队，并更新距离
return distance
# 测试数据
network = {
'Alice': ['Bob', 'Charlie', 'David'],
'Bob': ['Alice', 'Eve'],
'Charlie': ['Alice', 'Dave'],
'David': ['Alice', 'Frank'],
'Dave': ['Charlie', 'Frank'],
'Eve': ['Bob', 'Frank'],
'Frank': ['David', 'Dave', 'Eve']
}
start_person = 'Alice'
distances = find_six_degrees(network, start_person)
for person, dist in distances.items():
print(f"{person} 与 {start_person} 的距离为 {dist}")
以上代码使用字典表示人际关系网络，其中每个人作为键，对应的值是一个列表，表示与该人直接相连的朋友。通过BFS遍历，可以找到起始人与每个其他人之间的距离，并打印出来。你可以根据实际情况修改测试数据进行验证。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2023-12-30 17:56
好的，以下是使用BFS进行六度空间理论的代码：
用python语言证明六度空间理论w urbanlife 发表于 2023-12-30 17:58
用python语言证明六度空间理论w
六度空间理论是基于人际关系网络的理论，它并没有严格的数学证明。然而，我们可以通过编写代码来模拟验证六度空间理论。
首先，我们需要构建一个人际关系网络。假设我们有一组人名，我们可以随机生成他们之间的关系。
import random
# 生成一个人际关系网络
def generate_network(names):
network = {}
for name in names:
# 随机选择5个朋友
friends = random.sample(names, 5)
# 将自己从朋友列表中移除
friends.remove(name)
network = friends
return network
# 测试数据
names = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank']
network = generate_network(names)
# 打印人际关系网络
for name, friends in network.items():
print(f"{name}的朋友：{friends}")
接下来，我们可以使用BFS算法来计算每个人与起始人之间的距离，并统计距离超过6的人的数量。
from queue import Queue
# 使用BFS算法计算每个人与起始人的距离
def calculate_distances(network, start):
distances = {}
visited = set()
queue = Queue()
queue.put((start, 0))
visited.add(start)
while not queue.empty():
person, dist = queue.get()
distances = dist
if dist < 6:
friends = network
for friend in friends:
if friend not in visited:
visited.add(friend)
queue.put((friend, dist + 1))
return distances
# 计算每个人与起始人之间的距离
distances = calculate_distances(network, 'Alice')
# 统计距离超过6的人的数量
count = sum(1 for dist in distances.values() if dist > 6)
print(f"距离超过6的人的数量：{count}")
通过运行以上代码，我们可以得到一个结果，表示距离超过6的人的数量。如果数量很小，那么可以认为六度空间理论成立。请注意，由于人际关系网络是随机生成的，每次运行结果可能会有所不同。
这个例子只是一个模拟验证，不能完全证明六度空间理论的准确性。真正验证这个理论需要更多的真实数据和复杂的算法分析。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]