1.node的定义类
package Graph;
public class Node {
int data;
Node next;
Node(int data){ //初始化结点
this.data=data;
this.next=null;
}
}
2.图的构建和遍历
package Graph;
public class Graph {
private Node[]head; //存放每个结点的数据
int []visited; //表示每个结点的访问状态
private int Max_size=100; //初始化的队列的大小
int front=-1,rear=-1;
int queue[]=new int[Max_size];
public Graph(int n){ //构造函数,用来初始化head和visited
head=new Node[n];
visited=new int[n];
}
public void cerateGraph(int node[][],int num){
Node newnode=null;
Node ptr=null;
int start,end;
for(int j=1;j<=8;j++){
head[j]=new Node(j);
visited[j]=0;
}
for(int i=0;i<num;i++){
start=node[i][0]; //记录每条边的起点
end=node[i][1]; //记录边的终点
newnode=new Node(end);
ptr=head[start];
while(ptr.next!=null)
ptr=ptr.next; //找到以每个结点为起点的链表的最后一个结点
//将以start为起点的边插入到对应的head【start】尾部
ptr.next=newnode;
}
}
public void print(){ //打印图的邻接表 的表示
for(int i=1;i<=8;i++){
System.out.print(head[i].data);
Node ptr=head[i].next; //一定要用一个临时变量来操作,否则邻接表的值会被改变
while(ptr!=null){
System.out.print("-->"+ptr.data);
ptr=ptr.next;
}
System.out.println();
}
}
public void DFS(int current){ //深度优先
Node ptr;
visited[current]=1; //表示已经被访问
System.out.print(head[current].data+" ");
ptr=head[current].next;
while(ptr!=null){
if(visited[ptr.data]==0)
DFS(ptr.data); //递归实际上就是利用栈
ptr=ptr.next;
}
}
public void enqueue(int data){
rear++;
queue[rear]=data;
}
public int dequeue(){
front++;
return queue[front];
}
public void BFS(int current){
Node ptr;
for(int j=1;j<=8;j++){ //此处需要初始化,因为visited的状态已经被DFS改变
visited[j]=0;
}
enqueue(current); //将起点压入栈
visited[current]=1; //改变访问状态
System.out.print(current+" "); //输出这个结点
while(front!=rear){ //队列不为空时
current=dequeue();
ptr=head[current].next; //起点的下一个结点
while(ptr!=null){
if(visited[ptr.data]==0){ //如果没有被访问过,
enqueue(ptr.data); //进队列
visited[ptr.data]=1; //改变访问状态
System.out.print(ptr.data+" "); //输出这个结点
}
ptr=ptr.next; //访问下一个结点
}
}
}
}
3.测试类
package Graph;
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
System.out.print("input the count of the virtex: ");
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
System.out.print("input the count of the edge: ");
int E=sc.nextInt();
System.out.println("input the information of edge: ");
int node[][]=new int[E][2];
for(int i=0;i<E;i++){
System.out.print("第"+(i+1)+" 边的起点和终点 :");
node[i][0]=sc.nextInt();
node[i][1]=sc.nextInt();
}
/*int node[][]={{1,2},{2,1},
{1,3},{3,1},
{2,4},{4,2},
{2,5},{5,2},
{3,6},{6,3},
{3,7},{7,3},
{4,8},{8,4},
{5,8},{8,5},
{6,8},{8,6},
{7,8},{8,7}
};*/
Graph g=new Graph(N+1); //N+1主要是为了表示的时候方便
g.cerateGraph(node, E);
System.out.println("邻接表表示的结果是:");
g.print();
System.out.print("\n深度优先遍历的结果是:");
g.DFS(1);
System.out.print("\n广度优先遍历的结果是:");
Graph gp=new Graph(N+1); //之所以要重新创建一个对象是因为DFS已经把visited的状态更新为自己的
gp.cerateGraph(node, E);
gp.BFS(1);
}
}
分享到:
相关推荐
java 实现图数据结构以及深度优先和广度优先算法
Java实现深度优先、广度优先的网页爬虫
图的深度优先遍历和广度优先遍历-Java实现
无向图的连接表存储结构的创建...从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的算法 对具有G.vexnum个顶点的图的广度优先遍历的算法
NULL 博文链接:https://redhacker.iteye.com/blog/413606
图的深度优先和广度优先遍历,下载下来可直接运行。你值得拥有
使用Java实现图的深度优先和广度优先遍历算法
NULL 博文链接:https://128kj.iteye.com/blog/1663164
直接演示:求深度优先遍历、广度优先遍历、最短路径、最小生成树
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
主要介绍了深度优先与广度优先Java实现代码示例,具有一定借鉴价值,需要的朋友可以参考下。
用Java描述的图,以邻接表存储,包含常用算法
本程序通过java使用邻接表对图进行深度和广度优先遍历,其中包括图和节点的数据结构实现
主要介绍了Java编程实现基于图的深度优先搜索和广度优先搜索完整代码,具有一定借鉴价值,需要的朋友可以了解下。
主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
对一个完全图,(稍加修改即可对非完全图适用),经过每个节点有且仅有...其中采用了深度优先的函数,广度优先的实现在注释中给予了实现。最后测试了五个节点的图,大家可以看看到底多少个节点之后计算机运行明显变慢。
分别采用广度优先遍历和深度优先遍历实现八皇后的求解问题。源代码(.java)文件
设计和实现了图的广度优先搜索和深度优先搜索,使用的编程语言是java
图的几种常用算法(广度/深度优先搜索,最小生成树,弗洛伊德,拓扑排序....邻接矩阵),java实现。 注释清晰,代码简单易懂。