图的深度优先遍历

首页 » 算法 » 图的深度优先遍历

从初始访问节点出发,初始节点可能有多个邻接节点,深度优先遍历的策略就是首先访问第一个邻接节点,
然后再以这个被访问的邻接节点作为初始节点,访问它的第一个邻接节点

  1. 访问初始节点v,并标记节点v为已访问
  2. 查找节点v的第一个邻接节点w
  3. 若w存在,则继续执行4,如果w不存在(不连接),则回到第1步,将从v的下一个节点继续遍历
  4. 若w未被访问,对w进行深度优先遍历(即把w当作另一个v,然后进行步骤123)
  5. 查找节点v的w邻接节点的下一个邻接节点,转到步骤3

 

图的深度优先遍历
图的深度优先遍历
矩阵形式
//得到第一个邻接节点的下标w
/**
 * 
 * @param index
 * @return 如果存在就返回对应的下标,否则返回-1
 */
public int getfirst(int index) {
 for(int j=0;j<ddlist.size();j++) {
  if(ljjz[index][j]>0) {
   return j;
  }
 }
 return -1;
}
//根据前一个邻接节点的下标来获取下一个邻接节点
public int getnext(int v1,int v2) {
 for(int j=v2+1;j<ddlist.size();j++) {
  if(ljjz[v1][j]>0){//说明存在
   return j;
  }
 }
 return -1;
}
//深度优先遍历
//i第一次就是0
public void dfs(boolean[] isvisited,int i) {
 //首先访问该节点并输出
 System.out.print(getvelau(i)+"->");
 //将节点设置成已经访问
 isvisited[i]=true;
 //查找节点i的第一个邻接节点w
 int w=getfirst(i);
 while(w != -1) {
  if(!isvisited[w]) {
   dfs(isvisited,w);
  }
  //如果w节点已经被访问过
  w=getnext(i, w);
 }
}
//对dfs进行重载,遍历所有的节点,并进行dfs
public void dfs() {
 //遍历所有的节点,进行dfs(回朔)
 for(int i=0;i<getdnum();i++) {
  if(!isvisited[i]) {
   dfs(isvisited,i);
  }
 }
}

图创建和遍历

package 图;

import java.util.ArrayList;
import java.util.Arrays;

public class 图创建{
 private ArrayList<String> ddlist;//存储顶点集合
 private int[][] ljjz;//存储对应的邻接矩阵
 private int b;//边的数目
 //定义数组,记录某个节点是否被访问过
 private boolean[] isvisited;
 public 图创建(int n) {
  ljjz=new int[n][n];
  ddlist=new ArrayList<String>(n);
  b=0;
  isvisited = new boolean[5];
 }
 
public static void main(String[] args) {
 int n=5;//节点的个数
 String vv[]= {"a","b","c","d","e"};
 //创建图对象
 图创建 graph = new 图创建(n);
 //循环的添加顶点
 for (String v: vv) {
  graph.insertd(v);
 }
 //添加边
 //a-b a-c b-c b-d b-e
 graph.insertb(0, 1, 1);
 graph.insertb(0, 2, 1);
 graph.insertb(1, 2, 1);
 graph.insertb(1, 3, 1);
 graph.insertb(1, 4, 1);
 graph.show();
 graph.dfs();
}
//得到第一个邻接节点的下标w
/**
 * 
 * @param index
 * @return 如果存在就返回对应的下标,否则返回-1
 */
public int getfirst(int index) {
 for(int j=0;j<ddlist.size();j++) {
  if(ljjz[index][j]>0) {
   return j;
  }
 }
 return -1;
}
//根据前一个邻接节点的下标来获取下一个邻接节点
public int getnext(int v1,int v2) {
 for(int j=v2+1;j<ddlist.size();j++) {
  if(ljjz[v1][j]>0){//说明存在
   return j;
  }
 }
 return -1;
}
//深度优先遍历
//i第一次就是0
public void dfs(boolean[] isvisited,int i) {
 //首先访问该节点并输出
 System.out.print(getvelau(i)+"->");
 //将节点设置成已经访问
 isvisited[i]=true;
 //查找节点i的第一个邻接节点w
 int w=getfirst(i);
 while(w != -1) {
  if(!isvisited[w]) {
   dfs(isvisited,w);
  }
  //如果w节点已经被访问过
  w=getnext(i, w);
 }
}
//对dfs进行重载,遍历所有的节点,并进行dfs
public void dfs() {
 //遍历所有的节点,进行dfs(回朔)
 for(int i=0;i<getdnum();i++) {
  if(!isvisited[i]) {
   dfs(isvisited,i);
  }
 }
}
//显示图对应的矩阵
public void show() {
 for(int[] link:ljjz) {
  System.out.println(Arrays.toString(link));
 }
}
//返回节点的个数
public int getdnum() {
 return ddlist.size();
}
//得到边的数目
public int getbnum() {
 return b;
}
//返回节点i(下标)对应的数据 0->"a" 2->"c"
public String getvelau(int i) {
 return ddlist.get(i);
}
//返回v1和v2的权值
public int getweight(int v1,int v2) {
 return ljjz[v1][v2];
}
//插入节点
public void insertd(String ver) {
 ddlist.add(ver);
}
//添加边
/**
 * 
 * @param v1 表示第一个顶点的下标即第几个顶点 "a"-"b" "a"->0 "b"->1
 * @param v2 表示第二个顶点对应的下标
 * @param wetght 权值(边对应的值【0/1】)
 */
public void insertb(int v1,int v2,int weight) {
 ljjz[v1][v2]=weight;
 ljjz[v2][v1]=weight;
 b++;
}
}

 

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

 



觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00