说明一下:下边的例子就是<Java数据结构和算法>书的一个例子,并非我所写的,这一本书我觉得是最好 的一本java数据结构的入门书籍.现在把这一个例子记录在blog上,当作温习一下啦。
无向图的广度搜索的规则有如下:
规则1、访问下一个未来访问的邻接点(如果存在),这个顶点必须是当前顶点的邻接点,标点它,并把它插入到队列中。
规则2、如果因为已经没有未访顶点而不能执行规则1,那么从队列取一个顶点(如果存在),并使其成为当前的顶点。
规则3、如果因为队列为空而不能执行规则2,则搜索结束。
下面是实例的代码:
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
/*Graph类的bfs()方法和dfs()方法类似的,只是用队列代替了栈,嵌套的循环代替了单层 *循环。外层循环等待队列为空,而内层循环依次寻找当前顶点的未访问邻接点。
**/
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; // mark 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; // mark 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
分享到:
相关推荐
无向图的课设,有程序和报告,内容有邻接矩阵建立无向图、邻接矩阵遍历、广度优先搜索遍历、深度优先搜索遍历、(最小生成树普里姆(Prim)算法)、单源最短路径(地杰斯特拉(Dijkstra)算法),程序打开即可运行。
对于有向图和无向图,BFS的执行方式基本相同,区别在于邻接节点的定义。在无向图中,两个节点之间有一条边,那么它们相互为邻接节点。而在有向图中,只有当存在一条从节点A到节点B的边,节点B才是节点A的邻接节点。 ...
最后,**最小生成树(MST)** 是一个无向图中边的子集,它包含了图中的所有节点,并且任何两个节点之间都有路径相连,同时这个子集的总权重是最小的。求解MST是图论中的经典问题,常见算法包括Prim的贪心算法和...
在有向图中,每个边都有明确的方向,从一个节点指向另一个节点。 3. **DAG类(DAG Class)**:DAG类管理所有节点和边,提供添加、删除节点和边的方法。它还可能包含用于执行特定操作,如拓扑排序和最短路径计算的...
在ACM程序设计竞赛中,广度优先搜索(Breadth-First Search,简称BFS)是一种常用的图遍历算法,常用于解决许多问题,如最短路径、判断连通性等。本压缩包文件“BFS”包含了作者在参与ACM竞赛时总结的一些BFS实例...
在寻找最小生成树时,可以使用BFS来解决如Prim算法的简化版本,尤其是在加权无向图中。 总结,广度优先搜索是一种重要的图论算法,广泛应用于寻找最短路径、遍历结构等问题。通过上述五个实例,我们可以更好地理解...
- **拓扑排序**:在有向无环图(DAG)中,BFS可以进行拓扑排序,确定节点的先后顺序。 - **判断连通性**:通过BFS遍历所有节点,可判断图是否连通。 在实际编程中,BFS的实现需要特别注意空间效率,因为可能会有大量...
DFS在有向图和无向图中都能使用,但不保证找到最短路径。在某些问题,如判断图是否连通、查找有向图中的环等,DFS是非常有效的。 在提供的文件列表中,我们可以看到`Graph.cpp`, `Node.cpp`, `Path.cpp`, 和 `Main....
- **拓扑排序**:在无环有向图中,BFS可以用于执行拓扑排序。 - **层次遍历**:在树结构中,BFS可以按层级顺序访问所有节点,例如在二叉树中进行层次遍历。 5. **Java实现**: 在Java中,我们可以使用`java.util...
2. `main.cpp`: 这是程序的主入口,可能会创建一个无向图实例,调用`func.cpp`中的函数进行图的操作,并打印结果或者进行其他处理。 3. `UD_Graph_Structure.h`: 这是一个头文件,很可能定义了无向图的数据结构,...
- **有向图与无向图**:如果图中的每条边都具有明确的方向,则该图称为有向图;反之,若图中边无方向,则称为无向图。 - **简单图与多重图**:简单图要求任意两条边的起点和终点不能完全相同,并且每条边必须连接...
定义了一个函数`creatgraph`用于创建一个无向图实例,并初始化顶点和边。用户需要输入边的信息来构建图。 ```c void creatgraph(Graph *g, int n) { // 初始化顶点 for (int i = 1; i ; i++) { g->V[i] = i; } ...
通常,BFS的学习案例会包括经典问题,如寻找二叉树的层次遍历、社交网络中的朋友查找、有向图或无向图的最短路径等。 【标签】"源码 工具"表明这篇内容可能会包含实际的Java代码实现,并可能提供了一些实用工具或...
3. 测试用例,用于验证算法的正确性,可能包括有向图、无向图、有向网(带权有向图)和无向网(带权无向图)的实例。 4. 可能还包含输入输出处理,用于读取图的结构信息并打印搜索结果。 在实际应用中,DFS和BFS各...
示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1...
在迷宫问题中,我们把迷宫看作一个有向图,每个可通行的单元格是一个节点,相邻的可通行单元格之间有边相连。 BFS算法的步骤如下: 1. 将起点放入一个队列。 2. 创建一个集合(或者用一个二维数组)来跟踪已经访问...
此外,对于有向图中的强连通分量和拓扑排序等问题,BFS也有其独特的优势。 学习BFS时,建议结合实际问题进行练习,例如构建自己的图数据结构,实现BFS算法并进行调试,这样可以更深入地理解和掌握这种算法。同时,...
在一个加权无向图中,最小生成树是一棵树形子图,包含了原图的所有顶点,且所有边的权重之和是最小的。常见的算法有Prim算法和Kruskal算法,它们分别通过贪心策略和并查集数据结构寻找最小生成树。 **广度优先搜索...
根据边是否有方向,图可以分为无向图和有向图。无向图中的边没有方向,而有向图中的边具有明确的方向。例如,无向完全图中任意两个顶点之间都有边相连,而有向完全图则包含方向相反的两条边。 图的术语包括度...