CODEWITHSUNDEEP
c++arrays
Chuwilliamson
Chuwilliamson

Reputation: 3

Adjacency list implementation

I'm trying to implement a simple adjacency list. I understand that the index of the array is a key for the vertex at that point.

For Example: If i had edges of the format: (start, finish, cost) (1,2,4) (2,3,5) (1,3,27) (3,4,8)

I would have an array that would be

[0] -> null

[1] -> 2|4 -> 3|27 -> null

[2] -> 3|5 -> null

[3] -> 4|8 -> null

One issue is that the container holding the edges has pointers but the elements inserted into them (edges) do not. I'm lost.

editing this post because I don't know how to put code in the comments.

struct Node{
       Edge *head;
       Node *next;
}

Node *root;

void adjacencyList::insert(const Edge &edge)
{

  if(root == NULL)
   {
      root = new Node;
      root->head = edge;
    }
  else
    {
      while(root != NULL)
        {          
          root = root->next;
          if(root == NULL);
          {
            root = new Node;
            root->head = edge;
            root = root ->next;

          }
        }
     }
}

The edge object has 3 properties(source, destination, cost) Right now this does nothing but keep adding edges in a linked list. How can i separate the lists by the source?

Upvotes: 0

Views: 1977

Answers (1)

Konrad Rudolph
Konrad Rudolph

Reputation: 545488

An adjacency list doesn’t have to be a linked list. Even if it were, do not implement an (intrusive) linked list yourself, use an existing implementation.

But here we go; just have a vector of (node, cost) pairs:

typedef std::pair<int, int> weighted_node_t;
typedef std::vector<std::vector<weighted_node_t>> graph_t;

Then you can represent your graph as follows (using C++11 initialisation syntax):

graph_t graph{
    {},
    {{2, 4}, {3, 27}},
    {{3, 5}},
    {{4, 8}}
};

Now let’s assume you wanted to traverse the graph (depth first search), you’d do the following (again, C++11 syntax because it’s cleaner):

void dfs(graph_t const& graph, std::vector<bool>& visited, int node) {
    visited[node] = true;
    for (auto const& neighbor : graph[node])
        if (not visited[neighbor])
            dfs(graph, visited, neighbor.first);
}

And call it like this:

std::vector<bool> visited(graph.size());
dfs(graph, visited, 1);

Upvotes: 2

Related Questions