文档章节

图(3)——邻接链表法

自由的角马
 自由的角马
发布于 2015/01/10 13:58
字数 1740
阅读 46
收藏 0

邻接链表法

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

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

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

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

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

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

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

邻接表法的特点

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

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

 ◆ 在无向图,顶点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();
	}
}

 邻接链表法表示的图ListGraph.java

package datastructure.graph;

import datastructure.list.ArrayList;
import datastructure.list.List;
import datastructure.queue.ArrayQueue;
import datastructure.queue.Queue;

public class ListGraph implements Graph {
	private List<Vertex> vertexs;
	private int edgeNum; //边的条数 
	private enum Visit{unvisited, visited};
	
	public ListGraph() {
		vertexs = new ArrayList();
	}
	public List getVertexs() {
		return vertexs;
	}
	public ListGraph(Object[] vexs) {
		this();
		for(int i=0; i<vexs.length; i++) {
			vertexs.add(new Vertex(vexs[i]));
		}
	}

	
	private Vertex find(Object v) {
		Vertex vex = new Vertex(v);
		int i = vertexs.indexOf(vex);
		if(i<0) {
			return null;
			//throw new ArrayIndexOutOfBoundsException("顶点" + v + "不存在!");
		}
		return (Vertex)vertexs.get(i);
	}


	@Override
	public void addEdge(Object v1, Object v2, double weight) {
		Vertex vex1 = find(v1);
		Vertex vex2 = find(v2);
		if(vex1 != null && vex2 != null) {
			ArcEdge e = new ArcEdge(null, weight, vex2);
			if(vex1.getFirstArc() == null) {
				vex1.setFirstArc(e);
			} else {
				ArcEdge arc = vex1.getFirstArc();
				while(arc.getNext() != null) {
					arc = arc.getNext();
				}
				arc.setNext(e);
				e.setPrior(arc);
			}
			edgeNum ++;
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点" + v1 + "或" + v2 + "不存在!");
		}
	}


	@Override
	public void addEdge(Object v1, Object v2, Object info, double weight) {
		Vertex vex1 = find(v1);
		Vertex vex2 = find(v2);
		if(vex1 != null && vex2 != null) {
			ArcEdge e = new ArcEdge(info, weight, vex2);
			if(vex1.getFirstArc() == null) {
				vex1.setFirstArc(e);
			} else {
				ArcEdge arc = vex1.getFirstArc();
				while(arc.getNext() != null) {
					arc = arc.getNext();
				}
				arc.setNext(e);
				e.setPrior(arc);
			}
			edgeNum ++;
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点" + v1 + "或" + v2 + "不存在!");
		}
	}


	@Override
	public void addVex(Object v) {
		vertexs.add(new Vertex(v));
	}


	@Override
	public String bfs(Object o) {
		// ----------------该方法还有点问题-------------
		Visit visit[] = new Visit[vertexs.size()];
		for(int i=0; i<vertexs.size(); i++)
			visit[i] = Visit.unvisited;
		StringBuilder sb = new StringBuilder();
		Vertex vex = new Vertex(o);//find(o);
		bfs(vex, visit, sb);
		return sb.toString();
	}


	private void bfs(Vertex vex, Visit[] visit, StringBuilder sb) {
		Queue queue = new ArrayQueue();
		
		int n = vertexs.indexOf(vex);
		sb.append(vex.getData() + "\t");
		visit[n] = Visit.visited;
		
		queue.push(vex);
		while(!queue.isEmpty()) {
			Vertex u = (Vertex) queue.deQueue();
			Vertex v = getFirstVertex(u);
			while(null != v) {
				if(Visit.unvisited == visit[vertexs.indexOf(v)]) {
					sb.append(v.getData() + "\t");
					visit[vertexs.indexOf(v)] = Visit.visited;
					queue.push(v);
				}
				v = getNextVertex(u, v);
			}
		}
	}


	@Override
	public String dfs(Object o) {
		// ----------------该方法还有点问题-------------
		Visit visit[] = new Visit[vertexs.size()];
		for(int i=0; i<vertexs.size(); i++)
			visit[i] = Visit.unvisited;
		StringBuilder sb = new StringBuilder();
		Vertex vex = new Vertex(o);//find(o);
		dfs(vex, visit, sb);
		return sb.toString();
	}


	private void dfs(Vertex vex, Visit[] visit, StringBuilder sb) {
		int n = vertexs.indexOf(vex);
		sb.append(vex.getData() + "\t");
		visit[n] = Visit.visited;
		
		Vertex v = getFirstVertex(vex);
		while(null != v) {
			if(Visit.unvisited == visit[vertexs.indexOf(v)])
				dfs(v, visit, sb);
			v = getNextVertex(vex, v);
		}
	}


