java 将二维矩阵转换为图形
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25405165/
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
Converting a 2D matrix into a graph
提问by Virat
I am facing a problem while converting a given 2D matrix containing both invalid and valid points into a graph with only valid nodes. The problem goes like this. I have a 2D matrix like
我在将包含无效点和有效点的给定二维矩阵转换为只有有效节点的图形时遇到问题。问题是这样的。我有一个二维矩阵
# # # # #
# . C C #
# S # # #
# . . E #
# # # # #
I want to find the shortest distance from S to E keeping in mind that I have to cover all 'C' and '#' acts as a wall and '.' acts as free path. Now I want to convert this matrix into a graph containing only the valid nodes. Kindly help me out.
我想找到从 S 到 E 的最短距离，记住我必须覆盖所有的 'C' 和 '#' 作为一堵墙和 '.' 充当自由路径。现在我想将此矩阵转换为仅包含有效节点的图形。请帮帮我。
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
for i=1 to n:
for j=1 to n:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest
回答by Gene
A 2d matrix of the characters is a perfectly fine graph representation for this problem.
字符的二维矩阵是这个问题的完美图形表示。
Each matrix element (i,j) is a node. Assuming you can only step East, West, North, South, there exist 0 to 4 undirected edges from this node to its neighbors (i +or- 1, j +or- 1) as determined by simply testing the character in each location.
每个矩阵元素 (i,j) 都是一个节点。假设您只能向东、西、北、南步进，那么从这个节点到它的邻居 (i +or- 1, j +or- 1) 存在 0 到 4 条无向边，这通过简单地测试每个位置的字符来确定。
You could also test for i,j values that are out of range (negative or too big), but if there is always a "wall" around the border as you have shown, this is not needed. The wall serves as a sentinel.
您还可以测试超出范围（负数或太大）的 i,j 值，但如果如图所示边界周围始终存在“墙”，则不需要这样做。墙壁充当哨兵。
Building a general purpose structure to represent a graph embedded in a grid is a waste of time and memory.
构建一个通用结构来表示嵌入在网格中的图形是浪费时间和内存。
回答by ElRoBe
In order to make the graph, you have to generate a node for each non-wall space. Go through the 2D matrix (assuming it's just a char array) and create nodes and add edges:
为了制作图形，您必须为每个非墙空间生成一个节点。遍历二维矩阵（假设它只是一个字符数组）并创建节点并添加边：
nodes = new Node[matrix.length][matrix[0].length]; //instance variable
for ( int row = 0; row < matrix.length; row++ )
{
for ( int col = 0; col < matrix[row].length; col++ )
{
char type = matrix[row][col];
if ( type != '#' )
{
Node n = new Node();
nodes[row][col] = n; //constructor to determine type of node
if ( type == 'S' )
startNode = n;
else if ( type == 'E' )
endNode = n;
findNeighbors(row, col); //assuming nodes and matrix variables are instance variables
}
else
nodes[row][col] = null;
}
}
With a 2D array of nodes, you can then go through and add neighbors with findNeighbors:
使用二维节点数组，您可以通过 findNeighbors 遍历并添加邻居：
public void findNeighbors(int row, int col)
{
for ( int r = -1; r <= 1; r++ )
{
for ( int c = -1; c <= 1; c++ )
{
try {
if ( matrix[row+r][col+c] != '#' )
nodes[row][col].addEdge(nodes[row+r][col+c]);
} catch (ArrayIndexOutOfBoundsException e) {}
}
}
}
Now, after all that code, you have a 2D array of Node objects that represent a graph. You could store the Start node in an instance variable to keep a handy reference to it and easily access its neighbors.
现在，完成所有这些代码之后，您就有了一个代表图形的 Node 对象的二维数组。您可以将 Start 节点存储在一个实例变量中，以便方便地引用它并轻松访问它的邻居。
With the code I wrote, the Node class will need a method addEdge(Node)that adds the argument node to a list of nodes.
使用我编写的代码，Node 类将需要一个addEdge(Node)将参数节点添加到节点列表的方法。
回答by John Cohen
This looks like a homework but for the sake of conversation (time/space complexity) I would do something different. First I would create a Graph that only contains valid edges between nodes that can be a path (e.g. not a wall). This minimize the space needed. I won't use a matrix because it uses too much space in real graph (sparse) and the time complexity is ROW*COL (V^2 for a square matrix).
这看起来像是作业，但为了对话（时间/空间复杂性），我会做一些不同的事情。首先，我将创建一个仅包含可以是路径（例如，不是墙）的节点之间的有效边的图。这最大限度地减少了所需的空间。我不会使用矩阵，因为它在实图中使用了太多空间（稀疏）并且时间复杂度为 ROW*COL（方阵为 V^2）。
class Graph {
Map<Integer, Set<Integer>> edgeTo;
Graph() {
this.edgeTo = new HashMap<Integer, Set<Integer>>();
}
public int size() {
return edgeTo.size();
}
public void addEdge(int v1, int v2) {
add(v1, v2);
add(v2, v1);
}
private void add(int from, int to) {
if (!edgeTo.containsKey(from)) {
Set<Integer> s = new HashSet<Integer>();
s.add(to);
edgeTo.put(from, s);
} else {
edgeTo.get(from).add(to);
}
}
public Set<Integer> adj(int v) {
return edgeTo.get(v);
}
}
With this in-place the creation of the graph follows the idea of previous post,
有了这个就地图的创建遵循上一篇文章的想法，
private Graph createGrap(char[][] matrix) {
Graph g = new Graph();
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
// skip this cells
if (!isFreeCell(matrix[r][c])) {
continue;
}
int id = createUniqueId(r, c);
if (matrix[r][c] == 'S') {
startVertex = id;
} else if (matrix[r][c] == 'E') {
endVertex = id;
}
createNeighbor(r, c, matrix, g);
}
}
return g;
}
private void createNeighbor(final int r, final int c, final char[][] matrix2, final Graph g) {
for (int row = -1; row <= 1; row++) {
for (int col = -1; col <= 1; col++) {
// avoid the center cell
if (row ==0 && col == 0){
continue;
}
// outside matrix
if ((0 > c + col) || (c + col >= matrix2[0].length) || (0 > r + row) || (r + row >= matrix2.length)) {
continue;
}
char value = matrix2[r+row][c+col];
if (!isFreeCell(value)){
continue;
}
int from = createUniqueId(r, c);
int to = createUniqueId(row+r, col+c);
g.add(from, to);
}
}
}
private boolean isFreeCell(char value) {
return (value != '#' && value !='C');
}
private int createUniqueId(int r, int c) {
return r * MAX_COL + c;
}
Now the only thing left is to find the Shortest Path...using BFS of this undirected-graph with no negative weighed edges...
现在唯一剩下的就是找到最短路径......使用这个无向图的 BFS 没有负加权边......
private void findSP(Graph g) {
if (g == null || g.size() == 0) {
throw new IllegalArgumentException("empty or null graph");
}
if (g.size() == 1) {
throw new IllegalArgumentException(
"graph's size must be greater than 1");
}
if (startVertex == -1) {
throw new IllegalArgumentException("Start vertex not found");
}
if (endVertex == -1) {
throw new IllegalArgumentException("End vertex not found");
}
Map<Integer, Integer> sonToParent = bfs(g, startVertex, endVertex);
Stack<Integer> path = new Stack<Integer>();
for (int son = endVertex; son!= startVertex; son = sonToParent.get(son)){
path.push(son);
}
path.push(startVertex);
while (!path.isEmpty()){
System.out.print(path.pop() + ", ");
}
}
private Map<Integer, Integer> bfs(Graph g, int startVertex2, int endVertex2) {
Queue<Integer> q = new LinkedList<Integer>();
Set<Integer> marked = new HashSet<Integer>();
Map<Integer, Integer> sonToParent = new HashMap<Integer, Integer>();
q.add(startVertex2);
while (!q.isEmpty()) {
int v = q.poll();
for (Integer s : g.adj(v)) {
if (!marked.contains(s)) {
marked.add(s);
sonToParent.put(s, v);
if (s == endVertex2) {
return sonToParent;
}
q.add(s);
}
}
}
return null;
}
回答by DevLan
I would either create a node struct, or a node class. For example:
我要么创建一个节点结构，要么创建一个节点类。例如：
struct Node {
node type; //Indicate in some way if the node is a 'S', '.' or 'E'
std::vector<Node> adjacentNodes;
}
As far as filling this data structure, I would start at the 'S' block. And make a recursive call kind of like:
至于填充这个数据结构，我会从“S”块开始。并进行类似的递归调用：
Set alreadyVisited;
FillGraph(i,j,Node){
// for all adjacent nodes, add them to Node's adjacentNodes.
// add Node to alreadyVisited Set
// for each of the adjacentNodes (i.e. any neighbor that isn't a wall.
// if(adjacentNode is not in alreadyVisited)
// FillGraph(adjaent-i, adjacent-j, adjacentNode);
}
