java 图的邻接表实现图的各种算法

java 图的邻接表实现图的各种算法，增加数据结构知识学习

/**
 * Name:Dijstra算法，基于邻接表
 * Author:杨寅
 * Date:2009/03/16
 */
package dijkstra;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.linkedList;
import java.util.ListIterator;

import gdatastructure.Graph;

public class Gdijkstra {
	
	int dvalue[];
	int shortest[];
	int source = 0;
	
	private Graph mygraph;
	
	public Gdijkstra（Graph mygraph）{
		this.mygraph = mygraph;
		dvalue = new int[mygraph.size（） + 1];
		shortest = new int[mygraph.size（） + 1];
	}
	//用户交互，提示用户输入源点
	public void userInterface（）
	{
		System.out.println（“/*** The Dijkstra Algorithm ***/“）;
		System.out.println（“Input your source node:“）;
		System.out.print（“$“）;
		BufferedReader in =	new BufferedReader（new InputStreamReader（ System.in））;
		try{
			this.source = Integer.parseInt（in.readLine（）.trim（））;
		}catch（Exception e）
		{
			
		}
		runDijkstra（）;
		showResults（）;
	}
	private void initializeSingleSource（）
	{
		for（int i = 1; i <= mygraph.size（）; i++）
		{
			dvalue[i] = -1; // -1 is the maximum value
			shortest[i] = 0;
		}
		dvalue[source] = 0;
	}
	//松弛算法
	private void relax（int u int v int w）
	{
		int edgevalue = mygraph.getEdgeValue（u v）;
		if（dvalue[v] == -1 || dvalue[v] > dvalue[u] + edgevalue）
		{
			dvalue[v] = dvalue[u] + edgevalue;
			shortest[v] = u;
		}
	}
	//运行Dijkstra算法
	public void runDijkstra（）
	{
		//初始化松弛参数
		this.source = source;
		initializeSingleSource（）;
		//初始化结点集合S和Q
		linkedList S = new linkedList（）;
		linkedList Q = new linkedList（）;
		for（int i = 1; i <= mygraph.size（）; i++）
			Q.add（i）;
		while（Q.size（） != 0）
		{
			ListIterator iterator1 = Q.listIterator（）;
			ListIterator iterator2 = null;
			int minvalue = -1;
			int minpos = -1;
			while（iterator1.hasNext（））
			{
				int curpos = iterator1.next（）;
				if（（minvalue == -1 || dvalue[curpos] < minvalue） && dvalue[curpos] != -1）
				{
					minvalue = dvalue[curpos];
					minpos = curpos;
				}
			}
			Q.remove（Q.indexOf（new Integer（minpos）））;
			S.add（minpos）;
			
			iterator2 = mygraph.getAllNeighbours（minpos）.listIterator（）;
			while（iterator2.hasNext（））
			{
				int pos = iterator2.next（）;
				relax（minpos pos mygraph.getEdgeValue（minpos pos））;
			}
		}
	}
	//递归法打印最短路径
	private void printfPath（int source int dest）
	{
		if（dest == source）
			System.out.print（source）;
		else
		{
			printfPath（source shortest[dest]）;
			System.out.print（“->“ + dest）;
		}
	}
	//打印结果
	public void showResults（）
	{
		System.out.println（“/*** The Dijkstra Results source point is “ + source+ “ ***/“）;
		for（int i = 1; i <= mygraph.size（）; i++）
		{
			if（dvalue[i] != -1 && i != source）
			{
				System.out.println（“*******************“）;
				System.out.println（“To node [“ + i + “]“）;
				System.out.println（“Minimum path length: “ + dvalue[i]）;
				printfPath（source i）;
				System.out.println（““）;
				
			}
		}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        257  2009-03-16 15:27  GraphAlgorithm\.classpath

     文件        390  2009-03-15 17:34  GraphAlgorithm\.project

     文件       3818  2009-03-17 11:15  GraphAlgorithm\bin\dijkstra\Gdijkstra.class

     文件       2607  2009-03-17 17:01  GraphAlgorithm\bin\gconnectivity\StrongConnectivity.class

     文件       1111  2009-03-17 11:22  GraphAlgorithm\bin\gdatastructure\AutoBuildGraph.class

     文件       1004  2009-03-16 22:10  GraphAlgorithm\bin\gdatastructure\Color.class

     文件       4049  2009-03-17 11:29  GraphAlgorithm\bin\gdatastructure\Graph.class

     文件       1199  2009-03-17 11:20  GraphAlgorithm\bin\gdatastructure\link.class

     文件       1261  2009-03-17 11:20  GraphAlgorithm\bin\gdatastructure\Vertex.class

     文件        734  2009-03-17 11:20  GraphAlgorithm\bin\gdatastructure\VNode.class

     文件        728  2009-03-17 16:39  GraphAlgorithm\bin\packagefortest\Main.class

     文件       1873  2009-03-17 17:01  GraphAlgorithm\bin\tool\DFSBasic.class

     文件       2532  2009-03-17 17:17  GraphAlgorithm\bin\tool\DFSSuc1.class

     文件       3141  2009-03-17 11:15  GraphAlgorithm\src\dijkstra\Gdijkstra.java

     文件       1641  2009-03-17 17:01  GraphAlgorithm\src\gconnectivity\StrongConnectivity.java

     文件       1468  2009-03-17 11:22  GraphAlgorithm\src\gdatastructure\AutoBuildGraph.java

     文件         72  2009-03-16 22:08  GraphAlgorithm\src\gdatastructure\Color.java

     文件       3442  2009-03-17 11:29  GraphAlgorithm\src\gdatastructure\Graph.java

     文件       1042  2009-03-17 11:20  GraphAlgorithm\src\gdatastructure\link.java

     文件        845  2009-03-17 11:20  GraphAlgorithm\src\gdatastructure\Vertex.java

     文件        450  2009-03-17 11:20  GraphAlgorithm\src\gdatastructure\VNode.java

     文件       1472  2009-03-17 16:39  GraphAlgorithm\src\packagefortest\Main.java

     文件       1327  2009-03-17 17:01  GraphAlgorithm\src\tool\DFSBasic.java

     文件       1879  2009-03-17 17:17  GraphAlgorithm\src\tool\DFSSuc1.java

     文件        329  2009-03-17 17:30  GraphAlgorithm\修改记录.txt

     文件      34816  2009-04-15 22:23  GraphAlgorithm\模块简要说明.doc

     目录          0  2009-03-16 22:10  GraphAlgorithm\bin\dijkstra

     目录          0  2009-03-16 22:10  GraphAlgorithm\bin\gconnectivity

     目录          0  2009-03-17 10:35  GraphAlgorithm\bin\gdatastructure

     目录          0  2009-03-17 11:21  GraphAlgorithm\bin\packagefortest

............此处省略12个文件信息