`

图 邻接矩阵表示法 代码实现 java

阅读更多

 

package abc.Dijkstra.pack3;

public class MGraph {
	int vertexNum;
	int [][] adjMatrix;
	
	MGraph(int vertexNum) {
		this.vertexNum = vertexNum;
		adjMatrix = new int[vertexNum][vertexNum];
	}
	
	void addArc(int vi, int vj) {
		if(vi < 1 || vi > vertexNum)
			throw new RuntimeException("Not contain Vertex " + vi);
		if(vj < 1 || vj > vertexNum)
			throw new RuntimeException("Not contain Vertex " + vj);
		adjMatrix[vi-1][vj-1] = 1;
	}
	
	void print() {
		System.out.print("   ");
		for(int i = 1; i <= vertexNum; i++)
			System.out.print(String.format("%2d", i));
		System.out.println();
		
		int lable = 1;
		for(int[] a : adjMatrix) {
			System.out.print(lable++ + " [");
			for(int i : a)
				System.out.print(String.format("%2d", i));
			System.out.println(" ]");
		}
	}
	
	static MGraph createUndigraph() {
		MGraph mGraph = new MGraph(4);
		mGraph.addArc(1, 2);	mGraph.addArc(1, 3);	mGraph.addArc(1, 4);
		mGraph.addArc(2, 1);	mGraph.addArc(2, 4);
		mGraph.addArc(3, 1);
		mGraph.addArc(4, 1);	mGraph.addArc(4, 2);
		return mGraph;
	} // sample for 8.10 undigraph adjancet graph.
	
	static MGraph createDigraph() {
		MGraph mGraph = new MGraph(4);
		mGraph.addArc(1, 2);
		mGraph.addArc(2, 4);		
		mGraph.addArc(4, 2);	mGraph.addArc(4, 3);
		return mGraph;
	} // sample for 8.11 undigraph adjancet graph.

	public static void main(String[] args) {
		MGraph.createUndigraph().print();
		MGraph.createDigraph().print();
	}

}

 

输出 写道
1 2 3 4
1 [ 0 1 1 1 ]
2 [ 1 0 0 1 ]
3 [ 1 0 0 0 ]
4 [ 1 1 0 0 ]
1 2 3 4
1 [ 0 1 0 0 ]
2 [ 0 0 0 1 ]
3 [ 0 0 0 0 ]
4 [ 0 1 1 0 ]

 

分享到:
评论

相关推荐

    图的邻接矩阵实现及深度优先搜索(JAVA)

    在这个话题中,我们将深入探讨如何使用Java语言实现图的邻接矩阵表示法以及如何进行深度优先搜索(DFS)。 首先,邻接矩阵是一种二维数组,用于存储图中节点之间的连接信息。如果节点i和节点j之间存在边,那么邻接...

    数据结构 作业 图的遍历

    在提供的压缩包文件中,你可能会找到用不同编程语言(如C++、Java、Python等)实现的DFS和BFS算法,它们可能包含了递归和非递归版本,以及如何表示图(邻接矩阵或邻接表)。通过理解并运行这些代码,你可以更好地...

    java实现维诺图

    比如,可以使用优先队列(PriorityQueue)存储事件,用邻接表或邻接矩阵表示边的连接关系。 5. **交互性**:描述提到的“点击即可生成维诺图”,意味着需要实现用户交互功能。在Java中,可以监听鼠标事件,当用户...

    Java实现图结点着色图形化演示

    图的实现通常有两种方式:邻接矩阵和邻接表。邻接矩阵是一个二维数组,其中的元素表示节点对之间是否存在边。邻接表则是为每个节点维护一个边的列表,节省了空间,尤其在处理稀疏图(边的数量远小于节点数量的平方)...

    数据结构图方法包java语言

    - **邻接矩阵**:邻接矩阵是一个二维数组,用于表示图中任意两个顶点之间的连接。如果两个顶点之间有边,则对应元素为1,否则为0。邻接矩阵适用于稠密图(边的数量接近顶点数量的平方)。 2. **图的遍历**: - **...

    数据结构与算法Java语言描述 部分代码实现

    7. **图**:图数据结构表示对象之间的关系,Java中没有内置的图类,但可以通过邻接列表或邻接矩阵实现。图的常见算法有深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(如Dijkstra、Floyd)等。 8. **...

    《java算法》部分源代码

    源代码可能会涵盖这些算法的Java实现,帮助理解图的邻接矩阵或邻接表表示。 6. **贪心算法**:贪心算法通常用于解决局部最优解也能达到全局最优的问题,如霍夫曼编码、活动选择问题等。源代码会展示如何通过每次...

    java实现哈密顿路径,递归和非递归两种方式

    在Java代码中,可能会包含一个图的表示(如邻接矩阵或邻接表),以及相应的递归和非递归算法实现。这些实现可能包括以下关键部分: 1. 图的初始化:创建一个图结构,用数组或链表存储顶点及其邻接关系。 2. 递归...

    数据结构(Java版)源代码

    Java中可以使用`java.util.ArrayList`或`java.util.LinkedList`来表示邻接列表,或者用`int[][]`数组表示邻接矩阵来实现图。 8. **堆**:堆是一种特殊的树形数据结构,通常满足最大堆或最小堆性质,即父节点的值...

    java实现算法的代码

    这些都需要用到优先队列和邻接矩阵或邻接表来表示图。 7. **动态规划的Java实现**:动态规划是一种解决最优化问题的方法,如背包问题、斐波那契数列等。在Java中,我们可以使用二维数组来存储子问题的解。 8. **...

    基于Java的中国地图着色演示程序

    2. **地图数据结构**:地图以某种形式的数据结构存储,如邻接矩阵或邻接表,表示各省份之间的相邻关系。 3. **颜色分配逻辑**:根据回溯法,程序会尝试给每个未着色的省份分配颜色,如果发现违反了相邻省份不同色的...

    java迷宫程序及代码

    3. **迷宫表示**:迷宫通常可以用二维数组或者邻接矩阵来表示,其中0表示可通行,1表示墙壁。代码中应该有关于如何创建和操作这种表示的函数。 4. **游戏界面**:如果这是一个完整的迷宫游戏,那么可能会有一个用户...

    java最短路算法代码

    构造函数接收一个二维数组`G`作为输入,该数组表示了图的邻接矩阵,其中`G[i][j]`表示从顶点`i`到顶点`j`的边的权重,如果`i`和`j`之间没有直接相连的边,则`G[i][j]`被设为一个极大值`max`。 #### 主要算法流程 1...

    数据结构和算法课程配套实现代码(java).zip

    这个Java代码库中可能包含了以上数据结构和算法的实现,通过阅读和实践这些代码,可以加深对它们的理解,并提升编程技能。记得在学习过程中,不仅要理解代码的逻辑,还要思考如何优化和改进,以适应不同的场景和需求...

    编译原理 DFA编程实现

    在C++中实现DFA,首先需要设计一个数据结构来表示状态和状态转移。常见的做法是使用枚举类型来定义状态,用哈希表或者数组来存储状态转移关系。例如,可以用`std::unordered_map, int&gt;`来存储每个状态对于输入字符的...

    数据结构—图及其应用(交通问题,实现最短路径、最短时间、最少费用查询).rar

    同时,根据所选的图表示法(邻接矩阵或邻接表),编写相应的查找和更新最短路径的代码。 6. **交通咨询模拟系统** 设计一个城市交通咨询系统,可以通过用户输入起始和目的地,结合图的最短路径算法,提供最佳路线...

    贪心算法法-单源最短路径 java

    - 创建二维数组 `a[][]` 存储图的邻接矩阵表示;创建一维数组 `dist[]` 和 `prev[]` 分别用于存储当前顶点到源点的最短距离和前驱顶点。 2. **初始化**: - 初始化 `dist[]` 数组,将所有顶点到源点的距离设为...

    数据结构与算法(JAVA语言版)含源代码

    - **图结构**:用于表示对象之间的关系,如邻接矩阵和邻接表。它们在路由算法、社交网络分析等领域中很重要。 - **哈希表**:利用哈希函数快速查找和存储数据,支持O(1)的平均时间复杂度。 2. **算法**: - **...

    java连连看源代码

    开发者需要考虑如何优化数据结构以提高查找效率,例如使用邻接矩阵表示图案间的连接关系。 4. **算法设计**:连连看游戏中的关键算法包括寻找匹配路径和判断游戏结束。寻找匹配路径可能采用深度优先搜索(DFS)或...

    数据结构和算法必知必会的50个代码实现

    6. 图:用于表示对象间的关系,如邻接矩阵和邻接表。 接下来,我们讨论算法部分。常见的算法包括排序(如冒泡排序、插入排序、快速排序、归并排序、堆排序)、搜索(如二分查找、深度优先搜索、广度优先搜索)、图...

Global site tag (gtag.js) - Google Analytics