patterncppMinor

Kruskal algorithm implementation for adjacency list represented graph

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

representedkruskalimplementationgraphalgorithmforadjacencylist

Problem

Please review the implementation of Kruskal algorithm. Points on which I have doubt:

-
My Graph doesn't have any ID for nodes. Nodes are accessed based on their data. Is there any general approach in that? Should nodes be referenced by an ID as that will also make these algo somewhat easier to implement by using id as index into arrays.

-
With current graph representation, are there any issue in the algo implementation?

-
Are there any issues in method of accessing vertex and edges shared_ptr? Should weak_ptr be used at some places? Any shared_ptr validity issue?

-
Anything that you can suggest to improve will be helpful.

Vertex:

class Vertex {
public:
    Vertex() {
        bVisited = false;
    }
    int data = 0;
    EdgeList edgeList;
    bool bVisited = false; 
};

Edge:

struct Edge {
    int cost;
    boost::weak_ptr srcVertex;
    boost::weak_ptr dstVertex;
};

Graph:

typedef std::list> VerticesList;
typedef std::map DataVertexMap;
class Graph {

    VerticesList _verticesList;
    DataVertexMap _dataVertexMap;

    //TODO: Need some design to have this function internal only and not exposed to client
    boost::shared_ptr addAndGetVertex(int data);
public:
    Graph();
    ~Graph();

    bool isEmpty() const;
    //We don't check for duplicate vertex
    void addVertex(int data);
    void addEdge(int srcData, int dstData, int cost);
    int getCostForEdge(int srcData, int dstData);
    void displayGraph();
    void dfsTraversal();
    void bfsTraversal();

    void findShortestPath(int srcData, int dstData);
    void kruskalMST();
    void primMST();
};

Kruskal's Implementation:

```
class CompareEdge {
public:
bool operator() (const boost::shared_ptr & e1, const boost::shared_ptr & e2) const{
if(e1->cost == e2->cost)
return e1.get()

return e1->cost cost;
}
};

typedef std::map, boost::shared_ptr> ParentMap;

// A utility function to find the subset of an element i
boost::sha

Solution

-
Since Vertex just has public members, it can just be a struct.

In addition, you don't need to set bVisited to false in two places. It just needs to be done in the constructor. You could also make it an initializer list instead, which is more proper when setting default values for data members.

-
In Graph, you can omit both the constructor and destructor if you're not overriding them. But if you need to keep the constructor anyway, then use C++11's default constructor

.

Graph() = default;


- 
With C++11, you can replace

typedef`s:

typedef std::list> VerticesList;
typedef std::map DataVertexMap;

with type aliases:

using VerticesList = std::list>;
using DataVertexMap = std::map;

Code Snippets

Graph() = default;

typedef std::list<boost::shared_ptr<Vertex>> VerticesList;
typedef std::map<int, VerticesList::const_iterator> DataVertexMap;

using VerticesList = std::list<boost::shared_ptr<Vertex>>;
using DataVertexMap = std::map<int, VerticesList::const_iterator>;

Context

StackExchange Code Review Q#70770, answer score: 3

Revisions (0)

No revisions yet.