189 8069 5689
理解为一个ArcNode型的变量。其实java中任何一个非基本数据类型的变量名就相当于一个指针，只是一般不这么说罢了。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、雅安服务器托管、营销软件、网站建设、广汉网站维护、网站推广。
这个函数用于删除图中一个顶点的，删除顶点时要同时删除所有与该顶点相关联的边。设要删除的顶点为u，它的某个邻接点为v，则要先删除边（u，v）和（v，u）。又假定与v关联的边只有（v，u），则程序在删除（v，u）时，s指向（v，u），t指向s的前驱，这时，t就为空，而s不为空了。
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.addAdj(vertexList);
if (!is) {vertexList.addAdj(vertexList);}
}
/**
* 返回节点个数
* @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(){
ArrayListVertex next = null;
for (int i = 0; i vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayListVertex 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){
ArrayListVertex 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 ArrayListVertex next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//为节点添加邻接点
public void addAdj(Vertex ver){
if(next == null) next = new ArrayListVertex();
next.add(ver);
}
public ArrayListVertex getAdj(){
return next;
}
public void setIndex(int index){
this.index = index;
}
public String toString(){
return "顶点 "+label+",下标："+index+".";
}
}
代码来自：