Creating an adjacency lists

Question

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

There are too many news in your code. Where is your copy constructor etc? — Neil Kirk
– Neil Kirk, Commented Apr 13, 2015 at 1:17
would I create a while loop or something with an index and increment the objects created instead? @NeilKirk — Slae
– Slae, Commented Apr 13, 2015 at 1:19
I don't understand. You also shouldn't be using static variables in your function. — Neil Kirk
– Neil Kirk, Commented Apr 13, 2015 at 1:21
If you say "I need to build my own data structure" then your question is not about adjacency matrixes, but about implementing basic data structures such as linked lists. Before you can think of implementing an adjacency matrix, you first need to come up with a solid, debugged linked list implementation. Once you have that done, and only then, can you think about using it to implement more complicated data structures, such as adjacency matrixes. — Sam Varshavchik
– Sam Varshavchik, Commented Apr 13, 2015 at 1:33

Sam Varshavchik · Accepted Answer · 2015-04-13 02:44:01Z

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.

Collectives™ on Stack Overflow

Creating an adjacency lists

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related