精华内容
下载资源
问答
  • 最小生成树 prim算法实现(利用图的邻接矩阵来存放图)
    千次阅读
    2015-11-18 09:32:59

    定义:最小生成树并不像数据结构中的树一样,而是从图演化而来,生成树有DFS生成树,BFS生成树,最小生成树等。

    所谓最小生成树,就是在有N个节点的连通图中,找出N-1条边使N个点仍然连通,并且个边权值和最小。

    代码如下:

    /**********计算出图的最小生成树的代价,不能直达的点之间的权值设为100,假设所有点之间的
    权值不超过99,代码暂时显示出生成树的路径貌似有bug*********/
    #include<stdio.h>
    #define M 6
    void INIT_MAP(int map[][M]){
    	for(int i=0;i<M;i++){
    		for(int j=0;j<M;j++){
    			scanf("%d",&map[i][j]);
    		}
    	} 
    }
    
    void SHOW_MAP(const int map[][M]){
    	for(int i=0;i<M;i++){
    		for(int j=0;j<M;j++){
    			printf("%d ",map[i][j]);
    		}printf("\n");
    	}
    }
    
    int procs(const int map[][M],int visit[][M-1]){
    	int res=0;
    	int ever[M]={0};
    	int low[M]={0};
    	int pos=0;
    	ever[0]=1;
    	for(int i=1;i<M;i++){
    		low[i]=map[pos][i];
    	}								//随即从第一个节点开始访问 
    	for(int i=1;i<M;i++){
    		//printf("%d-----",pos+1);
    		int max=100;
    		for(int j=0;j<M;j++){
    			if(ever[j]==0&&max>low[j]){
    				pos=j;
    				max=low[j];
    			}
    		}
    		visit[0][i-1]=max;
    		visit[1][i-1]=pos;
    	//	printf("-----%d\n",pos+1);
    		ever[pos]=1;
    	//	printf("%d\n",max); 
    		res+=max;
    		for(int j=0;j<M;j++){
    			if(ever[j]==0&&low[j]>map[pos][j]){
    				low[j]=map[pos][j];
    			}
    		}
    	}
    	return res;
    }
    
    void SHOW_ROAD(const int map[][M],const int visit[][M-1]){
    	for(int i=0;i<M-1;i++){
    		for(int j=0;j<M;j++){
    			if(map[visit[1][i]][j]==visit[0][i]){
    				printf("%d",j+1);
    			}
    		}
    		//printf("%d",);
    		printf("-----%d\n",visit[1][i]+1); 
    	} 
    }
    void main(){
    	int map[M][M];
    	int visit[2][M-1]={0};
    	INIT_MAP(map);
    	int result=procs(map,visit);
    	//SHOW_MAP(map);
    	SHOW_ROAD(map,visit);
    	printf("最小生成树的权值是%d\n",result);
    }


    测试数据:

    100 6 1 5 100 100
    6 100 5 100 3 100
    1 5 100 5 6 4
    5 100 5 100 100 2
    100 3 6 100 100 6
    100 100 4 2 6 100





    更多相关内容
  • Prim算法计算最小生成树(无向图&邻接矩阵)——C语言实现。
  • def prim(graph, vertex_num): INF = 1 &lt;&lt; 10 visit = [False] * vertex_num dist = [INF] * vertex_num #preIndex = [0] * vertex_num #对所有的顶点进行循环,首先是确定头结点 #找到当前无向...
    # coding:UTF-8
    def prim(graph, vertex_num):
        INF = 1 << 10
        visit = [False] * vertex_num
        dist = [INF] * vertex_num
        #preIndex = [0] * vertex_num
        #对所有的顶点进行循环,首先是确定头结点
        #找到当前无向图的最小生成树
        for i in range(vertex_num):
    
            minDist = INF + 1
            nextIndex = -1
            #第一次循环时,nextIndex就是头结点
            #所以要把minDIst加上1,之后这个循环
            #的功能是找到基于当前i,邻接矩阵中i行到哪一行距离最小的那个位置作为下一个结点,当然前提是那个结点没有去过
            for j in range(vertex_num):
                if dist[j] < minDist and not visit[j]:
                    minDist = dist[j]
                    nextIndex = j
    
            print (nextIndex)
            visit[nextIndex] = True
            #由于前面已经找到了下一个结点了,现在就要构建再下一个结点的dist矩阵了,这就要看当前这个nextIndex这一行了
            for j in range(vertex_num):
                if dist[j] > graph[nextIndex][j] and not visit[j]:
                    dist[j] = graph[nextIndex][j]
                    #preIndex[j] = nextIndex
    
        return dist, #preIndex
    
    
    _ = 1 << 10
    
    graph = [
        [0, 6, 3, _, _, _],
        [6, 0, 2, 5, _, _],
        [3, 2, 0, 3, 4, _],
        [_, 5, 3, 0, 2, 3],
        [_, _, 4, 2, 0, 5],
        [_, _, _, 3, 5, 0],
    ]
    
    prim(graph, 6)
    
    展开全文
  • 邻接表实现Prim算法

    2021-05-27 22:26:38
    Prim算法 Prim算法是通过连通网找最小生成树(mst)的算法 过程: 1.首先选取任意顶点作为树的根 2.遍历其他(不在树中)的顶点,对于每个顶点,找到一条到mst路径最短的边,这样,每个顶点都有一条通往mst的边...

    Prim算法

    Prim算法是通过连通网找最小生成树(mst)的算法
    过程:
    1.首先选取任意顶点作为树的根
    2.遍历其他(不在树中)的顶点,对于每个顶点,找到一条到mst路径最短的边,这样,每个顶点都有一条通往mst的边(不是邻接的就设权值无限大)

    这里路径的意思是两顶点的直接距离,不相邻的顶点,路径距离就是∞,否则就是这条边的权值

    3.在所有的边中,找到权值最小的一条,将对应顶点加入到mst中
    循环2,3(对于n个顶点,循环n-1次)


    例如,求下图的最小生成树
    在这里插入图片描述
    首先,选择v0作为起点,其他顶点到mst的距离分别为[0, 4, ∞, ∞, 3, 1]
    在这里插入图片描述

    从这6条边中选择最小的一条(非零)(v0, v5),将v5加入到mst中:

    在这里插入图片描述


    接着,重复上面步骤,各顶点到mst的最小距离为:[0, 4, 7, 8, 3, 0]
    在这里插入图片描述

    v2从(v2, v0) 和 (v2, v5)中选择了(v2, v5),与树的距离从原来的无穷大更新为7,同样,v3也是这样,从∞更新为8

    从这些边中选择最小的非零边(v0, v4),将v4加入到mst中
    …一直循环,最终结果如下:
    在这里插入图片描述



    代码实现

    使用邻接表来存储图结构:

    typedef struct EdgeNode{
        int adjIndex;   //邻接到下标为adjindex的顶点
        WEIGHT weight;
        struct EdgeNode * next;
    }EdgeNode;			//边节点
    
    typedef struct VertexNode{
        DataElement data;
        int id;
        EdgeNode* firstEdge;
    }VertexNode;		//顶点节点
    
    typedef struct AdjList{
        VertexNode* VerNode[MAXSIZE];
        int verQuantity;    //顶点数量
        int edgeQuantity;   //边数量
    }AdjList;
    

    创建最小生成树需要三个辅助的数组:

    • bool isAdded[MAXSIZE]
    • int lowcost[MAXSIZE]
    • int adjVex[MAXSIZE]

    isAdded储存某个定点是否已经加入到mst中

    这个数组在邻接矩阵表示法中是没有的,因为邻接矩阵中可以用0和INFINITY表示顶点已经加入到mst中以及边权值为无穷大,而在邻接表表示法中只能通过指针指向NULL表示边的权值无穷大,因此需要一个辅助数组isAdded

    lowcost储存某个结点到mst的最短路径

    例如mst中有三个顶点A,B,C,此时一个非mst的顶点D到mst就有三条路径:(A,D),(B,D),(C,D),lowcost[D]储存了最短的一条(B,D)

    adjVex储存mst中各个顶点中到其他顶点路径最短的那个顶点

    比如上例中mst中各个顶点到顶点D最短的为B顶点,则adjVex[D]储存了顶点B

    这三个数组是从算法思路上需要的,具体的实现需要根据实际代码修改

    /** 普里姆算法生成最小生成树 */
    void PrimCreat(AdjList* adj)
    {
        int min;        //最小权值
        int minIndex;   //最小权值的边的下标
        int isAdded[MAXSIZE] = {0};
        EdgeNode*  lowcost[MAXSIZE] = {NULL};                    //保存边的信息,如果为NULL,则表示权值无穷大
        VertexNode* adjVex[MAXSIZE] = {NULL};                    //保存另一顶点信息   Vi 与 Vadjvex[i] 的权值为lowcost[i]
        
        EdgeNode* temp = adj->VerNode[0]->firstEdge;    
        isAdded[0] = 1;
        for(int i = 0; i < adj->verQuantity; i++)               //两个数组的初始化
        {
            adjVex[adj->VerNode[i]->id] = adj->VerNode[0];       //都指向第一个顶点
            if(temp)
            {
                lowcost[temp->adjIndex] = temp;
                temp = temp->next;
            }
        }
    
        for(int i = 0; i < adj->verQuantity - 1; i++)
        {
            min = INFINITY;
            //首先找到lowcost中权值最小的边以及对应的非mst顶点下标
            for(int k = 0; k < adj->verQuantity; k++)
            {
                if(lowcost[k] != NULL && lowcost[k]->weight < min)
                {
                    min = lowcost[k]->weight;
                    minIndex = k;
                }
            }
            //打印
            printf("(%d, %d)%d - ", adjVex[minIndex]->id, minIndex, min);
    
            isAdded[minIndex] = 1;
            //minIndex这个顶点已经加入到mst中了,它与mst的距离为0了(这里没有另一种状态表示距离为0,只能指向NULL)
            //如果没有isAdded这个数组,则不能区分lowcost中NULL是表示距离为0还是距离为无穷大
            lowcost[minIndex] = NULL;
    
            //更新lowcost数组
            //mst中新加了一个顶点,所有的更新都与这个顶点相关,因此用与依附于这个顶点的所有边进行更新
            temp = adj->VerNode[minIndex]->firstEdge;
            while(temp)
            {
                //更新就是找到一条更短的路径,因此对方顶点不在mst中并且权值更小就可以更新
                if(isAdded[temp->adjIndex] != 1 && (lowcost[temp->adjIndex] == NULL || temp->weight < lowcost[temp->adjIndex]->weight))
                {
                    lowcost[temp->adjIndex] = temp;
                    adjVex[temp->adjIndex] = adj->VerNode[minIndex];    //同时更新adjVex数组
                }
                temp = temp->next;
            }
        }
    }
    

    具体的思路都写在注释里面了

    展开全文
  • python--数据结构--邻接矩阵

    千次阅读 2020-08-21 18:06:20
    邻接矩阵 :class VertexNode: 顶点结点类 :class ArcNode: 弧结点类 :class AdjMatrix: 邻接矩阵类 :method create_adj_matrix: 创建一个邻接矩阵对象 :method depth_first_search_recursion: 深度优先递归遍历...
    adj_matrix.py
    """
    邻接矩阵
    
    :class VertexNode: 顶点结点类
    
    :class ArcNode: 弧结点类
    
    :class AdjMatrix: 邻接矩阵类
    
    :method create_adj_matrix: 创建一个邻接矩阵对象
    
    :method depth_first_search_recursion: 深度优先递归遍历
    
    :method depth_first_search_nonrecursion: 深度优先非递归遍历
    
    :method breadth_first_search_nonrecursion: 广度优先非递归遍历
    
    :class TravVistor: 访问者类,对深度优先递归、深度优先非递归、广度优先非递归的访问
    
    :method travers_graph: 遍历接口,设置不同参数利用TravVistor对象实现深度优先递归、深度优先非递归、广度优先非递归调用
    
    :method mini_span_tree_prim: 最小生成树,普利姆算法
    
    :method mini_span_tree_kruskal: 最小生成树,克鲁斯卡尔算法
    
    :method topo_sort: 拓扑排序
    
    :method shortest_path_djs: 迪杰斯特拉算法,计算从某一顶点开始到其余顶点的最短路径
    
    :method shortest_path_floyd: 弗洛伊德算法,计算任意两个顶点之间的最短路径
    
    :method center_vex: 计算中心结点
    """
    
    
    import numpy as np
    from typing import List, Tuple, Union
    from collections import deque
    from array import array
    
    
    # 所创建的图的种类:DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向图
    graph_kind_ = {"DG": 0, "DN": 32768, "UDG": 0, "UDN": 32768}  # 对于有权网此处默认权值范围小于32768
    
    
    class VertexNode:
        def __init__(self, name: str):
            self.name = name  # 顶点结点名
            self.other_info = None
    
    
    class ArcNode:
        def __init__(self, arc_tail: VertexNode, arc_head: VertexNode, weight: Union[int, float]):
            self.arc_head = arc_head  # 该弧弧结点的弧头顶点结点
            self.arc_tail = arc_tail  # 该弧弧结点的弧尾顶点结点
            self.weight = weight  # 弧的权重
            self.other_info = None
    
    
    class AdjMatrix:
        def __init__(self):
            self.vertexs: List = []  # 该邻接矩阵中顶点结点列表
            self.vex_num: int = 0  # 顶点的数量
            self.arc_num: int = 0  # 弧的数量
            self.arcs_matrix: np = None  # 准备创建的邻接矩阵
            self.graph_kind: str = ""  # 该邻接矩阵表示的图的类型
    
    
    def locate_vertex(adj_matrix: AdjMatrix, vertex_node: VertexNode):
        """
        获取顶点的位置
    
        :param adj_matrix: 在该邻接矩阵对象的顶点列表中查找顶点结点位置
        :param vertex_node: 所需查找位置的顶点结点
        :return: 顶点结点的索引
        """
        for index, vertex_node_item in enumerate(adj_matrix.vertexs):
            if vertex_node.name == vertex_node_item.name:
                return index
    
    
    def create_adj_matrix(adj_matrix: AdjMatrix, vertexs: List[VertexNode],
                          arcs: List[Union[Tuple[VertexNode, VertexNode, int], Tuple[VertexNode, VertexNode, float]]],
                          graph_kind: str = 'DN'):
        """
        创建一个邻接矩阵
    
        :param adj_matrix: 一个空的邻接矩阵
        :param vertexs: 顶点列表
        :param arcs: 弧列表
        :param graph_kind: 所创建的图的种类:DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向图
        :return: None
        """
        adj_matrix.vertexs = vertexs  # 设置该邻接矩阵对象的顶点列表
        adj_matrix.arc_num = len(arcs)  # 设置该邻接矩阵对象的弧结点个数
        adj_matrix.vex_num = len(adj_matrix.vertexs)  # 设置该邻接矩阵对象的顶点结点个数
        adj_matrix.graph_kind = graph_kind  # 设置该邻接矩阵对象所表示的图的类型
        adj_matrix.arcs_matrix = np.ones([adj_matrix.vex_num, adj_matrix.vex_num]) * graph_kind_[graph_kind]  # 为该邻接矩阵对象创建邻接矩阵
        for arc in arcs:  # 获得一条弧的两个顶点及权值
            arc_node = ArcNode(*arc)  # 创建弧结点
            i = locate_vertex(adj_matrix, arc_node.arc_tail)  # 获得弧尾结点的位置
            j = locate_vertex(adj_matrix, arc_node.arc_head)  # 获得弧头结点的位置
            if graph_kind == "DN" or graph_kind == "DG":  # 在邻接矩阵中将相应位置设置为弧的权重,相当于建立弧
                adj_matrix.arcs_matrix[i][j] = arc_node.weight
            else:
                adj_matrix.arcs_matrix[i][j] = arc_node.weight
                adj_matrix.arcs_matrix[j][i] = arc_node.weight
        if graph_kind == 'DN' or graph_kind == 'UDN':
            for i in range(adj_matrix.vex_num):
                adj_matrix.arcs_matrix[i][i] = 0
    
    
    visited = array('i', [])  # 访问标志数组
    trav_seq = deque()  # 遍历队列
    
    
    def depth_first_search_recursion(adj_matrix: AdjMatrix, vertex_node: VertexNode):
        """
        深度遍历图
    
        算法思想:
            (1) 访问出发点v0;
            (2) 依次以v0的未被访问的临界点为出发点,深度优先搜索图,直至图中所有与v0有路径相通的顶点都被访问。
    
        :param adj_matrix: 已创建好的邻接矩阵对象
        :param vertex_node: 访问出发点v0
        :return: 深度遍历序列
        """
        vi_index = locate_vertex(adj_matrix, vertex_node)  # 获取当前顶点节点在ad_matrix中的下标
        trav_seq.append(adj_matrix.vertexs[vi_index])   # 访问当前顶点结点,放入访问对列中
        visited[vi_index] = 1  # 将访问过的当前顶点结点标志置为1,表示已访问过
        for vj_index in range(adj_matrix.vex_num):  # 寻找当前结点的所有邻接顶点结点
            # 判断adj_matrix.arcs_matrix[vi_index][vj_index]是否是当前顶点结点的邻接顶点结点,并判断是否被访问过,访问过不能入栈
            if not visited[vj_index] and 0 < adj_matrix.arcs_matrix[vi_index][vj_index] <= graph_kind_['DN']:
                depth_first_search_recursion(adj_matrix, adj_matrix.vertexs[vj_index])  # 对当前顶点结点的邻接点顶点结点进行深度遍历
        return trav_seq  # 返回深度遍历序列
    
    
    def depth_first_search_nonrecursion(adj_matrix: AdjMatrix, vertex_node: VertexNode):
        """
        深度非递归遍历图
    
        算法思想:
            (1) 首先将v0入栈
            (2) 只要栈不空,则重复下述处理:栈顶顶点出栈,如果未访问,则访问并置访问标志;然后将该顶点所有未访问的邻接点入栈。
    
        :param adj_matrix: 已创建好的邻接矩阵对象
        :param vertex_node: 访问出发点v0
        :return: 深度遍历序列
        """
        temp_stack = deque()  # 栈
        temp_stack.append(vertex_node)  # 将起始顶点结点入栈
        while temp_stack:  # 循环直到栈为空为止
            vi_node = temp_stack.pop()  # 将栈顶顶点结点出栈成为当前结点
            vi_index = locate_vertex(adj_matrix, vi_node)   # 获取当前顶点结点在邻接表adj_list的顶点列表中的下标
    
            if not visited[vi_index]:  # 判断当前顶点结点是否被访问过,对于同一个顶点结点栈中可能出现多次,重复出现的在第一次出栈的时候已被访问过
                trav_seq.append(vi_node)  # 将当前顶点结点放入访问队列
                visited[vi_index] = 1  # 将当前顶点节点设置为1,表示已被访问
                for vj_index in range(adj_matrix.vex_num):  # 将所有以当前顶点结点为弧尾顶点结点的的弧的弧头结点入栈
                    # 判断adj_matrix.arcs_matrix[vi_index][vj_index]是否是当前顶点结点的邻接顶点结点,并判断是否被访问过,访问过不能入栈
                    if not visited[vj_index] and 0 < adj_matrix.arcs_matrix[vi_index][vj_index] <= graph_kind_["DN"]:
                        temp_stack.append(adj_matrix.vertexs[vj_index])
        return trav_seq  # 返回以当前顶点结点为起始节点的深度遍历序列
    
    
    def breadth_first_search_nonrecursion(adj_matrix: AdjMatrix, vertex_node: VertexNode):
        temp_queue = deque()  # 队列
        temp_queue.append(vertex_node)  # 将起始顶点结点入对
        while temp_queue:  # 循环直到队列为空为止
            vi_node = temp_queue.popleft()  # 将栈顶顶点结点出对成为当前结点
            vi_index = locate_vertex(adj_matrix, vi_node)  # 获取当前顶点结点在邻接表adj_list的顶点列表中的下标
            if not visited[vi_index]:  # 判断当前顶点结点是否被访问过,对于同一个顶点结点对中可能出现多次,重复出现的在第一次出对的时候已被访问过
                trav_seq.append(vi_node)  # 将当前顶点结点放入访问队列
                visited[vi_index] = 1  # 将当前顶点节点设置为1,表示已被访问
                for vj_index in range(adj_matrix.vex_num):  # 将所有以当前顶点结点为弧尾顶点结点的的弧的弧头结点入对
                    # 判断adj_matrix.arcs_matrix[vi_index][vj_index]是否是当前顶点结点的邻接顶点结点,并判断是否被访问过,访问过不能入对
                    if not visited[vj_index] and 0 < adj_matrix.arcs_matrix[vi_index][vj_index] <= graph_kind_["DN"]:
                        temp_queue.append(adj_matrix.vertexs[vj_index])
        return trav_seq  # 返回以当前顶点结点为起始节点的广度遍历序列
    
    
    class TravVistor:
        """
        遍历访问者
    
        访问者设计模式:使用同一个方法对不同对象访问具有不同的行为
        对不同的遍历方法使用同一个方法traver_graph进行遍历
        """
        __recursion_nonrecursion = {"r": "recursion", "nr": "nonrecursion"}  # 递归遍历与非递归遍历
        __depth_breadth = {"d": "depth", "b": "breadth"}
    
        def __init__(self, adj_list, vertex_node, depth_breadth: str, recursion_nonrecursion: str):
            self.adj_list = adj_list
            self.vertex_node = vertex_node
            self.depth_breadth = depth_breadth
            self.recursion_nonrecursion = recursion_nonrecursion
    
        def traver_graph(self):
            func_name = f'{self.__depth_breadth[self.depth_breadth]}_first_search_{self.__recursion_nonrecursion[self.recursion_nonrecursion]}'
            func_obj = getattr(self, func_name, None)
            return func_obj()
    
        def depth_first_search_recursion(self):
            return depth_first_search_recursion(self.adj_list, self.vertex_node)
    
        def depth_first_search_nonrecursion(self):
            return depth_first_search_nonrecursion(self.adj_list, self.vertex_node)
    
        def breadth_first_search_nonrecursion(self):
            return breadth_first_search_nonrecursion(self.adj_list, self.vertex_node)
    
    
    def travers_graph(adj_matrix: AdjMatrix, deepth_breadth: str = "d", recursion_nonrecursion: str = "nr"):
        """
        遍历图
    
        算法思想:
            若是非连通图,则途中一定还有顶点未被访问,需要从途中另选一个未被访问过的顶点作为起始顶点,重复深度优先搜索过程,
            直至图中所有的顶点均被访问过为止。
    
        :param adj_list: 已创建好的邻接表对象
        :param deepth_breadth: 选用深度deepth_breadth = 'd', 选用广度deepth_breadth = 'b'
        :param recursion_nonrecursion: 选用递归way = 'r' ,选用非递归way = 'nr'
        :return: 返回多个连通子图的遍历序列
        """
        travers_list = deque()
        for vi_index in range(adj_matrix.vex_num):  # 初始化visited
            visited.append(0)
        for vi_index in range(adj_matrix.vex_num):  # 循环调用遍历方法来遍历连通子图的操作,若图adj_list是连通图,则此调用只执行一次
            if not visited[vi_index]:
                trav_vistor = TravVistor(adj_matrix, adj_matrix.vertexs[vi_index], deepth_breadth,
                                         recursion_nonrecursion)  # 创建一个遍历访问者对象
                travers_list.append(trav_vistor.traver_graph().copy())  # 将遍历结果添加到travers_list
            trav_seq.clear()  # 清空trav_seq,以便下一轮的使用
        return travers_list  # 返回多个连通子图的遍历序列
    
    
    def min_(closedage) -> int:
        temp_weight = 32768
        temp_index = 0
        # print(closedage)
        for i in range(0, len(closedage)):
            if closedage[i][1] != 0 and temp_weight > closedage[i][1]:
                # print(temp_index, temp_weight)
                temp_weight = closedage[i][1]
                temp_index = i
        return temp_index
    
    
    def mini_span_tree_prim(adj_matrix: AdjMatrix, vertex_start: VertexNode):
        """
        最小生成树:普利姆算法:加点法,适用于稠密网
    
        算法思想:
            (1) 首先将初始顶点vertex_start加入到U中,对其余的每一个顶点i,将closedge[i]初始化为i到vertex_start边信息;
            (2) 循环n-1次,做如下处理:
                a. 从各组最小边closedge[v]中选出最小的最小边closedge[k](v,k属于V-U)
                b. 将k加入到U中
                c. 更新剩余的每组最小边信息closedge[v](v属于V-U)
    
        #closedge[v] = List[List[adjvex, lowcost]]
            a. adjvex 记录最小边在U中的那个顶点
            b. lowcost 存储最小边的权值
    
        算法时间复杂度:
            由于算法中有两个for循环嵌套,故它的时间复杂度为O(n**2)
    
        :param adj_matrix:
        :param vertex_start:
        :return:
        """
        vk_index = locate_vertex(adj_matrix, vertex_start)
        vex_num = adj_matrix.vex_num
        closedage = []
        edges = deque()
        for i in range(vex_num):  # 初始化closedge
            if i == vk_index:
                closedage.append([adj_matrix.vertexs[vk_index], 0])
            else:
                closedage.append([adj_matrix.vertexs[vk_index], adj_matrix.arcs_matrix[vk_index][i]])
    
        for i in range(1, vex_num):  # 找n-1条边
            k = min_(closedage)  # closedge[k]中存有当前最小边(arc_tial, arc_head)的信息
            arc_tail = closedage[k][0]  # arc_tail属于U
            arc_head = adj_matrix.vertexs[k]  # arc_head属于V-U
            edges.append((arc_tail, arc_head, closedage[k][1]))  # 保存生成树的当前最小边(arc_tial, arc_head, weight)
            closedage[k][1] = 0  # 将顶点arc_tail纳入U集合
            for j in range(vex_num):  # 在顶点arc_tail编入U之后,更新closedge[j]
                if adj_matrix.arcs_matrix[k][j] < closedage[j][1]:
                    closedage[j][1] = adj_matrix.arcs_matrix[k][j]
                    closedage[j][0] = arc_head
        return edges
    
    
    def adj_matrix_arcs(adj_matrix: AdjMatrix):
        # 此函数可进行进一步优化,此处只是为了实现功能,因对于UDG和UDN来说,邻接矩阵是对称阵,用以下算法会占用两倍的空间
        arcs = []
        if adj_matrix.graph_kind == "UDG" or adj_matrix.graph_kind =="DG":
            for i in range(adj_matrix.vex_num):
                for j in range(adj_matrix.vex_num):
                    if adj_matrix.arcs_matrix[i][j] == 1:
                        arcs.append((adj_matrix.vertexs[i], adj_matrix.vertexs[j], 1))
        else:
            for i in range(adj_matrix.vex_num):
                for j in range(adj_matrix.vex_num):
                    if adj_matrix.arcs_matrix[i][j] < 32768:
                        arcs.append((adj_matrix.vertexs[i], adj_matrix.vertexs[j], adj_matrix.arcs_matrix[i][j]))
        return arcs
    
    
    def mini_span_tree_kruskal(adj_matrix: AdjMatrix):
        """
        最小生成树:克鲁斯卡尔算法:加边发,适合于稀疏网
    
        算法思想:
            假设N = (V, {#})是联通图,将N中的边按边权值从小到大的顺序排列。
            (1) 将n个顶点看成n个集合。
            (2) 按权值由小到大的顺序选择边,所选边应满足两个顶点不在同一个顶点集合内,将改变放到生成树边的集合中,同时将该边的
                两个顶尖所在的顶点集合合并
            (3) 重复(2)直到所有的顶点都在同一个顶点集合内
    
        算法时间复杂度:
            克鲁斯卡尔算法的时间复杂度主要由排序方法决定,而克鲁斯卡尔算法的排序方法只与网中边的条数有关,而与网中顶点的个数无
            关,当使用时间复杂度为O(elog2e)的排序方法时,克鲁斯卡尔算法的时间复杂度即为O(log2e),因此当网的顶点个数较多、
            而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果较好
        :param adj_matrix: 邻接矩阵
        :return: 最小生成树的边序列
        """
        awaited_edges = adj_matrix_arcs(adj_matrix)  # 从邻接矩阵中获取所有的边
        vex_index_dict = {}  # 用于存放邻接矩阵中顶点结点在其顶点列表vertexs中元素与索引的键值对,因所编写的并查集只接受数值型和字符串类型的值
        for index, vertex_node in enumerate(adj_matrix.vertexs):  # 初始化vex_index_dict
            vex_index_dict.setdefault(vertex_node, index)
        from mf_set import MFSet, SeqList
        vex_set = MFSet()  # 并查集对象,包含了所有顶点集合之间的关系
        vex_set.initialization(SeqList([i for i in range(index+1)]))  # 初始化vex_set
        tree_edges = deque()  # 用于保存最小生成树的边序列
        abc = lambda edge: edge[2]  # 表示按边的权重降序排序
        awaited_edges = sorted(awaited_edges, key=abc, reverse=True)  # 对边按权重进行降序排序
        while awaited_edges:  # 生成n-1条边,权值最小
            edge_min = awaited_edges.pop()  # 获取权重最小的一条边
            i = vex_set.find_2(vex_index_dict[edge_min[0]])  # 查找当前边中一个顶点所在树的根
            j = vex_set.find_2(vex_index_dict[edge_min[1]])  # 查找当前边中另一个顶点所在树的根
            if i == j:  # 当前边的两个端点位于同一个顶点集中,出现回路,抛弃该边
                continue
            tree_edges.append(edge_min)  # 将当前边放入最小生成树的边序列
            vex_set.merge(i, j)  # 合并当前边的两个端点所在的顶点集
        return tree_edges  # 返回最小生成树的边序列
    
    
    def find_id(adj_matrix: AdjMatrix, indegree: array):
        for i in range(adj_matrix.vex_num):
            indegree.append(0)
        for arc_head_index in range(adj_matrix.vex_num):
            for arc_tail_index in range(adj_matrix.vex_num):
                if adj_matrix.arcs_matrix[arc_tail_index][arc_head_index] == 1:
                   indegree[arc_head_index] += 1
        return indegree
    
    
    def topo_sort(adj_matrix: AdjMatrix):
        """
        拓扑排序:邻接矩阵
    
        拓扑排序:
            在有向图G=(V, {E})中,V中顶点的线性序列(vi1,vi2,vi3,...,vin)称为拓扑序列。如果此序列满足条件:对序列中任意两个顶点
            vi,vj,在G中有一条从vi到vj的路径,则在序列中vi必排在vj之前。
    
        拓扑排序基本思想:
            (1) 从有向图中选一个无前驱的结点输出;
            (2) 将此结点和以它为起点的边删除
            (3) 重复(1)(2),直到不存下来无前驱的结点
            (4) 若此时输出的结点数小于有向图的顶点数,则说明有向图中存在回路,否则输出的顶点顺序即为一个拓扑序列
    
        基于邻接矩阵的存储结构:
            此时入度为0的顶点即没有前驱的顶点,因此可以附设一个存放各顶点入度的数组indegree[],于是有:
                (1) 找G中无前驱的顶点--查找indegree[i]为零的顶点i;
                (2) 删除以i为起点的所有弧--对链在顶点i后面的所有临界顶点k,将对应的indegree[k]减1
                为了避免重复检测入读为0的顶点,可以再设置一个辅助栈,若某一顶点的入度减为0,则将它入栈,每当输出
                某一顶点时,便将它从栈种删除。
    
        算法思想:
            (1) 首先求出各顶点的入度,并将入度为0的顶点入栈。
            (2) 只要栈不空,则重复下面处理:
                a. 将栈顶顶点i出栈并打印
                b. 将栈顶顶点i的每一个邻接点k的入度减1,如果顶点k的入度变为0,则将顶点k入栈。
    
        算法时间复杂度:
            若有向无环图有n个顶点和e条弧,则在拓扑排序的算法中,for循环需要执行n次,时间复杂度为O(n);对于while循
            环,由于每一顶点必定出栈一次,出一次栈,其时间复杂度为O(n),每次都有一个n列的循环;故该算法的时间复杂
            度为O(n+n**2),即O(n**2)
    
        :param adj_matrix:  需要拓扑排序的邻接矩阵
        :return: 拓扑排序序列
        """
        indegree = array('i', [])  # 入度计数
        temp_stack = deque()  # 辅助栈,避免重复检测入度为0的顶点
        vex_seq = deque()  # 用于保存排好序的顶点结点
        counter = 0  # 用于记录顶点个数,便于最后判断AOV网中是否存在回路
        indegree = find_id(adj_matrix, indegree)
        for index, value in enumerate(indegree):  # 初始化temp_stack
            if value == 0:
                temp_stack.append((adj_matrix.vertexs[index], index))  # 将入度为0的结点及其在adj_matrix.vertexs列表中的下标构成一个元组入栈
                indegree[index] -= 1  # 若没有此语句当有多个入度为0的顶点时,在进入出栈访问时,会导致重复入栈
        while temp_stack:  # 循环直到栈为空为止
            vertex_node_index = temp_stack.pop()  # 栈顶顶点出栈
            vex_seq.append(vertex_node_index[0])  # 访问当前顶点,进行保存
            counter += 1  # 计数,当前顶点是序列中的第几个顶点
            arc_tail_index = vertex_node_index[1]
            for arc_head_index in range(adj_matrix.vex_num):
                if adj_matrix.arcs_matrix[arc_tail_index][arc_head_index] == 1:  # 为1表示两个顶点结点之间有弧
                    indegree[arc_head_index] -= 1
                if indegree[arc_head_index] == 0:
                    # 表示adj_list.vertexs[arc_head_index]该顶点结点已没有前驱结点需对其入栈
                    temp_stack.append((adj_matrix.vertexs[arc_head_index], arc_head_index))
                    indegree[arc_head_index] -= 1  # 当在该轮出栈访问循环中有多个减为0入栈的顶点时,如果没有此语句在下轮出栈访问时会导致重复入栈
        if counter < adj_matrix.vex_num:  # 判断AOV网中是否存在回路
            return "ERROR"  # 表示AOV网中存在回路
        return vex_seq  # 成功返回拓扑序列
    
    
    def min__(dist) -> int:
        min_value = graph_kind_['DN']
        min_p = None
        for index, value in enumerate(dist):
            if value and min_value > value:
                min_value = value
                min_p = index
        print(min_p, )
        return min_p
    
    
    def shortest_path_djs(adj_matrix: AdjMatrix, vertex_node: VertexNode):
        """
        迪杰斯特拉算法:邻接矩阵
    
        最短路径:求一个顶点到其他各顶点的最短路径
    
            算法中使用了辅助数组dist[],dist[i]表示目前已经找到的、从开始点v0到终点vi的当面最短路径的长度。它的初值为:如
        果v0到vi有弧,则dist[i]为弧的权值;否则dist[i]为 ∞。
            长度最短的一条最短路径必为(v0,vk),vk满足如下条件:
                dist[k] = Min{dist[i]|vi∈V-S}
            求得顶点vk的最后路径后,将vk加入到第一组顶点集S中。
            每加入一个新的顶点vk到顶点集S中,对第二组剩余的各个顶点而言,就多了一个"中转"结点,从而多了一个"中转"路径,所
        以要对第二组剩余的各个顶点的最短路径长度dist[i]进行修正。
            原来v0到vi的最短路径长度为dist[i],加紧vk后,已vk作为中间顶点的"中转"路径长度为dist[k]+wki,(wki为弧<vk, vi>上
        的权值),若“中转”路径长度小于dist[i],则将顶点vi的最短路径长度修正为“中转”路径长度。
            修正后,在选择数组dist[]中最小的顶点加入到第一组顶点集S中,如此进行下去,直到图中所有顶点都加入到第一组顶点集S
        中为止。
            另外,为了记录从v0出发到其余各点的最短路径(顶点序列),引进辅助数组paths[],path[i]表示目前已经找到的、从开始点
        v0到终点vi的当前最短路径顶点序列。它的初值为:如果从v0到vi有弧,则path[i]为(v0,vi);否则path[i]为空。
    
        算法思想:
            (1) S←{v0};
                dist[i] = g.arcs[v0][vi].adj(vi∈V-S)
                (将v0到其余顶点的最短路径长度初始化为权值)
            (2) 选择vk,使得dist[k] = Min(dist[i]|vi∈V-S),vk为目前求得的下一条从v0出发的最短路径的终点;
            (3) 将vk加入S;
            (4) 修正从v0出发到集合V-S上任一顶点vi的最短路径的长度;
                从vo出发到集合V-S上任一顶点vi的当前最短路径的长度为dist[i],
                从v0出发,中间经过新加入S的vk,然后到达集合V-S上任一顶点vi的路径长度为:
                    dist[k]+g.arcs[k][i].adj
                如果dist[k] + g.arcs[k][i].adj < dist[i],则dist[i]=dist[k] + g.arcs[k][i].adj。
            (5) 重复(2)-(4)共n-1次,即可按最短路径长度的递增循序,主格求出v0到途中其他每个顶点的最短路径。
    
        算法时间复杂度:
            算法前半部分完成了对向量最短路径长度dist[]、路径path[]及顶点集S的初始化工作。
            算法后半部分通过n-1次循环,将第二组顶点集V-S中的顶点按照递增有序方式加入到集合S中,并求得从顶
        点v0出发到达图中其余顶点的最短路径。
            显然,算法的时间复杂度为O(n**2)
    
        :param adj_matrix: 创建好的邻接矩阵对象,即图g
        :param vertex_node: 起始顶点
        :return: paths, paths_weight
        """
        paths = deque()  # 存放起始顶点到达不同顶点的路径,一个二维列表
        paths_weight = deque()  # 存放起始顶点到达不同顶点的路径长度
        dist = deque()  # 辅助列表
        for i in range(adj_matrix.vex_num):  # 为初始化作准备
            paths.append(deque())
            paths_weight.append(None)
            dist.append(0)
        vertex_index = locate_vertex(adj_matrix, vertex_node)  # 获取起始顶点在adj_matrix.vertexs中的下标
        for i in range(adj_matrix.vex_num):  # 初始化
            if vertex_index == i:  # 开始时将起始顶点移入S集合
                dist[i] = None   # 对于移入S集的顶点dist[i]设置为None,避免多次被访问
                paths[i].append(adj_matrix.vertexs[i])  # 将起始顶点自身作为其路径,加入其路径序列
                paths_weight[i] = 0  # 起始顶点路径长度为0,并保存
            else:  # 对非起始顶点进行初始化操作
                dist[i] = adj_matrix.arcs_matrix[vertex_index][i]  # 非起始顶点的dist[i]为起始顶点到该顶点弧权,无弧的此处默认为32768
                if adj_matrix.arcs_matrix[vertex_index][i] < graph_kind_['DN']:  # 初始化从起始顶点到每个可达的非起始顶点路径
                    paths[i].append(adj_matrix.vertexs[vertex_index])  # 起始顶点作为路径的第一个顶点
                    paths[i].append(adj_matrix.vertexs[i])  # 非起始顶点作为路径的第二个顶点
    
        for i in range(adj_matrix.vex_num):  # 循环n-1次,因计算的是从起始顶点到其余n-1各顶点的最短路径
            arc_tail_index = min__(dist)  # 从dist中获取路径长度最小的下标
            if not arc_tail_index:  # 下标返回None时表明从起始顶点到其余n-1各顶点的最短路径已计算完成
                return paths, paths_weight  # 返回计算结果
    
            for arc_head_index in range(adj_matrix.vex_num):  # 对还未访问到的非起始节点的dist[i]以及paths[i]进行修改
                if dist[arc_head_index] and adj_matrix.arcs_matrix[arc_tail_index][arc_head_index] < graph_kind_['DN'] \
                        and dist[arc_tail_index] + adj_matrix.arcs_matrix[arc_tail_index][arc_head_index] < \
                        dist[arc_head_index]:  # 满足条件的才可修改
                    dist[arc_head_index] = dist[arc_tail_index] + adj_matrix.arcs_matrix[arc_tail_index][arc_head_index]
                    paths[arc_head_index] = paths[arc_tail_index].copy()
                    paths[arc_head_index].append(adj_matrix.vertexs[arc_head_index])  # 结点自身作为路径的终止点
            paths_weight[arc_tail_index] = dist[arc_tail_index]  # 保存路径长度
            dist[arc_tail_index] = None  # 修改已访问过的非起始顶点结点dist[i]值,避免被多次访问
    
    
    def shortest_path_floyd(adj_matrix: AdjMatrix):
        """
        求任一对顶点间的最短路径:弗洛伊德算法:邻接矩阵
    
        算法思想:
            设g用邻接矩阵表示,求图g中任意对顶点vi与vj间的最短路径(以下序号是D,P两个矩阵的下表)
            (-1)将vi到vj的最短的路径长度初始化为g.arcs[i][j].adj,然后进行如下n次比较和修正:
            (0) 在vi与vj间加入顶点v0,得到(vi,v0,vj)和(vi,vj)的路径长度,取其中较短的路径作为vi到vj的且中间顶点号
                不大于0的最短路径。
            (1) 在vi与vj间加入顶点v1,得到(vi,...,v1)和(v1,...,vj),其中(vi,...,v1)是vi到v1的且中间顶点号不大于0的最
                短路径,(v1,...,v1,...,vj)与上一步已求出的且vi到vj中间顶点号不大于0的最短路径比较,取其中较短的路径
                作为vi到vj的且中间顶点号不大于1的最短路径
            (2) 在vi与vj间加入顶点v2,得(vi,...,v2)和(v2,...,vj),其中(vi,...,v2)是vi到v2的且中间顶点号不大于1的最
                短路径,(v2,...,vj)是v2到vj的且中间顶点号不大于1的最短路径,这两条路径在上一步中已求出。将(vi,...,v2,
                ...,vj)与上一步已求出的且vi到vj中间顶点号不大于1的最短路径比较,取其中较短的路径作为vi到vj的且中间顶
                点号不大于2的最短路径。
                ..........
                以此类推,经过n次比较和修正,在第n-1步,将求得vi到vj的且中间顶点号不大于n-1的最短路径,这必是从vi到vj
            的最短路径。
                图g中所有顶点偶对vi与vj间的最短路径长短对应一个n阶方阵D。在上述N+1步中,D的值不断变化,对应一个n阶方
            阵序列。
    
        算法时间复杂度:
            O(n**3)
    
        :param adj_matrix:  已创建好的邻接矩阵
        :return:  返回各路径与路径长度信息
        """
        paths = deque()  # 用于存放路径
        dist = adj_matrix.arcs_matrix.copy()  # 初始化dist
        for i in range(adj_matrix.vex_num):  # 初始化paths
            paths.append(deque())
            for j in range(adj_matrix.vex_num):
                paths[i].append(deque())
                if adj_matrix.arcs_matrix[i][j] < graph_kind_['DN'] and adj_matrix.arcs_matrix[i][j] != 0:
                    paths[i][j].append(adj_matrix.vertexs[i])  # 将弧尾顶点结点保存到路径中
                    paths[i][j].append(adj_matrix.vertexs[j])  # 将弧头顶点结点保存到路径中
    
        for k in range(adj_matrix.vex_num):  # 共n个顶点,每次循环将一个顶点作为两个不同结点之间的连接顶点
            for i in range(adj_matrix.vex_num):  # dist 共n行
                for j in range(adj_matrix.vex_num):  # dist 共n列
                    if k == i or k == j or i == j:
                        continue
                    weight_i_k_j = dist[i][k] + dist[k][j]  # 以vk作为中间连接点计算从vi到vk的路径长度
                    if weight_i_k_j < dist[i][j]:
                        # 以vk作为中间连接点从vi到vk的路径长度小于从vi到vk的原路径长度,需要更新dist[i][j],path[i][j]
                        dist[i][j] = weight_i_k_j
                        temp_path = paths[i][k].copy()  # 注意必须copy(),否则在更新过程中会出错
                        temp_path.pop()  # 因paths[i][k]的最后一个顶点结点与paths[k][j]的第一个顶点结点重复
                        temp_path.extend(paths[k][j].copy())  # 注意必须copy(),否则在更新过程中会出错
                        paths[i][j] = temp_path
        return paths, dist  # 返回各路径与路径长度信息
    
    
    def center_vex(adj_list: AdjMatrix):
        paths, path_weight = shortest_path_floyd(adj_list)
        temp_row_index = 0
        temp_row_sum = graph_kind_['DN']*adj_list.vex_num
        path_row_sum = 0
        for row in range(adj_list.vex_num):
            for col in range(adj_list.vex_num):
                path_row_sum += path_weight[row][col]
            if temp_row_sum > path_row_sum:
                temp_row_sum = path_row_sum
                temp_row_index = row
        return adj_list.vertexs[temp_row_index], paths[temp_row_index], path_weight[temp_row_index], temp_row_sum
    
    test_adj_matrix.py
    from graph.adj_matrix import VertexNode, ArcNode, AdjMatrix, create_adj_matrix, travers_graph, mini_span_tree_prim, \
        mini_span_tree_kruskal, topo_sort, shortest_path_djs, shortest_path_floyd, center_vex
    
    
    if __name__ == '__main__':
        # v1 = VertexNode('v1')
        # v2 = VertexNode('v2')
        # v3 = VertexNode('v3')
        # v4 = VertexNode('v4')
        # v5 = VertexNode('v5')
        # v6 = VertexNode('v6')
        #
        # arc1 = (v1, v2, 5)
        # arc2 = (v1, v4, 7)
        # arc3 = (v2, v3, 4)
        # arc4 = (v3, v1, 8)
        # arc5 = (v3, v6, 9)
        # arc6 = (v4, v3, 5)
        # arc7 = (v4, v6, 6)
        # arc8 = (v5, v4, 5)
        # arc9 = (v6, v1, 2)
        # arc10 = (v6, v5, 1)
        #
        # adj_martix = AdjMatrix()
        # vertexs = [v1, v2, v3, v4, v5, v6]
        # arcs = [arc1, arc2, arc3, arc4, arc5, arc6, arc7, arc8, arc9, arc10]
        # create_adj_matrix(adj_martix, vertexs, arcs, 'DN')
        # print(adj_martix.arcs_matrix)
        # travs_list = travers_graph(adj_martix, 'b', 'nr')
        # for trav_seq in travs_list:
        #     for vertex_node in trav_seq:
        #         print(vertex_node.name)
    
        # v1 = VertexNode('v1')
        # v2 = VertexNode('v2')
        # v3 = VertexNode('v3')
        # v4 = VertexNode('v4')
        # v5 = VertexNode('v5')
        # v6 = VertexNode('v6')
        #
        # arc1 = (v1, v2, 6)
        # arc2 = (v2, v5, 3)
        # arc3 = (v5, v6, 6)
        # arc4 = (v4, v6, 2)
        # arc5 = (v1, v4, 5)
        # arc6 = (v1, v3, 1)
        # arc7 = (v2, v3, 5)
        # arc8 = (v5, v3, 6)
        # arc9 = (v6, v3, 4)
        # arc10 = (v4, v3, 5)
        #
        # adj_matrix = AdjMatrix()
        # vertexs = [v1, v2, v3, v4, v5, v6]
        # arcs = [arc1, arc2, arc3, arc4, arc5, arc6, arc7, arc8, arc9, arc10]
        # create_adj_matrix(adj_matrix, vertexs, arcs, 'UDN')
        # edges = mini_span_tree_kruskal(adj_matrix)
        # for edge in edges:
        #     print((edge[0].name, edge[1].name, edge[2]))
    
        # 测试torpo_sort方法
        # v1 = VertexNode('v1')
        # v2 = VertexNode('v2')
        # v3 = VertexNode('v3')
        # v4 = VertexNode('v4')
        # v5 = VertexNode('v5')
        # v6 = VertexNode('v6')
        #
        # arc1 = (v1, v2, 1)
        # arc2 = (v1, v3, 1)
        # arc3 = (v1, v4, 1)
        # arc4 = (v4, v5, 1)
        # arc5 = (v6, v4, 1)
        # arc6 = (v6, v5, 1)
        # arc7 = (v3, v5, 1)
        # arc8 = (v3, v2, 1)
        #
        # adj_matrix = AdjMatrix()
        # vertexs = [v1, v2, v3, v4, v5, v6]
        # arcs = [arc1, arc2, arc3, arc4, arc5, arc6, arc7, arc8]
        # create_adj_matrix(adj_matrix, vertexs, arcs, 'DG')
        # topo_seq = topo_sort(adj_matrix)
        # # print(topo_seq)
        # topo_seq = ",".join([vertex_node.name for vertex_node in topo_seq])
        # print(topo_seq)
    
        # 测试迪杰斯特拉算法
        # v0 = VertexNode('v0')
        # v1 = VertexNode('v1')
        # v2 = VertexNode('v2')
        # v3 = VertexNode('v3')
        # v4 = VertexNode('v4')
        # v5 = VertexNode('v5')
        #
        # arc1 = (v0, v1, 50)
        # arc2 = (v0, v2, 10)
        # arc3 = (v0, v4, 45)
        # arc4 = (v1, v2, 15)
        # arc5 = (v1, v4, 10)
        # arc6 = (v2, v0, 20)
        # arc7 = (v2, v3, 15)
        # arc8 = (v3, v1, 20)
        # arc9 = (v3, v4, 35)
        # arc10 = (v4, v3, 30)
        # arc11 = (v5, v3, 3)
        #
        # adj_matrix = AdjMatrix()
        # vertexs = [v0, v1, v2, v3, v4, v5]
        # arcs = [arc1, arc2, arc3, arc4, arc5, arc6, arc7, arc8, arc9, arc10, arc11]
        # create_adj_matrix(adj_matrix, vertexs, arcs, 'DN')
        # # print(topo_seq)
        # paths, paths_weight = shortest_path_djs(adj_matrix, v0)
        # # print(paths)
        # for i in range(adj_matrix.vex_num):
        #     # print(paths[i])
        #     # if len(paths[i]) != 0:
        #     # print(','.join([vex_node.name for vex_node in paths[i]]))
        #     print((','.join([vex_node.name for vex_node in paths[i]]), paths_weight[i]))
    
        # 测试弗洛伊德算法
        # v0 = VertexNode('A')
        # v1 = VertexNode('B')
        # v2 = VertexNode('C')
        #
        # arc1 = (v0, v1, 4)
        # arc2 = (v1, v0, 12)
        # arc3 = (v1, v2, 5)
        # arc4 = (v2, v0, 6)
        #
        #
        # adj_matrix = AdjMatrix()
        # vertexs = [v0, v1, v2]
        # arcs = [arc1, arc2, arc3, arc4]
        # create_adj_matrix(adj_matrix, vertexs, arcs, 'DN')
        # # print(topo_seq)
        # paths, paths_weight = shortest_path_floyd(adj_matrix)
        # # print(paths)
        # print(paths_weight)
        # for i in range(adj_matrix.vex_num):
        #     for j in range(adj_matrix.vex_num):
        #         if paths[i][j]:
        #             print(','.join([vex_node.name for vex_node in paths[i][j]]), paths_weight[i][j])
    
        # 测试寻找中心点center_vex算法
        v0 = VertexNode('A')
        v1 = VertexNode('B')
        v2 = VertexNode('C')
    
        arc1 = (v0, v1, 4)
        arc2 = (v1, v0, 12)
        arc3 = (v1, v2, 5)
        arc4 = (v2, v0, 6)
    
        adj_matrix = AdjMatrix()
        vertexs = [v0, v1, v2]
        arcs = [arc1, arc2, arc3, arc4]
        create_adj_matrix(adj_matrix, vertexs, arcs, 'UDN')
        centre_vertex, paths, paths_weight, sum_weight = center_vex(adj_matrix)
        print((centre_vertex.name, sum_weight))
        print("具体每条路径".center(50, '*'))
        for i in range(adj_matrix.vex_num):
            if paths[i]:
                print(','.join([vex_node.name for vex_node in paths[i]]), paths_weight[i])
    
    展开全文
  • 针对城市之间建路问题和造桥问题,需要计算最小生成树来获取最小成本,Prim算法就是提供的策略之一
  • Python附代码)Prim算法最小生成树(贪心算法) 一、问题描述 【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。 ...
  • 文章目录库的版本号最小生成树的知识点PRIM算法Kruskal算法 库的版本号 列了这个是因为在学习过程中,会有很多文章,可能时间稍微久点了,用起来因为版本迭代,函数可能发生了变化,但你也不确实到底是什么问题。。...
  • Python实现最小生成树--Prim算法和Kruskal算法

    千次阅读 热门讨论 2020-06-21 21:01:22
    Python实现最小生成树–Prim算法和Kruskal算法 文章目录Python实现最小生成树--Prim算法和Kruskal算法前言设计需求分析系统设计系统实现Prim算法Kruskal算法功能介绍测试数据及代码测试数据完整代码参考文章 前言 ...
  • Pythonprim与kruskal最小生成树算法

    千次阅读 2019-04-13 10:20:17
    普里姆算法(Prim’s algorithm): ...prim算法基本思路: 所有节点分成两个group,一组为已经选取的selected_node(为list类型),一组为candidate_node,首先任取一个节点加入到selected_node,然后...
  • 最小生成 import copy MAXV=100 #表示最多顶点个数capacity ...class MatchGraph: #构建图邻接矩阵类,调用方法是 def __init__(self,n=0,e=0): #构造方法,n表示点node,e表示边edge self.edges
  • """有权稠密图 - 邻接矩阵""" def __init__ (self, n, directed) : self.n = n # 图中的点数 self.m = 0 # 图中的边数 self.directed = directed # bool值,表示是否为有向图 self.g = [[ None ...
  • python实现最小生成树--Prim算法

    千次阅读 2017-09-27 16:55:40
    一、从Excel导入邻接矩阵 import xlrd import sys def matrix(address): #读取excel生成邻接矩阵 wb = xlrd.open_workbook(address) sheet1 = wb.sheet_by_name('邻接矩阵_距离') L = [] for i in range(1,13...
  • //邻接矩阵的顶点也可以用这个 ArcNode firstarc ; char info ; } package Heap ; class ArcNode { int adjvex ; ArcNode nextarc ; int weight ; //weight就是adjlist[?]->...
  • python数据挖掘系列教程 最小生成树MST 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 也就是说,用原图中有的边,连接n个节点,保证每...
  • Sample Input 1 6 7 0 0 3 0 4 1 4 1 5 2 3 2 4 3 5 Output 0 3 4 2 5 1 Hint 实现邻接矩阵储存图,邻接矩阵存的一般是数据较少且比较稠密的图,它可以用结构体数组,也可以直接用数组,另外BFS思想很简单,就是...
  • PRIM算法,求最小生成树 ***************************************************************/ void AdjacencyWDiGraph::Prim() { //lowcost[i]是i与S中的节点最近的距离 int *lowcost = new int[n + 1]; //...
  • 本章介绍邻接矩阵无向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • prim算法也是一种贪心算法。开始时,最小生成树(MST)为空(不包含任何节点),然后维持两个集合,一个集合是包含已经进入MST中的节点,另一个集合时包含未被加入到MST中的节点。在算法的每个步骤中,从连接这两个...
  • 矩阵规则 对角线:元素 = 0 没有边: inf 有边: 权值 结构应该存在的东西 ...存储矩阵python:np.narray) class Graph: def __init___(self): self.mat # 存储矩阵 self.n # 存储边数 self.type...
  • 2.介绍一下我对书本上prim算法代码实现的理解 1.lowcost数组的作用 2.adjvex数组的作用 3.kruskal算法 3.要源码的直接看这里 1.题目简介 做完之后头发又掉了几根估计,写的代码将近两百行,结果提交上去OJ系统...
  • Prim算法与Kruskal算法构造最小生成树 ** 1.问题 分别采用Prim算法与Kruskal算法构造最小生成树,即对于给定无向图G=<V,E>(V表示顶点,E表示边),Edge(x,y)表示连接顶点x与顶点y的边,Weight(x,y)表示Edge(x,y...
  • """有权稠密图 - 邻接矩阵""" def __init__ (self, n, directed) : self.n = n # 图中的点数 self.m = 0 # 图中的边数 self.directed = directed # bool值,表示是否为有向图 self.g = [[ None ...
  • Dijkstra算法和其邻接矩阵实现 Dijkstra算法:求定点到各顶点的最短路。 step 0:置 S<-{1}, T<-{2,3,4...n}, u1<-0,对一切j属于T, uj<-bij ;  记录 R=(J1 ,J2,... Jn),对一切 j=1,2,3,.....
  • prim算法 最小生成树

    2020-02-17 21:11:10
    Prim算法 Prim算法的由来 Prim算法利用了MST的性质:假设N= (V,E)...普里姆算法的实现假设一个无向网G以邻接矩阵形式存储,从顶点u出发构造G的最小生成树T,要求输出T的各条边。为实现这个算法需附设一个辅助数组cl...
  • kruskal算法基本思路:先对边按...prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node(为list类型),一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected...
  • 在本题中,读入一个无向图的邻接矩阵(即数组表示),建立无向图并按照以上描述中的算法建立最小生成树,并输出最小生成树的代价。 输入:输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。 以后...
  • 最小生成树(Prim算法、Kruskal算法) 生成树的定义 生成树是一个连通图G的一个极小连通子图。包含G的所有n个顶点,但只有n-1条边,并且是连通的。 生成树可由遍历过程中所经过的边组成(有多个)。 扩展:无向图。极...
  • Prim算法和Kruskal算法构造最小生成树 1.问题 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即)且为无循环图,使得的 w(T) ...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 364
精华内容 145
热门标签
关键字:

邻接矩阵prim算法python