星空网 > 软件开发 > Java

邻接表存储图,DFS遍历图的java代码实现

邻接表存储图,DFS遍历图的java代码实现

import java.util.*;public class Main{ static int MAX_VERTEXNUM = 100; static int [] visited = new int[MAX_VERTEXNUM]; public static void main(String [] args){ Graph G = new Graph(); creatGraph(G); output(G); for(int i=0;i<G.vertex_num;i++) visited[i]=0; System.out.println("DFS遍历的结果是:"); dfs(G,0);//从G.node_list[0]开始DFS遍历 } static void creatGraph(Graph G){ Scanner in = new Scanner(System.in); System.out.println("请输入顶点数v和边数e,(v e):"); G.vertex_num = in.nextInt(); G.edge_num= in.nextInt(); System.out.println("请输入各顶点信息:"); for(int i=0;i<G.vertex_num;i++){ G.node_list[i] = new VertexNode(); G.node_list[i].date = in.next(); G.node_list[i].first_edge = null; //很重要 } System.out.println("请输入各边信息(以空格隔开):"); for(int i=0;i<G.edge_num;i++){ EdgeNode p = new EdgeNode(); String str1 = in.next(); String str2 = in.next(); int v1 = locateVex(G,str1); int v2 = locateVex(G,str2); p.vertex = v1; p.next = G.node_list[v2].first_edge; G.node_list[v2].first_edge = p; EdgeNode q = new EdgeNode();//如果是有向图,则不存在下面的代码(上面的代码的存储顺序可能有变化) q.vertex = v2; q.next = G.node_list[v1].first_edge; G.node_list[v1].first_edge = q; } } static int locateVex(Graph G,String s){ for(int i=0;i<G.vertex_num;i++){ if(G.node_list[i].date.equals(s)) return i; } return -1; } static void output(Graph G){ System.out.println("输出邻接表存储情况:"); EdgeNode p = new EdgeNode(); for(int i=0;i<G.vertex_num;i++){ System.out.print(G.node_list[i].date); p = G.node_list[i].first_edge; while(p!=null){ System.out.print("->"+G.node_list[p.vertex].date); p = p.next; } System.out.println(); } } static void dfs(Graph G,int k){ System.out.println(G.node_list[k].date); visited[k]=1; EdgeNode p = new EdgeNode(); p = G.node_list[k].first_edge; while(p!=null){ if(visited[p.vertex]!=1) dfs(G,p.vertex); p = p.next; } }}//顶点存储class VertexNode{ String date; EdgeNode first_edge = new EdgeNode();}//边存储class EdgeNode{ int vertex; EdgeNode next;}//图存储class Graph{ VertexNode [] node_list = new VertexNode[100]; int vertex_num,edge_num;}

输出结果:注意:(邻接表的保存顺序与输入边的顺序有关)
邻接表存储图,DFS遍历图的java代码实现

 




原标题:邻接表存储图,DFS遍历图的java代码实现

关键词:JAVA

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

网红营销: 一个问题,七大对策!:https://www.ikjzd.com/articles/96448
亚马逊卖家如何管理review?:https://www.ikjzd.com/articles/96453
联邦快递为何敢发错这个件?棱镜门重演?:https://www.ikjzd.com/articles/96454
央行、外管局:鼓励存托凭证业务使用人民币跨境收付:https://www.ikjzd.com/articles/96455
进出口企业留意,6月海关政策新规汇总,条条都重要!:https://www.ikjzd.com/articles/96456
盘点亚马逊的撤裁之路,想不到的变动,来了!:https://www.ikjzd.com/articles/96457
恐怖游轮2002 恐怖游轮2022:https://www.vstour.cn/a/365178.html
时尚电商平台Meesho拟融资3亿美元!:https://www.kjdsnews.com/a/1836524.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流