java图的邻接表

A. java中如何把图用邻接表表示出来

package my.graph;
import java.util.ArrayList;
import java.util.Iterator;
import my.queue.*;
import my.stack.StackX;
/**
* 邻接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20;
private Vertex vertexList[];
private boolean is = false;//是否为有向图
private int nVerts = 0;

private StackX stackX;
private Vertex dfs[];

private Vertex bfs[];
private Queue queue;

public Graph(){
vertexList = new Vertex[MAX_VERTS];
dfs = new Vertex[MAX_VERTS];
bfs = new Vertex[MAX_VERTS];
}
public Graph(int n){
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];

}
public Graph(int n, boolean is){
this.is = is;
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
//////////////////////////////////////////////
public boolean isIs() {
return is;
}
public void setIs(boolean is) {
this.is = is;
}
public Vertex[] getVertexList() {
return vertexList;
}
public Vertex[] getDfs() {
return dfs;
}
public Vertex[] getBfs() {
return bfs;
}

////////////////////////////////////////////////////
/**
* 添加顶点
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts);
vertexList[nVerts] = vertex;
nVerts++;
}
/**
* 添加边
*/
public void addEdge(int start, int end){
vertexList[start].addAdj(vertexList[end]);
if (!is) {vertexList[end].addAdj(vertexList[start]);}
}
/**
* 返回节点个数
* @return
*/
public int getVertsCount(){
return vertexList.length;
}

