数据结构(Java随笔)—图

　

java数据结构

图（Graph）——非线性数据结构，现实的图结构模型有通信网络，交通网络，人际关系网络等，图结构的组织形式比树结构更为复杂，因此，图结构对存储和遍历的要求更高。

一个典型的图结构包括如下两个部分：

• 顶点（Vertex）：图中的数据元素。
• 边（Edge）：图中连接这些顶点的线。

图结构的数学形式：G=（V，E）或G=（V（G），E（G））：

• V（G）：图中所有顶点的集合（数字或字母），必须为非空，即图至少包含一个顶点。
• E（G）：图中所有边的集合，每条边由所连接的两个顶点表示，可以为空，即图可以没有边。

图又分为有向图与无向图：

• 无向图：边没有方向性，即（A、B）与（B、A）表示同一条边，利用这个性质，保存边的邻接数组的左下方与右上方对称（edgeWeight[i][j]=edgeWeight[j][i]）
• 有向图：边是有方向性的，即（A、B）与（B、A）表示两条不同的边

顶点的度（Degree）：连接该顶点的边的数量

• 无向图：D（V）。
• 有向图：D（V）=ID（V）+OD（V），即一个顶点的总度等于入度和出度之和。

邻接顶点：

• 无向图：一条边的两个顶点互为邻接顶点。
• 有向图：一个顶点可能包含入边顶点和出边顶点。

无向完全图：任意两个顶点之间都存在一条边。

有向完全图：任意两个顶点之间都存在两条边。

权（Weight）：将边表示为某个数值，这个数值就称为该边的权。

遍历图：遍历图，就是逐个访问图中的所有顶点，由于图中多对多的关系，可能存在重复访问同一顶点，所以为了避免这种情况，在图的结构设计时设置了一个数组isTra[n]（true/false），来确定某一顶点是否已经被遍历。

常用的遍历图的方法有两种：广度优先法和深度优先法；这里的遍历采用的是深度优先。

图结构的实现步骤为：

1. 定义图结构（GraphMatrix）
2. 建立图（添加数据）（creatGraph）
3. 清空图（clearGraph）
4. 显示图（outGraph）
5. 遍历图（traversalGraph）深度优先

代码实现：

一、定义图结构

GraphMatrix gMatrix;// 定义全局头引用

	// 定义图结构
	class GraphMatrix {
		static final int VARTEXMAX = 20;// 定义顶点最大个数
		char[] vertex = new char[VARTEXMAX];// 数组保存顶点
		char graphType;// 图的类型(0(无向图),1(有向图))
		int vertexNum;// 顶点个数
		int edgeWeightNum;// 边的条数
		int[][] edgeWeight = new int[VARTEXMAX][VARTEXMAX];// 保存边的权
		boolean[] isTra = new boolean[VARTEXMAX]; // 遍历图时，保存顶点是否已被遍历
	}

二、创建图

// 建立图(添加数据)
	void creatGraph(scanner input) {
		int i, j, n = 0;
		if ((gMatrix = new GraphMatrix()) != null) {
			// 1、首先输入图的类型
			do {
				System.out.print("图的类型(0(无向图),1(有向图))：");
				gMatrix.graphType = (char) input.next().charAt(0);
			} while (gMatrix.graphType != '0' && gMatrix.graphType != '1');
			// 2、输入顶点个数
			do {
				System.out.print("顶点个数(1——20):");
				gMatrix.vertexNum = input.nextint();
			} while (gMatrix.vertexNum < 1 || gMatrix.vertexNum > 20);
			// 3、输入边的条数
			do {
				System.out
						.print("边的条数(0——"
								+ (gMatrix.vertexNum * gMatrix.vertexNum - gMatrix.vertexNum)
								+ "):");
				gMatrix.edgeWeightNum = input.nextInt();
			} while (gMatrix.edgeWeightNum < 0
					|| gMatrix.edgeWeightNum > (gMatrix.vertexNum
							* gMatrix.vertexNum - gMatrix.vertexNum));
			// 4、输入顶点
			System.out.print("输入顶点(空格隔开):");
			for (int k = 0; k < gMatrix.vertexNum; k++) {
				gMatrix.vertex[k] = input.next().charAt(0);
			}
			// 5、输入边的权
			if (gMatrix.edgeWeightNum == 0) {
				System.out.println("一个顶点不能构成边");
				return;
			}
			do {
				System.out.print("输入边(顶点1  顶点2  权值)：");
				char eStart = input.next().charAt(0);
				char eEnd = input.next().charAt(0);
				int eWeight = input.nextInt();
				for (i = 0; gMatrix.vertex[i] != eStart
						&& i < gMatrix.vertexNum; i++)
					;
				for (j = 0; gMatrix.vertex[j] != eEnd && j < gMatrix.vertexNum; j++)
					;
				if (i == gMatrix.vertexNum || j == gMatrix.vertexNum) {
					System.out.println("顶点不存在！");
				} else {
					gMatrix.edgeWeight[i][j] = eWeight;
					n++;
					if (gMatrix.graphType == '0') {
						gMatrix.edgeWeight[j][i] = eWeight;
					}
				}
			} while (n < gMatrix.edgeWeightNum);
		}
	}

