1

我创建了一个用 C 编写的通用数据结构和算法库。我尝试使用 Prim 算法实现最小生成树

当我运行双向图的代码时，我看到反向边也被添加为 MST() 的一部分，从而创建了重复边并增加了整体 MST 树成本。

代码实现如下所示，

图.h

/*! @file graph.h
    @brief 
    Contains declations of graph types, operations and structure
*/
#pragma once
#include "common.h"
#include "link_list.h"

/// graph Vertex
typedef struct gnode {
    t_gen id;           ///< Pointer to store Data
    int idx;            ///< Index of vertex in adaceny list
    t_linklist *neigh;      ///< Link List to neighbor vertices(nodes)
} t_gnode;

/// graph neighbor edges represented in neigh list
typedef struct gedge {
    t_gnode *node;          ///< Pointer to neighbor vertex
    int weight;         ///< Cost of the edge
} t_gedge;

// fn ptr for adding weighted edge
typedef t_gen (*f_wedge)(t_gen, t_gen, t_gen, int); 

/// graph struct defn
typedef struct graph {
    // graph info params
    char *name;         ///< Graph Instance Name
    int count;          ///< Vertex Count of graph
    int max_size;           ///< Max Vertex count of graph
    int total_edges;        ///< Edge count of graph

    // graph nodes
    t_gnode *nodes;         ///< Adaceny List Representation of graph vertices

    // graph routines
    f_gen2 add_vertex;      ///< routine to add a vertex in graph
    f_gen2 del_vertex;      ///< routine to del a vertex in graph
    f_gen3 add_edge;        ///< routine to add an edge in graph
    f_gen3 del_edge;        ///< routine to del an edge in graph
    f_gen3 add_edge_sym;        ///< routine to add a symmetric edge in graph
    f_gen3 del_edge_sym;        ///< routine to del a symmetric edge in graph
    f_wedge add_wedge;      ///< routine to add a weighted edge in graph
    f_wedge add_wedge_sym;      ///< routine to add a weighted symmetric 
    f_find find;            ///< routine to find a vertex in graph
    f_len len;          ///< routine to get vertex count in graph
    
} t_graph;


/// Dist info
typedef struct dist_info {
    t_gedge edge;           ///< Pointer to edge
    t_gnode *parent;        ///< Pointer to Vertex vertex
} t_distinfo;

图.c


/*! @brief  
 *  Find the Minimum Spanning for weighted undirected graph
 *  Using Prim's Algorithm
 *  @see https://en.wikipedia.org/wiki/Prim%27s_algorithm
 *  @param d     - Pointer instance of graph
 *  @return      - Pointer to dist array to all nodes in graph
 */
t_gen prims_mst(t_gen d)
{
    t_graph *g = (t_graph*)d;
    t_gedge *v, *u;
    t_llnode *cur, *end;
    t_linklist *neigh_list;
    t_distinfo *dist, *tmp;
    t_heap *h;
    t_dparams dp;
    t_gen *pq;

    // Data specific operation for generic min heap
    init_data_params(&dp, eUSER);
    dp.free     = dummy_free;
    dp.cmpr     = graph_wedge_cmpr; 
    dp.cmpr_idx = graph_wedge_cmpr_idx;
    dp.swap_idx = gen_swp_idx;
    dp.copy_idx = gen_cpy_idx;
    dp.get_idx  = gen_get_idx;

    // Creating a generic min heap to store edges
    pq   = get_mem(g->count, sizeof(t_gen));    
    h    = create_heap("Dijkstra's Heap", pq, g->count, eMIN_HEAP, &dp);
    
    // Initalize all dist to all nodes as infinite 
    dist = get_mem(g->count, sizeof(t_distinfo));   
    for (int i = 0; i < g->count; i++) {
        dist[i].edge.node   = &g->nodes[i];
        dist[i].edge.weight = INT_MAX; 
        dist[i].parent      = NULL;
    }
    
    
    // Set 0 as start vertex
    h->insert(h, &dist[0].edge);
    while (h->empty(h) != true) {
        // Of the edges that connect the tree to vertices not yet in the tree,
        // Find the minimum-weight edge, and transfer it to the tree
        u = h->extract(h);

        neigh_list = (t_linklist*)u->node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            v = (t_gedge*)cur->data;
            
            // If cur edge weight is greater than new edge
            // and the end vertex is not visited
            if (dist[v->node->idx].edge.weight > v->weight) {
                // Set new edge as part of MST, update parent
                // and add edge to heap
                dist[v->node->idx].edge.weight = v->weight;
                dist[v->node->idx].parent = u->node;
                h->insert(h, &dist[v->node->idx].edge);
            }
            
            // Exit after neigh list traversal complete
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    // Destroy heap and destroy the array used for storing heap
    h->destroy(h);
    free_mem(pq);

    return dist;
}

有人可以帮我弄清楚如何从 MST 中删除反向（重复）边缘。

堆实现在这里。

在此处完成 Graph 实现。

在此处形成邻接列表的链接列表实现。

在此处链接到 Github 存储库

4

0 回答 0