Why is my adjacency list showing duplicate edges?

 #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 < s开发者_开发知识库ize; 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.

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;
        }
    }

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.