算法系列 图数据结构探索(无向图搜索)

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第10篇《无向图搜索》,非常赞!希望对大家有帮助,大家会喜欢!

前面系列文章:

归并排序

#算法基础#选择和插入排序

由快速排序到分治思想

算法基础:优先队列

二分查找

二叉树查找

平衡查找树概述

平衡树之红黑树

算法基础9:散列表

随着图数据库,图计算,知识图谱的兴起,图这种数据结构使用逐渐面向大众,更为的广泛的使用我们这个篇章会给大家介绍图的一些数据结构及其对应相关的一些算法,希望大家能够喜欢,并对大家理解知识图谱,图计算有所帮助

本篇从无向图搜索讲起,说起无向图搜索 主要分为两块一块时深度优先,一块是广度优先。其实图搜索可以我在电脑里有一个文件夹,这个文件夹里有很多细分文件夹,而我们要便利每一个文件夹的一个过程。

而深度优先指的是,我先打开最开始的那个文件夹,之后再打开他下面的第一个文件夹,之后再打开这个子文件的子文件夹,循环往复的一个过程 ,直到所有的文件夹里的文件都便利过一遍。同理广度优先是指我先打开这个文件夹里的所有文件,然后再逐个打开他子文件的所有文件的一个循环往复的一个过程。

二话不说上代码吧 哈哈

深度优先搜索代码

public class DepthFirstPaths {
   private boolean[] marked;
   private int[] edgeTo;
   private final int s;

   public DepthFirstPaths(Graph G, int s) {
      marked = new boolean[G.V()];
      edgeTo = new int[G.V()];
      this.s = s;
      dfs(G, s);
   }

   private void dfs(Graph G, int v) {
      marked[v] = true;
      for (int w : G.adj(v)) {
         if (!marked[w]) {
            edgeTo[w] = v;
            dfs(G, w);
         }
      }
   }

   public boolean hasPathTo(int v) {
      return marked[v];
   }

   public Iterable<Integer> pathTo(int v) {
      if (!hasPathTo(v)) {
         return null;
      }
      Stack<Integer> path = new Stack<Integer>();
      for (int x = v; x != s; x = edgeTo[x]) {
         path.push(x);
      }
      path.push(s);
      return path;
   }

   public static void main(String[] args) {
      Graph G = new Graph(new In(args[0]));
      int s = Integer.parseInt(args[1]);
      DepthFirstPaths search = new DepthFirstPaths(G, s);
      for (int v = 0; v < G.V(); v++) {
         StdOut.print(s + " to " + v + ": ");
         if (search.hasPathTo(v)) {
            for (int x : search.pathTo(v)) {
               if (x == s) {
                  StdOut.print(x);
               } else {
                  StdOut.print("-" + x);
               }
            }
         }
         StdOut.println();
      }
   }

广度优先搜索代码

public class BreadthFirstPaths {
   private boolean[] marked;
   private int[] edgeTo;
   private int[] distTo; // Add for Exercise 4.1.13
   private final int s;

   public BreadthFirstPaths(Graph G, int s) {
      marked = new boolean[G.V()];
      edgeTo = new int[G.V()];
      distTo = new int[G.V()]; // Add for Exercise 4.1.13
      this.s = s;
      bfs(G, s);
   }

   private void bfs(Graph G, int s) {
      Queue<Integer> queue = new Queue<Integer>();
      marked[s] = true;
      // Add for Exercise 4.1.13
      for (int v = 0; v < G.V(); v++) {
         distTo[v] = Integer.MAX_VALUE;
      }
      distTo[s] = 0;
      queue.enqueue(s);
      while (!queue.isEmpty()) {
         int v = queue.dequeue();
         for (int w : G.adj(v)) {
            if (!marked[w]) {
               edgeTo[w] = v;
               marked[w] = true;
               distTo[w] = distTo[v] + 1; // Add for Exercise 4.1.13
               queue.enqueue(w);
            }
         }
      }
   }

   public boolean hasPathTo(int v) {
      return marked[v];
   }

   public Iterable<Integer> pathTo(int v) {
      if (!hasPathTo(v)) {
         return null;
      }
      Stack<Integer> path = new Stack<Integer>();
      for (int x = v; x != s; x = edgeTo[x]) {
         path.push(x);
      }
      path.push(s);
      return path;
   }

   /**
    * Exercise 4.1.13
    * 
    * @param v
    * @return
    */
   public int distTo(int v) {
      return distTo[v];
   }

   public static void main(String[] args) {
      Graph G = new Graph(new In(args[0]));
      int s = Integer.parseInt(args[1]);
      BreadthFirstPaths search = new BreadthFirstPaths(G, s);
      for (int v = 0; v < G.V(); v++) {
         StdOut.print(s + " to " + v + ": ");
         if (search.hasPathTo(v)) {
            for (int x : search.pathTo(v)) {
               if (x == s) {
                  StdOut.print(x);
               } else {
                  StdOut.print("-" + x);
               }
            }
         }
         StdOut.println();
      }
   }
}

应用再知识图谱中风控大量的应用了无向图搜索的内容,有兴趣的同学可以自己去找找相关资料。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-07-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java面试通关手册

一份送给Java初学者的指南

我自己总结的Java学习的系统知识点以及面试问题,目前已经开源,会一直完善下去,欢迎建议和指导欢迎Star: https://github.com/Snailc...

1523
来自专栏撸码那些事

【抽象那些事】 命令式抽象

这种坏味是由操作转换为类引起的,表现为类中只定义了一个方法,有时候类名和方法名相同。这种坏味还常常表现为方法操作的数据位于另一个类中。

3668
来自专栏java学习

java成员变量和局部变量

最新通知 ●回复"每日一练"获取以前的题目! ●【新】Android视频更新了!(回复【安卓视频】获取下载链接) ●【新】Ajax知识点视频更新了!(回复【学习...

30912
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题5.6

题目描述 给出一百分制成绩,要求输出成绩等级‘A’、‘B’、‘C’、‘D’、‘E’。 90分以上为A 80-89分为B 70-79分为C 60-69分为D 60...

3185
来自专栏撸码那些事

【抽象那些事】命令式抽象

1373
来自专栏企鹅号快讯

Python从零基础到精通!小白也能学会!

引言 Functional Programming(函数式编程)的概念最早起源于LISP,由约翰·麦卡锡在1958年创立,最早提出了自动垃圾回收的理念,这一理念...

1995
来自专栏spring源码深度学习

java核心技术——Exception和Error的区别

Exception 和 Error 都是继承了 Throwable 类,在 Java 中只有 Throwable 类型的实例才可以被抛出(throw)或者...

1651
来自专栏iOS 开发

iOS 代码使用 C++ 的 zero-cost abstraction 特性

1973
来自专栏Vamei实验室

编程异闻录

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

1062
来自专栏tkokof 的技术,小趣及杂念

Coroutine,你究竟干了什么?

  使用Unity已经有一段时间了,对于Component、GameObject之类的概念也算是有所了解,而脚本方面从一开始就选定了C#,目前来看还是挺明智的:...

501

扫码关注云+社区

领取腾讯云代金券