用二维数组表示图形
Representing a graph with a 2D array
我有一个问题,我用二维数组表示图形。
我也有一个样本,但我不知道它是如何工作的……
这是我得到的图表
这就是他们使用二维数组表示它的方式
如何将一个翻译成另一个?
此外,这是 Dijsktra 算法实现的一部分。
这是供您参考的代码,它取自
geeksforgeeks
// A Java program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath {
// A utility function to find the vertex with minimum distance value,
// from the set of vertices not yet included in shortest path tree
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[])
{
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " \t\t " + dist[i]);
}
// Function that implements Dijkstra's single source shortest path
// algorithm for a graph represented using adjacency matrix
// representation
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V]; // The output array. dist[i] will hold
// the shortest distance from src to i
// sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
Boolean sptSet[] = new Boolean[V];
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices
// not yet processed. u is always equal to src in first
// iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an
// edge from u to v, and total weight of path from src to
// v through u is smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist);
}
// Driver method
public static void main(String[] args)
{
/* Let us create the example graph discussed above */
int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
例如,如果这是给我的图形,我将如何使用二维数组来表示它?
他们用一个adjacency matrix
来表示一个加权无向图。根据 geeksforgeeks:
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the
number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1
indicates that there is an edge from vertex i to vertex j. Adjacency matrix for
undirected graph is always symmetric. Adjacency Matrix is also used to represent
weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex
j with weight w.
作为最后两行状态,邻接矩阵可以用来存储他们在这种情况下所做的加权图。
如果使用邻接矩阵来表示加权图,可能问题不大。这里我们用0
到表示任意两个顶点之间没有边。 如果图中有任何图的权重为0
,则需要对邻接矩阵稍作更改,因为0
已经表示无边 .
在评论中你提到了另一个图表。然而,那个 不是 加权 。 它也是不是无向图,因为它不是对称的。
如有其他疑问,请发表评论。
我想我已经弄明白了!
在示例图中,有 9 个顶点。因此创建了一个 9x9 二维矩阵,这样:
- 第1行对应顶点0,第2行对应顶点1,依此类推
和
- 第1列对应顶点0,第2列对应顶点1,依此类推
并填充数组,使其包含节点 x 和 y 之间的边的权重。例如:Row 1 column 2 (map0)包含顶点0和顶点1之间的边的权重。
因此对于具有n个顶点的图,需要创建一个nxn数组,使得数组中的位置[x][y]包含从x到y的边之间的权重。
至于我要求解决方案的示例图,这将是其对应的二维矩阵:
它有点大,因为我们创建了一个 16x16 的 2D 矩阵
你可以把它读成坐标table。
每行代表一个顶点,同一行上的每一列值代表到第 N 个顶点的距离。
示例:
0, 1:第一行第二列的值为4;这意味着顶点 0 到顶点 1 的距离是 4.
1, 7:第二行第8列的值为11;这意味着顶点 1 到顶点 7 的距离是 11.
等等...
我有一个问题,我用二维数组表示图形。
我也有一个样本,但我不知道它是如何工作的……
这是我得到的图表
这就是他们使用二维数组表示它的方式
如何将一个翻译成另一个?
此外,这是 Dijsktra 算法实现的一部分。 这是供您参考的代码,它取自 geeksforgeeks
// A Java program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath {
// A utility function to find the vertex with minimum distance value,
// from the set of vertices not yet included in shortest path tree
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[])
{
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[])
{
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " \t\t " + dist[i]);
}
// Function that implements Dijkstra's single source shortest path
// algorithm for a graph represented using adjacency matrix
// representation
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V]; // The output array. dist[i] will hold
// the shortest distance from src to i
// sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
Boolean sptSet[] = new Boolean[V];
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices
// not yet processed. u is always equal to src in first
// iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an
// edge from u to v, and total weight of path from src to
// v through u is smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist);
}
// Driver method
public static void main(String[] args)
{
/* Let us create the example graph discussed above */
int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
例如,如果这是给我的图形,我将如何使用二维数组来表示它?
他们用一个adjacency matrix
来表示一个加权无向图。根据 geeksforgeeks:
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the
number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1
indicates that there is an edge from vertex i to vertex j. Adjacency matrix for
undirected graph is always symmetric. Adjacency Matrix is also used to represent
weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex
j with weight w.
作为最后两行状态,邻接矩阵可以用来存储他们在这种情况下所做的加权图。
如果使用邻接矩阵来表示加权图,可能问题不大。这里我们用0
到表示任意两个顶点之间没有边。 如果图中有任何图的权重为0
,则需要对邻接矩阵稍作更改,因为0
已经表示无边 .
在评论中你提到了另一个图表。然而,那个 不是 加权 。 它也是不是无向图,因为它不是对称的。
如有其他疑问,请发表评论。
我想我已经弄明白了!
在示例图中,有 9 个顶点。因此创建了一个 9x9 二维矩阵,这样:
- 第1行对应顶点0,第2行对应顶点1,依此类推
和
- 第1列对应顶点0,第2列对应顶点1,依此类推
并填充数组,使其包含节点 x 和 y 之间的边的权重。例如:Row 1 column 2 (map0)包含顶点0和顶点1之间的边的权重。
因此对于具有n个顶点的图,需要创建一个nxn数组,使得数组中的位置[x][y]包含从x到y的边之间的权重。
至于我要求解决方案的示例图,这将是其对应的二维矩阵:
它有点大,因为我们创建了一个 16x16 的 2D 矩阵
你可以把它读成坐标table。 每行代表一个顶点,同一行上的每一列值代表到第 N 个顶点的距离。
示例:
0, 1:第一行第二列的值为4;这意味着顶点 0 到顶点 1 的距离是 4.
1, 7:第二行第8列的值为11;这意味着顶点 1 到顶点 7 的距离是 11.
等等...