有向加权图(邻接矩阵)的实现

Question

我需要帮助在java中使用邻接矩阵实现有向加权图。不知道如何检查是否有连接的边或如何删除，只知道如何添加边。

// Implementation of directed weighted Graph using Adjacent Matrix
public class Graph {
private int size;
private int adjacentMatrix[][];

public Graph (int size) {
this.size = size;
adjacentMatrix = new int [size][size];
}

public void addEdge (int source, int destination, int weight) {
if (source < size && source >= 0 && destination < size && destination >= 0)
adjacentMatrix [source][destination] = weight;
}
// need help in this function for what to set second line equal to or new function in general
public void removeEdge (int source, int destination, int weight) {
if (source < size && source >= 0 && destination < size && destination >= 0)
adjacentMatrix [source][destination] = 0;  //(not sure)
}

//need help with this entire function
//function to check if edges are connected
public boolean isEdge(int source, int destination) {
if(size >= 0 && size < size && destination >= 0 && destination < size) {
if(adjacentMatrix[source][destination] == 1)
return true;
else
return false;
}
}
}   
}
// I'm not sure if I did this correct at all any help would be appreciated

Answer 1

要删除边，只需将相邻矩阵的单元格更改为0(在默认阶段(。

Answer 2

你几乎已经想通了！

假设在邻接矩阵中，值为0意味着没有边，大于0意味着有一条具有该权重的边。

removeEdge方法不需要weight，因为它删除了一条边。此处设置为0是正确的，因为0表示"无边"。

public void removeEdge (int source, int destination) {
if (source < size && source >= 0 && destination < size && destination >= 0)
adjacentMatrix [source][destination] = 0;
}
}

既然告诉在那里放置weight参数，那么可能只有在权重与传入权重匹配的情况下才应该移除边缘？

isEdge方法应该检查adjacentMatrix[source][destination] > 0而不是adjacentMatrix[source][destination] == 1，因为任何正值都意味着"那里有边"。

public boolean isEdge(int source, int destination) {
if(size >= 0 && size < size && destination >= 0 && destination < size) {
return adjacentMatrix[source][destination] > 0;
} else {
return false; // if out of range, no edge
}
}

Answer 3

addEdge中对权重没有限制，因此权重可以有任何值，包括0。
因此，0不是表示没有边缘的最佳选择
我建议将权重设置为无穷大。在没有边缘的地方应用无限权重是有意义的：

adjacentMatrix [source][destination] =Integer.MAX_VALUE;

这可能需要在开始时将整个阵列adjacentMatrix[][]初始化为Integer.MAX_VALUE：

for(int[] row : adjacentMatrix)
Arrays.fill(row, Integer.MAX_VALUE);
}

isEdge也变得简单易读：

public boolean isEdge(int source, int destination) {
if(size >= 0  
&& destination >= 0 && destination < size
&& source >= 0 && source < size ) 
return adjacentMatrix[source][destination] != Integer.MAX_VALUE;                        
return false;            
}