复杂网络的任意子节点的网络最短距离

复杂网络的任意子节点的网络最短距离

前文图的同构算法忘记说环境了。要执行成功算法需要进行以下设置。
工具是学习用的pycharm
步骤：
1.File->Setting

2.找到如图所示的位置，点击+号

3.搜索对应的包下载即可。

这次是算法设计大作业的，复杂网络中m结点组成的子网的最短的一条路径。原题目是这样的。

思路
初始定义一个大小为结点数目的一维数组，这个一维数组下标即为对应的结点，即下标0对应结点1，同理也是如此。数据存的是该结点的父节点的下标，比如结点1的父节点是结点12，则数组对应的是arr[0]=11.一次类推，最后得到一条待裁剪的路径链。这次数组我定义为初始路径数组。
步骤：
对每个子网结点宽搜一遍。每宽搜到对应的结点则入队并且对初始路径数组进行更改，并且路径数++，每宽搜一层对应一条路径。对应的结束条件：子网结点都在宽搜队列。
最后能得到完整的初始路径数组。
对这一路径数组进行裁剪，即寻找m子网结点到初始宽搜的基点的各条路径，同二维数组存储，最终得到裁剪后的路径也就是以初始宽搜的基点为准的路径。
接着计算结点直接的路径距离，与最短路径比较，若小于最短路径则替代最短路径。
对m结点的每个结点都如此 *** 作，最终得到最短路径。
理论知识：
从基点开始宽搜，这个基点到其它点的路径是最短的。
贪心，求局部最优解进而退出整体最优解。
所有我个人认为这个思路是没问题的
程序由python代码编写。当然我也不知道你们看不看得懂。

import matplotlib.pyplot as plt
import networkx as nx
import pandas as pd
import numpy as np
# 获取Karate俱乐部数据的邻接表，以csv文件存储
columns = ['Source', 'Target']
data = pd.read_csv('Karate_club.csv', names=columns, header=None)
# 调用networkx画图
graph = nx.Graph()
data_len = len(data)
# 给graph中添加边，即用户关系
for i in range(data_len):
    graph.add_edge(data.iloc[i]['Source'], data.iloc[i]['Target'])
# 输出每个节点的度
print("每个节点的度:",graph.degree())
# 调用nx.draw()方法绘制图片
nx.draw(graph, with_labels=True)
# 保存图片
# plt.savefig('./karate_club.png')
# 展示图片
plt.show()
n =len(graph.degree())
print("结点个数：",n)
graphic=[
   [0,1,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0],
   [1,0,1,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0],
   [1,1,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0],
   [1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1],
   [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
   [1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,1,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],
   [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1],
   [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1],
   [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1],
   [0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
   [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,1],
   [0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,0,1],
   [0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,0],
]
print(graphic)

mNode=input("输入数个结点名，以空格分开：").split(" ")
print(mNode)
print("结点数目：",len((mNode)))
minPathLen=999999#子网络最短路径
minPath=[]#存储路径的
for i in range(len(mNode)):#m结点子网络，每个结点都遍历一遍
    print("结点{0}宽搜".format(mNode[i]))
    headPoint=mNode[i]
    queue = []  # 宽搜队列
    queue.append(int(mNode[i])-1) #进队
    onceDfsCount=len(queue) #初始一次宽搜次数为队列长度
    d = 0  # 初始化路径长度
    visit=np.full(n,0)#记录已被访问过的结点
    nodeList=np.full(n,-1)#构成路径 结点对应的父节点 下标对应结点 -1表示无父节点
    head = int(queue[0]) # 路径头
    while(len(queue)>0): #遍历宽搜扫描后的队列
        current=int(queue[0]) # 队头出队
        # print("当前结点={0}".format(current+1))
        del queue[0]# 队头出队
        visit[current]=1#标记访问过
        # print("目前已访问过的结点的下标：", visit)
        for k in range(n): #遍历识别关联边
            if(visit[k]==1):
                continue
            if(graphic[current][k]==1):#关联边
                # print("关联结点：",k+1)
                if(k not in queue): #如果不在队列则进 如果在就不用进了 因为先进的路径最短
                    nodeList[k]=current # 父节点
                    queue.append(k) # 关联结点进队列
        onceDfsCount -= 1  # 次数-1用于判断路径长度是否需++
        if (onceDfsCount == 0):
            d += 1  # 扫描一圈路径长度++
            onceDfsCount = len(queue) # 宽搜一圈相关点数
        # print("宽搜{0}次,关联结点下标：{1}".format(d,queue))
        count=0
        for flag in range(len(mNode)): #如果都扫面到了 就不用继续向下扫了
            if(visit[int(mNode[flag])]==1):
                count+=1
        # print("count:{0},len(mNode):{1}".format(count,len(mNode)))
        if(count==len(mNode)):
            print("路径结点下标链：",nodeList)
            pointList=[]#基点到波及点的链 链中有链
            print("裁剪路径链")
            # 根据路径计算路径长
            # 由基点扩散的 波及点绝对能回基点
            baseNodePath=0#基点到波及点路径之和
            for i in range(0,len(mNode)):
                print("路径：" + mNode[i])
                aid = int(mNode[i]) - 1  # 波及点下标
                distance=0 # 距离
                chirdList=[]#子链 与pointList联系
                chirdList.append(int(mNode[i]))
                for j in range(n):
                    temp=nodeList[aid]#波及点
                    aid=temp#路径搜索
                    if(temp==-1): #基点
                        print("回到基点：",head+1)
                        if (distance > 0):  # 自己对自己就没必要构成链了
                            pointList.append(chirdList)
                            baseNodePath+=distance
                        break
                    print("波及点：", temp + 1)
                    chirdList.append(temp+1)
                    distance+=1
                print("结点{0}到结点{1}的距离为{2}".format(mNode[i],head+1,distance))
            print("裁剪后的路径链：",pointList)
            print("基点到波及点的路径总长：",baseNodePath)
            '''
                波及点之间路径计算
            '''
            for i in range(len(pointList)):
                for j in range(i+1,len(pointList)):
                    spreadPointPath = len(pointList[i]) +len(pointList[j])# 波及点之间必有转点
                    for k in range(len(pointList[i])):
                        if(pointList[i][k] in pointList[j]):
                            spreadPointPath -= 2 #重复点2个
                    print("波及点{0}与波及点{1}的路径长度为{2}".format(pointList[i][0], pointList[j][0],spreadPointPath))
                    baseNodePath+=spreadPointPath#计算子网总路径
            print("以{0}为基点扩散,计算得子网总路径为{1}".format(headPoint,baseNodePath))
            if(minPathLen>baseNodePath):
                minPathLen=baseNodePath
                minPath=pointList
            print("结束！！！")
            break
print("故得最短路径长度{0}，对应的路径为:{1}".format(minPathLen,minPath))

本人估计算法时间复杂度O((n*m)^2),n为复杂网络是结点数之和，m为子网结点数。
空间复杂度:O(n^2),邻接矩阵存储的是这样的了。
总结：
代码我不知道是对还是错的哈，这是本人的课程要求设计的作业，还没交待验证。只是个人觉得应该是对的。
注意，数据集来源：Karate空手道俱乐部数据集的简单处理_int_chao的博客-CSDN博客。来源这个热心的大佬，谢谢你的数据。