java或c ++中的邻接矩阵以查找连接的节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/349446/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
adjacency matrix in java or c++ to find connected nodes
提问by Omnipresent
I am given a problem where I have been given N nodes in a graph that are interconnected to each other then given a matrix which lists down a node being connected to another (1 if it is, 0 if not). I am wondering how to best approach this problem. I think these are adjacency matrix? But how would I implement that ...
我遇到了一个问题，我在图中给出了 N 个相互连接的节点，然后给出了一个矩阵，该矩阵列出了一个连接到另一个节点的节点（如果是，则为 0，否则为 0）。我想知道如何最好地解决这个问题。我认为这些是邻接矩阵？但我将如何实施...
Basically what I am trying to get out of these is find whether a particular node is connected to all other nodes in a given set 'S'. And whether selected items are clique or not...
基本上我试图摆脱这些是查找特定节点是否连接到给定集合“S”中的所有其他节点。以及选择的项目是否是集团...
I'd appreciate any hints.
我很感激任何提示。
采纳答案by lemnisca
You can implement this using a 2-dimensional array of booleans. So, if node i is connected to node j, then myarray[i][j] would be true. If your edges are not directional, then myarray[j][i] would be true whenever myarray[i][j] is.
您可以使用布尔值的二维数组来实现这一点。因此，如果节点 i 连接到节点 j，则 myarray[i][j] 将为 true。如果您的边没有方向性，那么 myarray[j][i] 将在 myarray[i][j] 为真时为真。
This can also be extended to weighted edges by using integers (or another numeric type) instead of booleans as the elements of the array.
这也可以通过使用整数（或其他数字类型）而不是布尔值作为数组元素来扩展到加权边。
回答by Piotr Lesnicki
Hint: So you have your adjacency matrix Mwhich tells you if two nodes are directly connected. Then what does M^2 gives you? It tells you if there is a path of length 2 between two nodes.
提示：所以你有你的邻接矩阵M，它告诉你两个节点是否直接连接。那么M^2给了你什么？它告诉您两个节点之间是否存在长度为 2 的路径。
I let you imagine what are M^3,... , M^inf (when you reach the fixpoint)
我让你想象一下什么是 M^3,... , M^inf （当你到达固定点时）
回答by James
The easiest way to do this would be to use a square matrix (2d array), either of booleans to show the presence or absence of a connection or integers to represent the cost of traversal. For a sparse graph, however, you may get better compression by using jagged arrays and then storing which nodes are adjacent to the first one. In Java, I'd probably do this by having a List<List<Integer>>where the outer list corresponds to the node in question and the inner list is all of the nodes adjacent to this one.
最简单的方法是使用方阵（二维数组），要么使用布尔值来显示连接的存在或不存在，要么使用整数来表示遍历的成本。但是，对于稀疏图，您可以通过使用锯齿状数组然后存储哪些节点与第一个节点相邻来获得更好的压缩。在 Java 中，我可能会这样做，List<List<Integer>>其中外部列表对应于所讨论的节点，内部列表是与该节点相邻的所有节点。
Assuming you decide to use a standard (uncompressed) matrix, you could find out whether a node i is adjacent to every node j in a list by iterating through the list, and then looking up A[i][j]. If any of them are false, then it is not adjacent to every item in the list, otherwise it is true. For a clique, you just have to do this for every item in the list (dropping the case where i=j and making some optimizations for an undirected graph).
假设您决定使用标准（未压缩）矩阵，您可以通过遍历列表然后查找 A[i][j] 来确定节点 i 是否与列表中的每个节点 j 相邻。如果其中任何一个是false，则它不与列表中的每个项目相邻，否则为真。对于一个集团，您只需要对列表中的每个项目执行此操作（删除 i=j 的情况并对无向图进行一些优化）。
An example (again in Java)
一个例子（同样是在 Java 中）
public boolean isClique(boolean[][] A, List<Integer> nodes){
for(int i : nodes){
for(int j : nodes){
if(i != j){
if(!A[i][j]) return false;
}
}
}
return true;
}
Optimizations and a solution to the Max-Clique problem are left as an exercise to the reader.
Max-Clique 问题的优化和解决方案留给读者作为练习。
回答by Robin
Using your adjacency matrix, applying the Floyd-Warshall algorithmwill give you all your paths between nodes. Then you can check for particular sets.
使用您的邻接矩阵，应用Floyd-Warshall 算法将为您提供节点之间的所有路径。然后你可以检查特定的集合。
回答by Mr.Ree
You might want to use bitsetor bit_vectorinstead of bool[][].
您可能想要使用bitset或bit_vector而不是 bool[][]。
If you don't use a jagged array, and your connections are symmetric, consider wrapping with an accessor based on MIN() & MAX() [macros]. Storing the same data in two places is a recipe for pain. Eventually, array[i][j] != array[j][i].
如果您不使用锯齿状数组，并且您的连接是对称的，请考虑使用基于 MIN() 和 MAX() [宏] 的访问器进行包装。在两个地方存储相同的数据是一种痛苦的方法。最终，array[i][j] != array[j][i]。
E.g: getValue( int i, int j ) { return array [ MIN(i,j) ] [ MAX(i,j) ] }
回答by Mr.Ree
Try this:
尝试这个：
public class AdjacencyMatrix {
private String [] nodes;
private int [][] matrix;
public AdjacencyMatrix(String [] nodes,int [][] matrix){
this.nodes = nodes;
this.matrix = matrix;
}
boolean isSymmetric(){
boolean sym = true;
for(int i=0;i<matrix.length;i++){
for(int j=i+1; j < matrix[0].length ; j++){
if (matrix[i][j] != matrix[j][i]){
sym = false;
break;
}
}
}
return sym;
}
public Graph createGraph(){
Graph graph = new Graph();
Node[] NODES = new Node[nodes.length];
for (int i=0; i<nodes.length; i++){
NODES[i] = new Node(nodes[i]);
graph.addNode(NODES[i]);
}
for(int i=0;i<matrix.length;i++){
for(int j=i;j<matrix[0].length;j++){
int distance = matrix[i][j];
if (distance != 0){
graph.addEdge(new Edge(NODES[i], NODES[j], distance));
}
}
}
return graph;
}
public long pathLength(int[] path){
long sum = 0;
for (int i=0; i<path.length - 1; i++){
if (matrix[path[i]][path[i+1]] != 0)
sum += matrix[path[i]][path[i+1]];
else {
sum = 0;
break;
}
}
return sum;
}
public static void main(String[] args){
String[] nodes = {"A", "B", "C", "D", "E"};
int [][] matrix= { {0, 2, 2, 1, 0},
{2, 0, 1, 0, 0},
{2, 1, 0, 0, 1},
{1, 0, 0, 0, 4},
{0, 0, 1, 4, 7}};
AdjacencyMatrix am = new AdjacencyMatrix(nodes, matrix);
Graph graph = am.createGraph();
int[] a = {0, 2, 4, 4, 3, 0};
int[] b = {0, 1, 2, 4, 4, 3, 0};
graph.writeGraph();
am.pathLength(a);
am.pathLength(b);
}
}
