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 = 0i <vertexList.lengthi++) {
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 = 0i <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 = 0i <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 = 0i <getVertsCount()i++) {
vertexList[i].isVisted = false
}
}
/**
* 得到一个邻接点
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayList<Vertex>adjVertexs = vertex.getAdj()
for (int i = 0i <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 = 0i <nVertsi++) {
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
如何使邻接表的结构定义更加清晰。(java版)用邻接表实现无向图的创建出现的问题是关于内部类的使用，如何使邻接表的结构定义更加清晰，不分散。
在邻接表中，对图中每个顶点V建立一个单链表，把与V相邻接的顶点放在这个链表中。
