为什么我的邻接列表显示重复的边？

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：将邻接矩阵转换为邻接列表。

printList：遍历邻接矩阵并为每条边打印一条消息。

问题：某些边被重复。我不确定当我创建列表数组或遍历邻接矩阵来打印它时这是否是一个问题。有什么建议吗？

下面是带有边 (0, 1) 和 (3, 2) 的 5 个顶点的程序输出图片。矩阵是正确的。邻接表不是。边 (0, 1)、(1, 1) 和 (2, 3) 不应重复。

Answer 1

将其更改

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

为：

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

在邻接矩阵中，b[i][j] 和 b[j][i]< 处的每条边都有两个 1 /代码>。

创建列表时，您将为 adj 矩阵中找到的每个 1 添加两个节点到 adj 列表。因此，为每条边创建 4 个节点，而不是两个。

还将 print 函数中的以下内容更改

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

为：

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

您的打印功能也是错误的，它会在打印时破坏列表而不释放任何内存。它应该是这样的：

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

我认为邻接列表的问题是这个代码：

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

应该是这样的：

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

用于创建邻接列表的代码应该镜像您用于打印矩阵的代码。