luoweifu

浏览: 60970 次
性别:
来自: 北京

最近访客更多访客>>

艾伦蓝

lappaport

oldfaceold

阿拉拉

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (69)

社区版块

存档分类

图(3)——邻接链表法

邻接链表法

基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。

第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。

1结点结构与邻接链表示例

链表中的结点称为表结点，每个结点由三个域组成，如图(a)所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。

每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图(b)所示。链域(firstarc)指向链表中的第一个结点，数据域(data)存储顶点名或其他信息。

在图的邻接链表表示中，所有顶点结点用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量，向量的下标指示顶点的序号。

用邻接链表存储图时，对无向图，其邻接链表是唯一的，如图7-10所示；对有向图，其邻接链表有两种形式，如图7-11所示。

2邻接表法的特点

◆表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；

◆在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；

◆在无向图，顶点Vi的度是第i个链表的结点数；

◆对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表；逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表；

◆在有向图中，第i个链表中的结点数是顶点Vi的出(或入)度；求入(或出)度，须遍历整个邻接表；

◆在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；

3结点及其类型定义

顶点Vererex.java

package datastructure.graph;

import datastructure.list.LinkList;
import datastructure.list.List;
/**
 * 图的顶点
 * @author luoweifu
 *
 */
public class Vertex{
	private Object data;
	private ArcEdge firstArc;
	/**
	 * 构造函数
	 */
	public Vertex() {
		data = null;
		firstArc = null;
	}
	/**
	 * 构造函数
	 * @param data 顶点的数据
	 */
	public Vertex(Object data) {
		this.data = data;
		this.firstArc = null;
	}
	/**
	 * 获得顶点的数据
	 * @return　顶点的数据
	 */
	public Object getData() {
		return data;
	}
	/**
	 * 设置顶点的数据
	 * @param data 顶点的数据
	 */
	public void setData(Object data) {
		this.data = data;
	}
	/**
	 * 获得第一个孤结点
	 * @return
	 */
	public ArcEdge getFirstArc() {
		return firstArc;
	}
	/**
	 * 设置第一个孤结点
	 * @param firstArc
	 */
	public void setFirstArc(ArcEdge firstArc) {
		this.firstArc = firstArc;
	}
	@Override
	public boolean equals(Object obj) {
		Vertex v = (Vertex)obj;
		if(data.equals(v.getData()) )//&&  firstArc.equals(v.getFirstArc())
			return true;
		return false;
	}
	@Override
	public String toString() {
		return data + "  " + firstArc;
	}
	
}

孤结点ArcEdge.java

package datastructure.graph;

/**
* 弧结点定义
* @author luoweifu
*
*/
public class ArcEdge extends Edge{
	private Vertex vertex;
	private ArcEdge prior;
	private ArcEdge next;
	/**
	 * 构造函数
	 */
	public ArcEdge() {
		super();
	}
	/**
	 * 构造函数
	 * @param weight　权值
	 */
	public ArcEdge(double weight) {
		super(weight);
		prior = null;
		next = null;
	}
	/**
	 * 构造函数
	 * @param info 边的信息
	 * @param weight 权值
	 */
	public ArcEdge(Object info, double weight) {
		super(info, weight);
		prior = null;
		next = null;
	}
	/**
	 * 构造函数
	 * @param info 边的信息
	 * @param weight 权值
	 * @param vertex 顶点
	 */
	public ArcEdge(Object info, double weight, Vertex vertex) {
		this(info, weight);
		this.vertex = vertex;
		prior = null;
		next = null;
	}
	/**
	 * 获得顶点数据
	 * @return
	 */
	public Vertex getVertex() {
		return vertex;
	}
	/**
	 * 设置顶点
	 * @param vertex
	 */
	public void setVertex(Vertex vertex) {
		this.vertex = vertex;
	}
	/**
	 * 获得上一个孤结点
	 * @return
	 */
	public ArcEdge getPrior() {
		return prior;
	}
	/**
	 * 设置上一个孤结点
	 * @param prior
	 */
	public void setPrior(ArcEdge prior) {
		this.prior = prior;
	}
	/**
	 * 获得下一个孤结点
	 * @return
	 */
	public ArcEdge getNext() {
		return next;
	}
	/**
	 * 设置下一个孤结点
	 * @param next
	 */
	public void setNext(ArcEdge next) {
		this.next = next;
	}

	@Override
	public int compareTo(Object o) {
		double w2 = ((Edge)o).getWeight();
		if(this.weight< w2)
			return -1;
		else if(this.weight > w2)
			return 1;
		return 0;
	}
	
	@Override
	public boolean equals(Object obj) {
		ArcEdge arc = (ArcEdge)obj;
		if(this.next == arc.next && this.weight == arc.weight)
			return true;
		return false;
	}

	@Override
	public Object getFirstVertex() {
		return prior.vertex.getData();
	}


	@Override
	public Object getSecondVertex() {
		return vertex.getData();
	}
}