没学过数据结构,不懂什么叫回溯算法?广度优先?那位好心人麻烦给出示例代码,谢谢。
解决方案 »
- 字符串中怎么截取指定字符的前面的字符和后面的字符
- 在项目中,对于异常是怎么处理的?
- <html:radio>这个属性怎样不选情况下符合要求的插入数据库
- 求文件管理源码
- SQL查询完成但遇到错误,这种情况如何处理?
- 在JAVA中如何实现一个读写锁?
- applet上的按钮能否用双缓冲画出来。我的按钮有点闪。
- 请keiy() 来接分,原贴http://community.csdn.net/Expert/topic/4322/4322260.xml?temp=.3735315
- 我想知道VisualCafe Standard Edition 4.5 的license
- 文件流问题
- java中怎样实现C中的/t功能,java中有“/t”吗?在线等!
- Applet 中的构造方法???
class Queue
{
private final int SIZE = 20;
private int[] queArray;
private int front;
private int rear;
// -------------------------------------------------------------
public Queue() // constructor
{
queArray = new int[SIZE];
front = 0;
rear = -1;
}
// -------------------------------------------------------------
public void insert(int j) // put item at rear of queue
{
if(rear == SIZE-1)
rear = -1;
queArray[++rear] = j;
}
// -------------------------------------------------------------
public int remove() // take item from front of queue
{
int temp = queArray[front++];
if(front == SIZE)
front = 0;
return temp;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return ( rear+1==front || (front+SIZE-1==rear) );
}
// -------------------------------------------------------------
} // end class Queue
////////////////////////////////////////////////////////////////
class Vertex
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
// -------------------------------------------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// -------------------------------------------------------------
} // end class Vertex
////////////////////////////////////////////////////////////////
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private Queue theQueue;
// ------------------------------------------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix to 0
adjMat[j][k] = 0;
theQueue = new Queue();
} // end constructor
// -------------------------------------------------------------
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
// -------------------------------------------------------------
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
// -------------------------------------------------------------
public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // it
displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2; while( !theQueue.isEmpty() ) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
{ // get one,
vertexList[v2].wasVisited = true; // it
displayVertex(v2); // display it
theQueue.insert(v2); // insert it
} // end while
} // end while(queue not empty) // queue is empty, so we're done
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()
// -------------------------------------------------------------
// returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<nVerts; j++)
if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
} // end getAdjUnvisitedVertex()
// -------------------------------------------------------------
} // end class Graph
////////////////////////////////////////////////////////////////
class BFSApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for bfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4 theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE System.out.print("Visits: ");
theGraph.bfs(); // breadth-first search
System.out.println();
} // end main()
} // end class BFSApp
////////////////////////////////////////////////////////////////