	@Override
	public void clear() {
		vertexs.clear();
	}


	@Override
	public int getEdgeSize() {
		return edgeNum;
	}


	@Override
	public Object getFirstVertex(Object v) {
		Vertex vex = find(v);
		return getFirstVertex(vex).getData();
	}
	
	private Vertex getFirstVertex(Vertex v) {
		if(v.getFirstArc() != null && v.getFirstArc().getVertex() != null) 
			return v.getFirstArc().getVertex();
		return null;
	}

	@Override
	public Object getNextVertex(Object v1, Object v2) {
		// ----------------该方法还有点问题-------------
		Vertex vex1 = find(v1);
		Vertex vex2 = find(v2);
		System.out.println("v1:" + v1);
		System.out.println("v2:" + v2);
		System.out.println("vex1:" + vex1);
		System.out.println("vex2:" + vex2);
		return getNextVertex(vex1, vex2);
	}
	/**
	 * ----------------该方法还有点问题-------------
	 * @param vex1
	 * @param vex2
	 * @return
	 */
	private Vertex getNextVertex(Vertex vex1, Vertex vex2) {
		ArcEdge arc = vex1.getFirstArc();
		while(arc.getNext() != null && arc.getVertex()!=vex2) {
			arc = arc.getNext();
		}
		if(arc.getVertex() != null)  {
			//System.out.println(arc.getVertex());
			return arc.getNext().getVertex();
		}
		return null;
	}


	@Override
	public int getVertexSize() {
		return vertexs.size();
	}


	@Override
	public void removeEdge(Object v1, Object v2) {
		Vertex vex1 = find(v1);
		Vertex vex2 = find(v2);
		if(vex1 != null && vex2 != null) {
			ArcEdge arc = vex1.getFirstArc();
			while(arc.getNext() != null && arc.getVertex() != vex2) {
				arc = arc.getNext();
			}
			if(arc.getVertex() == vex2) {
				ArcEdge priEdge = arc.getPrior();
				ArcEdge nextEdge = arc.getNext();
				priEdge.setNext(nextEdge);
				nextEdge.setPrior(priEdge);
				edgeNum --;
			} else {
				throw new ArrayIndexOutOfBoundsException("边" + v1 + "到" + v2 + "不存在!");
			}
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点" + v1 + "或" + v2 + "不存在!");
		}
	}


	@Override
	public void removeVex(Object v) {
		for(int i=0; i<vertexs.size(); i++) {
			Vertex vex1 = (Vertex)(vertexs.get(i));
			ArcEdge arc = vex1.getFirstArc();
			if(arc  != null) {
				while(arc.getNext() != null) {
					if(arc.getVertex().getData() == v) {
						removeEdge(vex1, v);
					}
				}
			}
		}
		Vertex vex = find(v);
		if(vex != null) {
			int i = vertexs.indexOf(vex);
			vertexs.remove(i);
		}
		
	}

	@Override
	public String printGraph() {
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<vertexs.size(); i++) {
				Vertex vex = (Vertex) vertexs.get(i);
				sb.append("\n顶点:" + vex.getData() + "\t");
				ArcEdge arc = vex.getFirstArc();
				if(arc != null) {
					sb.append("孤," + arc.getVertex().getData());
					while(arc.getNext() != null) {
						sb.append("\t" + arc.getNext().getVertex().getData());
						arc = arc.getNext();
					}
				}
			}
		return sb.toString();
	}
}


本文转载自:http://blog.csdn.net/luoweifu/article/details/9270895

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
Java实现无向图的建立与遍历

一、基于邻接矩阵表示法的无向图   邻接矩阵是一种利用一维数组记录点集信息、二维数组记录边集信息来表示图的表示法,因此我们可以将图抽象成一个类,点集信息和边集信息抽象成类的属性,...

牛cattle
06/09
0
0
漫画:什么是 “图”?(修订版)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/bjweimengshu/article/details/88801670

程序员小灰
03/25
0
0
小蚂蚁学习数据结构(29)——图的存储表示

图的数组(邻接矩阵)存储表示 方法:将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二位数组中即构成图的数组(邻接矩阵)表示。 无向图的邻接矩阵具有如下特点: 1,它是...

嗜学如命的小蚂蚁
2016/02/04
49
0
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
2018/10/07
0
0
《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构,在查找上比链表有优势,但是在插入与删除上比不上链表。 Java中的数组有长度限制,为int值。在内存模型中,...

刀狂剑痴
2016/05/27
229
0

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
10
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部