Closeness centrality of a vertex v in a graph G V E is given

Closeness centrality of a vertex v in a graph G (V, E) is given as CC(v) 2 u inv d(u,v) where n IVI, and d(u, v) is the shortest path between the nodes u and v In other words, closeness centrality is the reciprocal of the average of the sum of the distances of the given vertex from all other vertices Write an algorithm to find the top 10 vertices with highest closeness centrality.

Solution

#include <iostream>
#include <cstdlib>
using namespace std;

/*
* Adjacency List Node
*/
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};

/*
* Adjacency List
*/
struct AdjList
{
struct AdjListNode *head;
};

/*
* Class Graph
*/
class Graph
{
private:
int V;
struct AdjList* array;
public:
Graph(int V)
{
this->V = V;
array = new AdjList [V];
for (int i = 0; i < V; ++i)
array[i].head = NULL;
}
/*
* Creating New Adjacency List Node
*/
AdjListNode* newAdjListNode(int dest)
{
AdjListNode* newNode = new AdjListNode;
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
/*
* Adding Edge to Graph
*/
void addEdge(int src, int dest)
{
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = array[src].head;
array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = array[dest].head;
array[dest].head = newNode;
}
/*
* Print the graph
*/
void printGraph()
{
int v;
for (v = 0; v < V; ++v)
{
AdjListNode* pCrawl = array[v].head;
cout<<\"\ Adjacency list of vertex \"<<v<<\"\ head \";
while (pCrawl)
{
cout<<\"-> \"<<pCrawl->dest;
pCrawl = pCrawl->next;
}
cout<<endl;
}
}
};

/*
* Main
*/
int main()
{
Graph gh(5);
gh.addEdge(0, 1);
gh.addEdge(0, 4);
gh.addEdge(1, 2);
gh.addEdge(1, 3);
gh.addEdge(1, 4);
gh.addEdge(2, 3);
gh.addEdge(3, 4);

// print the adjacency list representation of the above graph
gh.printGraph();

return 0;
}