论坛首页 Java企业应用论坛

基于java的图的实现

浏览 6907 次
精华帖 (0) :: 良好帖 (1) :: 新手帖 (8) :: 隐藏帖 (0)
作者 正文
   发表时间:2010-04-16   最后修改:2010-04-16

数据结构(java)版今天看到了图那一章,也按着其大体思路编码。发现作者很多地方实现的很巧妙。

 

类图如下:


 

 

图的表示是基于邻接表实现。

 

EGraph中的vInfos存有当前图中所有的顶点。verMap为 T - Integer键值对,vertextCache为已删除节点的索引栈,但节点删除后只并没有将其从vInfos中移走,只是将其occupied属性值为false,同时将其从verMap中移走,将其索引压入栈中以便插入新节点是使用。


 VertexInfo为储存顶点信息,vertext储存顶点值,edgeList储存以该顶点为起始点的所有边信息。

Edge 为边信息,dest为该边中点在vInfos中的位置,weight为该边的权值。

 

 

 

  

 以下为针对这个图的测试

graph1.dat

 

5

A B C D E

6

A B 3

A C 2

B C 6

C B 4

C D 1

E B 5

 

package com.woxiaoe.ds.graph;

import java.io.File;
import java.util.Scanner;

import junit.framework.TestCase;

public class GraphTest extends TestCase {
	EGraph<String> graph = new EGraph<String>();
	@Override
	protected void setUp() throws Exception {
		Scanner scn = new Scanner(new File("graph1.dat"));

		int vertexNum,edgeNum;
		vertexNum = scn.nextInt();
		for(int i = 0 ; i < vertexNum; i++){
			graph.addVertex(scn.next());
		}
		edgeNum = scn.nextInt();
		for(int i = 0; i < edgeNum; i++){
			graph.addEdge(scn.next(), scn.next(), scn.nextInt());
		}
	}
	public void testReadGraph(){
		System.out.println("边数:" + graph.numberOfEdges());
		System.out.println("顶点数" + graph.numberOfVertices());
		System.out.println("C - D 权值 :" + graph.getWeight("C", "D"));
		graph.setWeight("C", "D", 10);
		System.out.println("更改后的 - D 权值 :" + graph.getWeight("C", "D"));
		System.out.println("删除C - D" + graph.removeEdge("C", "D"));
		System.out.println("删除C-D后边数:" + graph.numberOfEdges());
		System.out.println("删除C-D后顶点数:" + graph.numberOfVertices());
		System.out.println("删除顶点C:" + graph.removeVertex("C"));
		System.out.println("删除顶点C后边数:" + graph.numberOfEdges());
		System.out.println("删除顶点C后顶点数:" + graph.numberOfVertices());
		
	} 

}
 

Output:

边数:6 顶点数5 C - D 权值 :1 更改后的 - D 权值 :10 删除C - Dtrue 删除C-D后边数:5 删除C-D后顶点数:5 删除顶点C:true 删除顶点C后边数:2 删除顶点C后顶点数:4

 


  • 大小: 31.9 KB
  • 大小: 10.6 KB
   发表时间:2010-04-16  
用不了啊 不知道怎么回事
0 请登录后投票
   发表时间:2010-04-16  
whaosoft 写道
用不了啊 不知道怎么回事

你好,哪里报错了,我也去看看
0 请登录后投票
   发表时间:2010-04-17  
测试的例子里面:
Scanner scn = new Scanner(new File("graph1.dat"));
改成这样比较好
Scanner scn = new Scanner(GraphTest.class.getResourceAsStream("graph1.dat")); 



       
       
0 请登录后投票
   发表时间:2010-04-17  
ccxw1983 写道
测试的例子里面:
Scanner scn = new Scanner(new File("graph1.dat"));
改成这样比较好
Scanner scn = new Scanner(GraphTest.class.getResourceAsStream("graph1.dat")); 



       
       

0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics