这是使用邻接列表实现无向图的正确方法吗？

-3

首先，我是图形学的新手。经过图形的概念研究。我想在C++中实现。当我寻找实现时，我感到很难理解代码，所以我想实现自己。这是使用邻接列表实现无向图的正确方法吗？

以下是我试图的代码：

#include<iostream> 
using namespace std; 

struct Node { 
    int data; 
    Node *link; 

}; 

//creating array of nodes 
struct Node *array[10]; 
//creating array of head pointers to point each of the array node. 
struct Node *head[10]; 
//creating array of current pointers to track the list on each array node. 
struct Node *cur[10]; 

void create(int v) 
{ 

    for (int i = 0; i < v; i++) { 
     array[i] = new Node; 
     head[i] = cur[i] = array[i]; 
     array[i]->data = i; 
     array[i]->link = NULL; 
    } 

} 

void add(int fr, int to) 
{ 
    Node *np = new Node; 
    np->data = to; 
    np->link = NULL; 

    if (head[fr]->link == NULL) { 
     head[fr]->link = np; 
     cur[fr] = np; 

    } else { 
     cur[fr]->link = np; 
     cur[fr] = np; 
    } 

    /*Node* np1=new Node; 
    np1->data=fr; 
    np1->link=NULL; 
    if(head[to]->link==NULL) 
    { 
    head[to]->link=np1; 
    cur[to]=np1; 
    }else 
    { 
    cur[to]->link=np1; 
    cur[to]=np1; 
    }*/ 

} 

void print(int a) 
{ 
    Node *p = NULL; 
    p = head[a]; 

    for (; p != NULL; p = p->link) 
    { cout << p->data; } 

} 



main() 
{ 

    int a; 
    cout << "enter the size of array"; 
    cin >> a; 
    create(a); 
    //adding edges 
    add(1, 4); 
    add(1, 3); 
    add(0, 3); 
    add(0, 2); 
    print(0); 
    cout << "\n"; 
    print(1); 
    //print(3); 

}

说明：

1），要求用户输入一个整数（节数顶点），因此我创建与请求的大小的阵列。同时，我将指针指向每个数组节点的指针和cur指针。数组的索引号等于顶点数。

2）通过添加函数从一个顶点向另一个顶点添加边。如果边缘发出的顶点的头节点为空，那么我指向头= cur =新节点（np），否则我在每次加法后更新cur指针。 Head将指向数组索引节点。 3）打印连接到请求节点的边缘。

我的问题是：

1）是实施正确的这种方式？

2）在上面的例子中，让我们假设我们连接顶点1和顶点3.与上面的代码3连接到1.我想自动更新从顶点3到顶点1的连接，所以我添加了代码里面的注释部分添加function.When我试着运行代码它要求我输入数组的大小，我输入一些整数它显示我的分段错误。为什么？

来源

2015-10-01 Dhineshkumar

你能告诉我你输入的整数值是多少？ – cryptomanic

我试着给3和4作为'a'，他们都给分段错误。 – Dhineshkumar

我会尽力给你这个想法。

在无向图中，每个节点都可以连接到任何其他节点。这意味着一个节点'指向'任何数量的其他节点。在你的代码中，每个节点都有Node*link;这是一个指向下一个节点的指针。您需要链接的列表（或数组），而不是：每个节点都必须包含指向其所连接的所有节点的链接。这是邻接列表。类似于

struct Node 
{ 
    int data; 
    ADJ* adjs; // list of Node* 
}; 

struct ADJ 
{ 
    ADJ* next; 
    Node* data; 
};

此处adjs是邻接列表。

此外，您的解决方案void print(int a)与您在共同列表中找到的更类似。您需要打印节点的所有邻接点，即它指向的所有节点。

记住，既然是无向图，你既需要pointert A-> B和B-> A

来源

2015-10-01 14:44:20

所以你的意思是先说我们创建一个ADJ数组，并使ADJ的* next指针一个接一个地指向Node的节点。 – Dhineshkumar

的确，这是带有邻接表的表示。作为奖励，您也可以实现具有相同结构的有向图。你可以有一些变化，例如代替Node *的列表，你可以有一个Node *的数组，但是这个概念是相同的。 –

非常感谢洛伦佐。 – Dhineshkumar

调用创建后（3）你的阵列看起来像如下：

array 
0 -> (0,NULL) 
1 -> (1,NULL) 
2 -> (2,NULL) 
3 
4 
5 
6 
7 
8 
9

分割调用add（1,4）时发生故障。

在第一部分即

Node *np = new Node; 
np->data = to; 
np->link = NULL; 

if (head[fr]->link == NULL) { 
    head[fr]->link = np; 
    cur[fr] = np; 

} else { 
    cur[fr]->link = np; 
    cur[fr] = np; 
}

没有问题。

现在阵列看起来如下所示：

array 
0 -> (0,NULL) 
1 -> (1,->) (4,NULL) 
2 -> (2,NULL) 
3 
4 
5 
6 
7 
8 
9

但接着的部分是分段的故障即

Node* np1=new Node; 
np1->data=fr; 
np1->link=NULL; 
if(head[to]->link==NULL) 
{ 
head[to]->link=np1; 
cur[to]=np1; 
}else 
{ 
cur[to]->link=np1; 
cur[to]=np1; 
}

问题的原因是在这条线：

head[to]->link==NULL

这里值to为4这意味着你的代码尝试访问head [4]的一部分，但head [4]不存储有效Node的地址。

来源

2015-10-01 18:46:07 cryptomanic

我认为它的头[4]而不是头[2]。我试着给'一个'5，它工作正常。非常感谢你。 – Dhineshkumar

这是使用邻接列表实现无向图的正确方法吗？

回答

相关问题