7: 图ITeye - 凯发娱乐

7: 图ITeye

2019年02月23日15时16分15秒 | 作者: 鸿晖 | 标签: 节点,链表,单元 | 浏览: 1513

 

邻接表表明法将图以邻接表(adjacency  lists)的方式存储在计算机中。所谓图的邻接表,也就是图的一切节点的邻接表的调集;而对每个节点,它的邻接表就是它的一切出弧。邻接表表明法就是对图的每个节点,用一个单向链表列出从该节点动身的一切弧,链表中每个单元对应于一条出弧。为了记载弧上的权,链表中每个单元除列出弧的另一个端点外,还能够包括弧上的权等作为数据域。图的整个邻接表能够用一个指针数组表明。例如,例7所示的图,邻接表表明为

 

能够很便利的知道  点的邻接点

 

这种结构合适查找极点及邻接点的信息,查极点的度,添加或删去极点和边(弧)也很便利,

但因指针多占用了存储空间,别的,某两极点间是否有边(弧)也不如邻接矩阵那么清楚。

对有向图的邻接表,查极点出度简单,而查极点入度却困难,要遍历整个邻接表。

要想查入度象查出度那样简单,

就要树立逆邻接表

 

 

package com.algorithm.common.graph;
import com.algorithm.common.Bag;
 * 无权重无向图 (邻接表表明)
 * @author lijunqing
public class Graph {
 * 极点数
 private int V;
 * 边数
 private int E;
 * 邻接表
 private Bag Integer [] adj;
 public Graph(int v) {
 this.V=v;
 this.E=0;
 adj=(Bag Integer [])new Bag[V];
 for(int i=0; i i++) { // 初始化邻接表
 adj[i]=new Bag Integer 
 public void addEdge(int v, int w) {
 if(v 0 || v V) {
 throw new IndexOutOfBoundsException();
 if(w 0 || w V) {
 throw new IndexOutOfBoundsException();
 E++;
 adj[v].add(w);
 adj[w].add(v);
 * 回来Iterable能够遍历
 * @param v
 * @return
 public Iterable Integer adj(int v) {
 if(v 0 || v V) {
 throw new IndexOutOfBoundsException();
 return adj[v];
 public int V() {
 return V;
 public int E() {
 return E;

 

 

 

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表凯发娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章