三、清空图

// 清空图
	void clearGraph() {
		for (int i = 0; i < gMatrix.vertexNum; i++) {// 循环清空顶点
			gMatrix.vertex[i] = 0;
		}
		for (int i = 0; i < gMatrix.vertexNum; i++) {// 循环清空权值(设置为0)
			for (int j = 0; j < gMatrix.vertexNum; j++) {
				gMatrix.edgeWeight[i][j] = 0;
			}
		}
		System.out.println("清空成功");
	}

四、显示图

// 显示图
	void outGraph() {
		System.out.print("    ");// 排版
		for (int i = 0; i < gMatrix.vertexNum; i++) {// 第一行输出顶点
			System.out.print(gMatrix.vertex[i] + "  ");
		}
		System.out.println("");// 换行
		for (int i = 0; i < gMatrix.vertexNum; i++) {
			System.out.print(gMatrix.vertex[i] + "   ");// 每行第一个位置输出一个顶点
			for (int j = 0; j < gMatrix.vertexNum; j++) {
				System.out.print(gMatrix.edgeWeight[i][j] + "  ");
			}
			System.out.println("");// 换行
		}
	}

五、遍历图

// 遍历图——分两步
	// 1、递归遍历单顶点
	void traversalGraphByRecursion(int n) {// 传入顶点所在位置
		int i;
		gMatrix.isTra[n] = true;// 标记该顶点已被遍历
		System.out.print("->" + gMatrix.vertex[n]);// 输出该顶点
		for(i = 0; i < gMatrix.vertexNum; i++) {// 循环递归其他顶点
			if (gMatrix.edgeWeight[n][i] != 0 && !gMatrix.isTra[i]) {
				traversalGraphByRecursion(i);
			}
		}
	}

	// 2、深度优先遍历
	void traversalGraph() {
		int k;
		// 图为空错误处理
		if (gMatrix == null) {
			System.out.println("图不存在!");
			return;
		}
		// 循环设置帮助数组isTra的值为false
		for (int i = 0; i < gMatrix.vertexNum; i++) {
			gMatrix.isTra[i] = false;
		}
		//深度遍历
		for (k = 0; k < gMatrix.vertexNum; k++) {
			if (!gMatrix.isTra[k]) {
				traversalGraphByRecursion(k);
			}
		}
		System.out.println("");
	}

六、运行测试

public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		Graph gr = new Graph();
		while (true) {
			System.out.println("请输入：0(退出),1(添加),2(清空),3(显示),4(遍历)");
			int i = in.nextInt();
			switch (i) {
			case 0:
				return;
			case 1:
				gr.creatGraph(in);
				break;
			case 2:
				gr.clearGraph();
				break;
			case 3:
				gr.outGraph();
				break;
			case 4:
				gr.traversalGraph();
				break;
			default:
				break;
			}
		}
	}

相关阅读

java.lang.StringIndexOutOfBoundsException: String

字符串截取下标越界   出错代码 @GetMapping("/edit") //@RequiresPermissions("erp:enquirySheet:edit") public String

使用Java生成的ZIP压缩包解压时出现不可预料的压缩文

使用Java生成的ZIP压缩包解压时出现不可预料的压缩文件末端的解决方案 问题描述： 如下图所示，在解压Java程序生成的ZIP压缩包时出

JavaScript权威指南(第6版)(中文版).pdf

pdf 电子版书籍， 百度云盘：[JavaScript权威指南(第6版)(中文版)] 提取密码：b0tf

javaBean

7.1 JavaBean介绍 7.1.1 javaBean 概述 起初，JavaBean的目的是为了将可以重复使用的代码进行打包，在传统的应用中，JavaBean主要用于

赛码网-计算器的新功能（Java实现）

题目描述 当你学一些可视化程序设计语言时，老师经常会让你设计并且编程做出一个计算器，这时也许你会仿照windows系统自