我正在嘗試將鄰接矩陣轉換為無向圖的關聯矩陣。對于邊：(1, 2), (1,5), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5) , (5,6)
Adj 矩陣是：
0 1 0 0 1 1
1 0 1 0 1 0
0 1 0 1 1 0
0 0 1 0 1 0
1 1 1 1 0 1
1 0 0 0 1 0
我希望關聯矩陣的結果是
0 1 0 0 1 1 0 0 0
1 0 1 0 1 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 0
1 1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0 0
但是，我的程式回傳這個：
1 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 1 0 1 0 0 0
1 0 1 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0
我的源代碼：
graph constructor
Graph(int vertices, int edges)
{
this->vertices = vertices;
this->edges = edges;
edge = std::vector<Graph::Edge*>(edges);
for (int i = 0; i < edges; i )
{
edge[i] = new Edge(this);
}
}
Graph* g = new Graph(numberOfVertices, numberOfEdges);
g->edge[0]->src = 1;
g->edge[0]->dest = 2;
g->edge[1]->src = 1;
g->edge[1]->dest = 5;
g->edge[2]->src = 1;
g->edge[2]->dest = 6;
g->edge[3]->src = 2;
g->edge[3]->dest = 3;
g->edge[4]->src = 2;
g->edge[4]->dest = 5;
g->edge[5]->src = 3;
g->edge[5]->dest = 4;
g->edge[6]->src = 3;
g->edge[6]->dest = 5;
g->edge[7]->src = 4;
g->edge[7]->dest = 5;
g->edge[8]->src = 5;
g->edge[8]->dest = 6;
for (i = 0; i < numberOfEdges; i )
{
adjacency_matrix[g->edge[i]->src][g->edge[i]->dest] = 1;
adjacency_matrix[g->edge[i]->dest][g->edge[i]->src] = 1;
}
std::cout << "Adjacency matrix : " << std::endl;
for (i = 1; i <= numberOfVertices; i )
{
for (j = 1; j <= numberOfVertices; j )
{
std::cout<<adjacency_matrix[i][j]<<" ";
}
std::cout << std::endl;
}
// Incidence Matrix
int counter = 0;
for( int i = 1; i <= numberOfEdges; i ){
for(int j = i 1; j < numberOfVertices; j ){
if(adjacency_matrix[i][j] == 1){
incidence_matrix[i][counter] = 1;
incidence_matrix[j][counter] = 1;
counter;
}
}
}
for( int i = 1; i <= numberOfVertices; i ){
for(int j = 1; j <= numberOfEdges; j ){
std::cout<<incidence_matrix[i][j]<<" ";
}
std::cout<<std::endl;
}
uj5u.com熱心網友回復：
代碼中的想法是正確的。但是陣列中的索引是錯誤的。
索引應從 0 開始。注意：這也適用于設定鄰接矩陣時。
用于命名最初為 1、2、3、4、5、6 的頂點/節點的數字。我建議稱它們為 0、1、2、3、4、5。您的原始邊緣 (1,2) 然后變為 (0,1)。但是，如果我們始終如一地重命名所有地方的所有頂點，我們最終會得到相同的圖。這種新命名約定的優點是我們可以將這些名稱直接用作您正在使用的 C 資料結構中的索引。（假設我們使用相應的整數值并且不將這些名稱視為字串。）
Graph 的規范變為
Graph* g = new Graph(numberOfVertices, numberOfEdges);
g->edge[0]->src = 0;
g->edge[0]->dest = 1;
g->edge[1]->src = 0;
g->edge[1]->dest = 4;
g->edge[2]->src = 0;
g->edge[2]->dest = 5;
g->edge[3]->src = 1;
g->edge[3]->dest = 2;
g->edge[4]->src = 1;
g->edge[4]->dest = 4;
g->edge[5]->src = 2;
g->edge[5]->dest = 3;
g->edge[6]->src = 2;
g->edge[6]->dest = 4;
g->edge[7]->src = 3;
g->edge[7]->dest = 4;
g->edge[8]->src = 4;
g->edge[8]->dest = 5;
所以列印鄰接矩陣就變成了：
std::cout << "Adjacency matrix : " << std::endl;
for (i = 0; i < numberOfVertices; i )
{
for (j = 0; j < numberOfVertices; j )
{
std::cout<<adjacency_matrix[i][j]<<" ";
}
std::cout << std::endl;
}
并且關聯矩陣的計算變為：
// Incidence Matrix
int counter = 0;
for( int i = 0; i < numberOfVertices; i ){ //numberOfVertices!!
for(int j = i 1; j < numberOfVertices; j ){
if(adjacency_matrix[i][j] == 1){
incidence_matrix[i][counter] = 1;
incidence_matrix[j][counter] = 1;
counter;
}
}
}
for( int i = 0; i < numberOfVertices; i ){
for(int j = 0; j < numberOfEdges; j ){
std::cout<<incidence_matrix[i][j]<<" ";
}
std::cout<<std::endl;
}
請注意，邊的順序現在由您遍歷鄰接矩陣的順序決定。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/515309.html
標籤：C 矩阵图论
上一篇：在Lua中注冊回呼