這是使用鄰接列表實現無向圖的正確方法嗎？

-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

這是使用鄰接列表實現無向圖的正確方法嗎？

回答

相關問題