CODEWITHSUNDEEP
c++data-structureslinked-listadjacency-list
Slae
Slae

Reputation: 345

Creating an adjacency lists

I'm learning to create adjacency lists and am very new to this. I'm trying to test one on my program. I wanted to create one vertex in the linked lists and then create a list or "edge" within that linked list. I create one linked here but not sure how to actually create one inside the linked list. I've created and tested my linked list class and I know it works, I just need to create a way to implement that into adjacency lists now. Also, I CAN'T use any list functions from the C++ library.

Am I heading in the right direction at all with my code?

#include "Vertex.h"

Vertex::Vertex(){
    neighbors = new LinkedList();
    discover = 0;
    finish = 0;
    pi = NULL;
    color = "white";
}

Vertex::~Vertex(){
   delete neighbors;
}

void Vertex::insert(Vertex* vertex){

    LinkedList *temp = new LinkedList();

if(index == 0){
    temp->insertElement(vertex);
    index++;
    if(index != 0){
        neighbors->insertElement(vertex);
    }
}

} Here's my main. Thanks in advance!

 #include <cstdlib>
#include <iostream> //to use cin and cout
#include <string> //to use strings
#include "LinkedList.h"

using namespace std;

int main (){

Vertex *vertex1 = new Vertex();

for (int i =0; i < 10; i++){
   vertex1->insert(vertex1);
}

Edit fixed a few things

Upvotes: 0

Views: 558

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118292

The most direct approach would be that each vertex's LinkedList would contain a list of all other vertices this vertex is adjacent to.

You didn't provide the details of your LinkedList implementation, and I presume that your insert() method's purpose is to record that two vertices are adjacent to each other, that this is adjacent to the vertex parameter.

If these assumptions are correct, then I would expect that your insert() method should look something like this:

void Vertex::insert(Vertex* vertex)
{
    neighbors->add(vertex);
    vertex->neighbors->add(this);
}

You have a neighbors member in the Vertex class that I am presuming would contain a list of pointers to other Vertexes that are adjance to this one.

Therefore, to record that two vertices are adjacent to each other, you have to record each one of them in the other vertex's neighbors method.

You will simply need to implement add(), to append a pointer to your linked list.

Now, when you need to find all vertices adjacent to the given Vertex, you'll just iterate over the vertices in its neighbors link list. So, iterating over each vertex in the pair would, eventually, include the other vertex too.

Your homework assignment is:

1) Your destructor is incomplete. Simply deleting the neighbors member would only work if you'll always delete all vertices in the matrix. If you wish to have the ability to remove vertices from an adjacency matrix, but to still keep the rest of it, you will obviously need to remove the Vertex being destroyed from the neighbors list in all the Vertexs that the vertex being destroyed is adjacent to.

2) Some basic error checking, to do something sensible if your code attempts to link two adjacent vertices after they've already been linked as adjacent to each other.

Upvotes: 1

Related Questions