0 
 #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) 不应重复。

替代文字

4

2 回答 2

3

改变这个：

   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++)

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

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

还要在打印功能中更改以下内容：

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;
        }
    }
于 2010-02-04T09:51:23.850 回答
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]);
    }
}

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

于 2010-02-04T09:55:28.307 回答