/**
* 深度优先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs();
return new DfsIterator();
}
/**
* 广度优先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs();
return new BfsIterator();
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayList<Vertex> next = null;
for (int i = 0; i < vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayList<Vertex> next = vertex.getAdj();
if(next == null){ System.out.println(vertex.toString()+" 无连接点");}
else{
System.out.print(vertex.toString()+"有邻接点:");
for (int i = 0; i < next.size(); i++) {
System.out.print("顶点"+next.get(i).label+", ");
}
System.out.println();
}
}

///////////////////////////////////////////////////////////

public void dfs(){
stackX = new StackX(MAX_VERTS);
vertexList[0].isVisted = true;
dfs[0] = vertexList[0];

stackX.push(vertexList[0]);
int dfsIndex = 0;

Vertex vertex;
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek());
if(vertex == null){
stackX.pop();
}else{
vertex.isVisted = true;
dfs[++dfsIndex]=vertex;
stackX.push(vertex);
}
}

for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}

}

public void bfs() {
queue = new Queue(MAX_VERTS);
vertexList[0].isVisted = true;
bfs[0] = vertexList[0];
queue.insert(vertexList[0]);
int bfsIndex = 0;
Vertex vertex;
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove();
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true;
bfs[++bfsIndex] = vertex;
queue.insert(vertex);
}
}

for (int i = 0; i < getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
/**
* 得到一个邻接点
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayList<Vertex> adjVertexs = vertex.getAdj();
for (int i = 0; i < adjVertexs.size(); i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i);
}
}
return null;
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{

int count = 0;
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1;
}
public Object next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub

}

}
//深度优先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super();
}

public Vertex next() {
return dfs[count++];
}
}
//广度优先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super();
}

public Object next() {
return bfs[count++];
}
}
/////////////////////////////////////////////////////////

public static void main(String[] args) {
int nVerts = 10;
int c = 'A'-1;
Vertex vertex;
Graph myGraph = new Graph(nVerts, false);
for (int i = 0; i < nVerts; i++) {
c++;
vertex = new Vertex((char)(c));
myGraph.addVertex(vertex);
}
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 4);
myGraph.addEdge(1, 2);
myGraph.addEdge(2, 3);
myGraph.addEdge(4, 5);
myGraph.addEdge(4, 6);
myGraph.addEdge(5, 8);
myGraph.addEdge(6, 7);
myGraph.addEdge(7, 8);
myGraph.addEdge(8, 9);

System.out.println("深度优先迭代遍历：");
for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());

}

System.out.println("/n广度优先迭代遍历：");
for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());

}
}
}
class Vertex{
public char label;
public boolean isVisted;
public int index;
private ArrayList<Vertex> next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//为节点添加邻接点
public void addAdj(Vertex ver){
if(next == null) next = new ArrayList<Vertex>();
next.add(ver);
}

public ArrayList<Vertex> getAdj(){
return next;
}

public void setIndex(int index){
this.index = index;
}

public String toString(){
return "顶点 "+label+",下标："+index+".";
}
}

代码来自：http://blog.csdn.net/Java2King/article/details/5683429

B. java中的单向链表，栈，串，有哪些对象使用的这些数据结构，还有树，图，广义表这些在JAVA有哪些对象

JAVA把数据结构简化了，提供了不少集合类（collection），用的最多的就是LIST和MAP这个两个接口。LIST和MAP各自对应了多个实现它们的类，比如ArrayList，HashMap等等。其中List就很像C里的链表，它有顺序存放和无序存放的对象。好像没有几个类能严格符合你说的几种数据结构，你可以自己写类来实现相同的功能。没有这么多复杂的数据结构，JAVA才体现出简单易学的特点啊。

C. 数据结构：图的邻接表实现

有的时候我并不能一口吃一个胖子，不是吗？编程也是一样，如果都让别人来帮助你，那么自己永远也难有提高的，其实要想编写好你提出图的问题首先要有一些基础才可以的。只有在基本概念非常熟悉的情况之下，我们才可能自己编写出真正属于自己的程序，而且会让我们的编程变得从容自如。

首先，我们要知道什么是邻接表，说简单点，邻接表是一个特殊数组，数组中的每个非空元素代表一个图的节点，且存放的是一个链表（如果不清楚什么是链表的话，那就看看清华大学严蔚敏版的《数据结构》）的头指针，这个链表是所有与此节点联通的节点的集合。如果还不太清楚的话看看下面的图片

左边的数组，就是所有定点列表啦，右边有6个链表

比如A节点与B，E节点相连，所以第一个链表里分别存放B，E节点（注意这里的B,E节点在邻接表中不直接用字母标出，而是使用B,E节点所在数组的下标表示，故分别为1节点和4节点，这样便于编程）

好啦，如果你明白了什么是邻接表，那么已经成功一半啦，对于图的操作都要修改这个抽象的邻接表。

其次，我们要懂得链表这样的数据结构的操作以及以上这些对于图的操作基本概念（可以看看严蔚敏版的《数据结构》），如果要讲清楚这些可能要讲到第二天的天亮。在这里请原谅我不能够一一讲解，不过你要求的这些基本程序在严蔚敏的那本书中都有源码的（建议不要看别人的源码，看如别人的会很痛苦，自己写反而很轻松的）。如果对链表的操作（主要是指针）还不熟悉，那么请先好好地学习一下链表的编程吧，链表比邻接表要简单得多，可以先简单后复杂，你会在编程的过程之中得到无穷的乐趣。

希望我的这点经验能够对你有些许帮助。

D. 如何实时更新邻接表边的权值java

本系列文章主要学习如何使用JAVA语言以邻接表的方式实现了数据结构---图（Graph），这是第一篇文章，学习如何用JAVA来表示图的顶点。从数据的表示方法来说，有二种表示图的方式：一种是邻接矩阵，其实是一个二维数组；一种是邻接表，其实是一个顶点表，每个顶点又拥有一个边列表。下图是图的邻接表表示。

从图中可以看出，图的实现需要能够表示顶点表，能够表示边表。邻接表指是的哪部分呢？每个顶点都有一个邻接表，一个指定顶点的邻接表中，起始顶点表示边的起点，其他顶点表示边的终点。这样，就可以用邻接表来实现边的表示了。如顶点V0的邻接表如下：

与V0关联的边有三条，因为V0的邻接表中有三个顶点(不考虑V0)。

E. 图的邻接表的时间复杂度问题

其实是O(n + e)，顶点加上边数
那个O(n*e)的意思是每次插入一条边，都需要重新查找边所包含两个顶点信息对应的下标，正常的算法没这么弱智吧，不需要顶点信息即为顶点的下标，用散列等方法可以不用这样的