Java用邻接矩阵存储图的示例代码

目录一、点睛1.无向图的邻接矩阵2.有向图的邻接矩阵3.网的邻接矩阵二、算法步骤三、实现四、测试

一、点睛

邻接矩阵通常采用一个一维数组存储图中节点的信息，采用一个二维数组存储图中节点之间的邻接关系。

邻接矩阵可以用来表示无向图、有向图和网。

1.无向图的邻接矩阵

在无向图中，若从节点 Vi 到节点 Vj 有边，则邻接矩阵 M[i][j] = M[j][i ]= 1,否则 M[i][j] = 0。

无向图的邻接矩阵的特定如下。

a 无向图的邻接矩阵是对称矩阵，并且是唯一的。

b 第 I 行或第 i 列非零的个数正好是第 i 个节点的度。

2.有向图的邻接矩阵

在有向图中，若从节点 Vi 到节点 Vj 有边，则邻接矩阵 M[i][j]=1，否则 M[i][j]=0 。

有向图的邻接矩阵的特定如下。

a 有向图的邻接矩阵不一定是对称的。

b 第 i 行非零元素的个数正好是第 i 个节点的出度，第 i 列非零元素的个数正好是第 i 个节点的入度。

3.网的邻接矩阵

网是带权图，需要存储边的权值，则邻接矩阵表示为：M[i][j] = Wij,其他情况为无穷大。

二、算法步骤

1 输入节点数和边数。

2 依次输入节点信息，将其存储到节点数组 Vex[] 中。

3 初始化邻接矩阵，如果是图，则将其初始化为0，如果是网，则将其初始化为无穷大。

4 依次输入每条边依附的两个节点，如果是网，则还需要输入该边的权值。

如果是无向图，则输入a,b，查询节点a、b在节点数组 Vex[] 中的存储下标 i、j，让 Edge[i][j]=Edge[j][i]=1。如果是有向图，则输入a,b，查询节点a、b在节点数组 Vex[] 中的存储下标 i、j，让 Edge[i][j]=1。如果是无向网，则输入a，b，w，查询节点a、b在节点数组 Vex[] 中的存储下标 i、j，让 Edge[i][j]=Edge[j][i]=w。如果是有向网，则输入a，b，w，查询节点a、b在节点数组 Vex[] 中的存储下标 i、j，让 Edge[i][j]=w。

三、实现

package graph;

import java.util.Scanner;

public class CreateAMGraph {

static final int MaxVnum = 100; // 顶点数最大值

static int locatevex(AMGraph G, char x) {

for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标

if (x == G.Vex[i])

retuDWJqwmFhrn i;

return -1; // 没找到

}

static void CreateAMGraph(AMGraph G) {

Scanner scanner = new Scanner(System.in);

int i, j;

char u, v;

System.out.println("请输入顶点数：");

G.vexnum = scanner.nextInt();

System.out.println("请输入边数:");

G.edgenum = scanner.nextInt();

System.out.println("请输入顶点信息:");

// 输入顶点信息，存入顶点信息数组

for (int k = 0; k < G.vexnum; k++) {

G.Vex[k] = scanner.next().charAt(0);

}

//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大

for (int m = 0; m < G.vexnum; m++)

for (int n = 0; n < G.vexnum; n++)

G.Edge[m][n] = 0;

System.out.println("请输入每条边依附的两个顶点：");

while (G.edgenum-- > 0) {

u = scanner.next().charAt(0);

v = scanner.next().charAt(0);

i = locatevex(G, u);// 查找顶点 u 的存储下标

j = locatevex(G, v);// 查找顶点 v 的存储下标

if (i != -1 && j != -1)

G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1

else {

System.out.println("输入顶点信息错！请重新输入！");

G.edgenum++; // 本次输入不算

}

}

}

static void print(AMGraph G) { // 输出邻接矩阵

System.out.println("图的邻接矩阵为：");

for (int i = 0; i < G.vexnum; i++) {

for (int j = 0; j < G.vexnum; j++)

System.out.print(G.Edge[i][j] + "\t");

System.out.println();

}

}

public static void main(String[] args) {

AMGraph G = new AMGraph();

CreateAMGraph(G);

print(G);

}

}

class AMGraph {

char Vex[] = new char[CreateAMGraph.MaxVnum];

int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum];

int vexnum; // 顶点数

int edgenum; // 边数

}

四、测试

绿色为输入，白色为输出。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。