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)的意思是每次插入一條邊，都需要重新查找邊所包含兩個頂點信息對應的下標，正常的演算法沒這么弱智吧，不需要頂點信息即為頂點的下標，用散列等方法可以不用這樣的