Why is my adjacency list showing duplicate edges?

Question

 #include <iostream>
using namespace std;

struct node
{
    int v;
    node* next;
    node (int x, node* t)
    {
        v = x;
        next = t;
    }
};

typedef node *link;

int **malloc2d(int, int);
void printMatrix(int **, int);
link *convertToList (int **, link *, int);
void printList (link * a, int size);

// program begins function execution
int main ()
{
    // input number of vertices
    int i, j, V;
    cout << "Enter the number of vertices: ";
    cin >> V;

    int **adj = malloc2d(V, V); // dynamically allocate matrix
    for (i = 0; i < V; i++) // initialize matrix with 0's
        for (j = 0; j < V; j++)
            adj[i][j] = 0;
    for (i = 0; i < V; i++) // initialize diagonal with 1's
        adj[i][i] = 1;

    // input the edges
    cout << "Enter the coordinates for an edge (or 'Ctrl' + 'Z'): ";
    while (cin >> i >> j)
    {
        adj[i][j] = 1;
        adj[j][i] = 1;
        cout << "Enter the coordinates for an edge (or 'Ctrl' + 'Z'): ";
    }

    // convert to list
    link *aList = new link [V];
    aList = convertToList(adj, aList, V);
    cout << endl;

    // print matrix
    cout << "Adjacency Matrix: " << endl;
    printMatrix (adj, V);
    cout << endl << endl;

    // print adjacency list
    cout << "Adjacency List: " << endl;
    printList (aList, V);

    return 0; // indicates successful completion
} // end function main


int **malloc2d(int r, int c)
{
    int **t = new int*[r];
    for (int i = 0; i < r; i++)
        t[i] = new int[c];
    return t;
} // end function malloc2d

void printMatrix (int ** a, int size)
{
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++)
            if (a[i][j] == 1)
                cout << "There is an edge between " << i << " and " 
                    << j << "." << endl;
} // end function print

link *convertToList (int ** b, link * a, int size)
{
    // create array
    for (int i = 0; i < size; i++)
        a[i] = 0;

    // create lists
    for (int i = 0; i < size; i++) 
        for (int j = i; j < size; j++)
        {
            if (b[i][j] == 1) // if an edge exists on the matrix
            { // create the edges on the adjacency list
                a[j] = new node(i, a[j]);
                a[i] = new node(j, a[i]);
            }
        }
    return a;
} // end function convertToList

void printList (link * a, int size)
{
    for (int i = 0; i < size; i++)
    {
        while (a[i]->next != NULL)
        {
            cout << "There is an edge between " << i << " and " 
                    << a[i]->v << "." << endl;
            a[i] = a[i]->next;
        }
    }
} // end function print

convertToList: converts an adjacency matrix into an adjacency list.

printList: traverses the adjacency matrix and prints a message for every edge.

Problem: Some edges are being duplicated. I'm not sure if it is a problem when I create the array of lists or when I traverse the adjacency matrix to print it. Any suggestions?

Below is a picture of the program output for 5 vertices with edges (0, 1) and (3, 2). The matrix is correct. The adjacency list is not. Edges (0, 1), (1, 1) and (2, 3) should not be repeated.

Answer 1

Change this:

   for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++)

To:

   for (int i = 0; i < size; i++) 
        for (int j = i; j < size; j++)

In the adjacency matrix there are two 1 for each edge at b[i][j] and b[j][i].

While creating the list you are adding two nodes to the adj list for each 1 found in the adj matrix. Hence 4 nodes get created for each edge instead of two.

Also change the following in the print function:

for (int i = 0; i < size; i++)
    {
        while (a[i]->next != NULL)
        {
            cout << "There is an edge between " << i << " and "
                    << a[i]->v << "." << endl;
            a[i] = a[i]->next;
        }
    }

to:

for (int i = 0; i < size; i++)
    {
        link ptr = a[i];
        while (ptr)
        {
            cout << "There is an edge between " << i << " and "
                    << ptr->v << "." << endl;
            ptr = ptr ->next;
        }
    }

Answer 2

Your print function is also wrong, and it destroys the list while printing without freeing any of the memory. It should read something like this:

void printList (link * a, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (link finger = a[i]; finger != NULL; finger = finger->next)
        {
            cout << "There is an edge between " << i << " and " 
                    << finger->v << "." << endl;
        }
    }
} // end function print

And I think your problem with the adjacency lists is that this code:

for (int j = i; j < size; j++)
{
    if (b[i][j] == 1) // if an edge exists on the matrix
    { // create the edges on the adjacency list
        a[j] = new node(i, a[j]);
        a[i] = new node(j, a[i]);
    }
}

should be this:

for (int j = 0; j < size; j++)
{
    if (b[i][j] == 1) // if an edge exists on the matrix
    { // create the edges on the adjacency list
        a[i] = new node(j, a[i]);
    }
}

The code for creating the adjacency lists should mirror the code you have for printing out the matrix.