数据结构——无权图的路径问题(C++和java实现)

好像又是接近半个月没有更新,这半个月忙着结婚的各项事情,本来预计的学习任务也拖拖拉拉,进度缓慢。吐槽一句,拍婚纱照真的是最非常非常累的一件事情,不想再有下次了。

好吧,言归正传,今天就在这周缓慢的学习进度中,抽取出来一个比较有代表性的知识点,记录一下吧。

首先,首次接触图这个类型的数据结构,我们先来看一下图的定义,了解一下到底什么是图。

图是由顶点的有穷非空集合和顶点之间的边的集合组成,通常表示为:G(V,E), 其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

接下来我们把图的定义与线性表定义的进行一下对比,让我们来更好的体会一下图的各种定义与其他数据结构的差异:

  • 线性表中,我们把数据元素叫做元素,树种将数据元素叫结点,在图中的数据元素,我们则称之为顶点。
  • 线性表中没有数据元素,称为空表。树种可以没有结点,叫做空树。但是在图结构中,不允许没有顶点。在定义中,若V是顶点的集合,则强调了顶点集合V是有穷非空的。
  • 线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

图的定义我们就暂时讲到这里,更细致的定义希望大家自己在网络或者书籍中获取资料,毕竟我写的再多,也不如教科书详尽,今天我们就来讲一个图的应用,关于路径查找的问题。在这里我想先说明,我们的路径查找是一种针对无向图的路径查找,比如给出起始点A,查询顶点A至顶点B是否有路径,若是有路径,则打印出A至B的路径。而这个路径,我们寻找的不一定是最短路径。

其实分析这个问题就可以知道,这是对图的深度优先遍历(Depth-First-Search 简称DFS)的一个应用,若是我们能实现了图的深度优先遍历,那么查找路径的问题也就迎刃而解。

接下来就先给出C++的代码,来展示解决查询路径问题的思路:

#include <iostream>
#include <vector>
#include <stack>
#include <cassert>

using namespace std;

// 路径查询
template<typename Graph>
class Path {

private:
    Graph &G; // 图的引用
    int s;    // 起始点
    bool* visited; // 记录dfs的过程中节点是否被访问
    int* from; // 记录路径,from[i]表示查找的路径上i的上一个节点

    // 图的深度优先遍历
    void dfs( int v ) {
        visited[v] = true;

        typename Graph::adjIterator adj(G, v);
        for (int i = adj.begin(); !adj.end(); i = adj.next()) {
            if (!visited[i]) {
                from[i] = v;
                dfs(i);
            }
        }
    } 

public:
    // 构造函数、寻路算法、寻找图graph从s点到其他点的路径
    Path(Graph &graph, int s): G(graph) {

        // 算法初始化
        assert( s >= 0 && s < G.V() );

        visited = new bool[G.V()];
        from = new int[G.V()];

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
        }

        this->s = s;

        // 寻路算法
        dfs(s);
    }

    // 析构函数
    ~Path() {
        delete[] visited;
        delete[] from;
    }

    // 查询从s点到w点是否有路径
    bool hasPath( int w ) {
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查询s点到w点的路径,存放在vec中
    void path( int w, vector<int> &vec ) {
        assert( hasPath(w) );

        stack<int> stack;
        // 通过from数组逆向查找到从s到w的路径,存放在栈中
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素,获得顺序从s到w的路径
        vec.clear();
        while ( !stack.empty() ) {
            vec.push_back( stack.top() );
            stack.pop();
        }
    }

    // 打印从s点到w点的路径
    void showPath( int w ) { 
        assert( hasPath(w) );

        vector<int> vec;
        path(w, vec);
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i];
            if (i == vec.size() - 1)
                cout << endl;
            else
                cout << " -> ";
        }
    }
};

� 通过上面的代码可以得知,我们首先在构造函数中传入我们的图数据结构graph,以及�我们标记的起始点S。而通过showPath()函数我们能够展示起始点S至任意点的路径,测试代码就如下所示:

int main() {
    string filename = "testG2.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();
    cout << endl;

    // 比较使用深度优先遍历和广度优先遍历获得路径的不同
    // 广度优先遍历获得的是无权图的最短路径
    Path<SparseGraph> dfs(g, 0);
    cout << "DFS : " << endl;
    dfs.showPath(6);

    ShortestPath<SparseGraph> bfs(g, 0);
    cout << "BFS : ";
    bfs.showPath(6);    
    
    return 0;
}

而Java版本的代码也是类似,只是某些函数的返回值变化了一点,代码如下:

public class Path {

    private Graph G;  // 图的引用
    private int s;  // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;  // 记录路径,from[i]表示查找的路径上i的上一个节点

    /**
     * 构造函数,寻路算法,寻找图graph从点s到其他点的路径
     * @param graph graph
     * @param s 寻路起始点s
     */
    public Path(Graph graph, int s) {
        assert s >= 0 && s < graph.V();

        this.G = graph;
        this.s = s;

        visited = new boolean[G.V()];
        from = new int[G.V()];

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
        }

        dfs(s);
    }

    /**
     * 深度优先遍历
     * @param v 从v点开始深度优先遍历
     */
    private void dfs(int v) {
        visited[v] = true;

        for (int i: G.adj(v)) {
            if (!visited[i]) {
                from[i] = v;
                dfs(i);
            }
        }
    }

    // 查询从s点到w点是否存在路径
    public boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // 查询点s到点w的路径,存放在vec中
    public Vector<Integer> path(int w) {
        assert(hasPath(w));

        Stack<Integer> stack = new Stack<Integer>();
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }

        Vector<Integer> vec = new Vector<Integer>();
        while (!stack.isEmpty()) {
            vec.add(stack.pop());
        }

        return vec;
    }

    // 打印出从点s到点w的路径
    public void showPath(int w) {
        assert (hasPath(w));

        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }
}

今天的无权图的路径问题就讲解到这里,之后的知识点等学习整理之后,再行记录。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

​图;代码轻松理解,代理

代理 代理是英文 Proxy 翻译过来的。我们在生活中见到过的代理,大概最常见的就是朋友圈中卖面膜的同学了。 她们从厂家拿货,然后在朋友圈中宣传,然后卖给熟人。...

31950
来自专栏Spark学习技巧

Flink DataStream编程指南

Flink程序是执行分布式集合转换(例如,filtering, mapping, updating state, joining, grouping, defi...

2.1K70
来自专栏ASP.NETCore

.Net Core中使用ref和Span<T>提高程序性能

其实说到ref,很多同学对它已经有所了解,ref是C# 7.0的一个语言特性,它为开发人员提供了返回本地变量引用和值引用的机制。 Span也是建立在ref语法...

22850
来自专栏苦逼的码农

Hash冲突之开放地址法

比如说我的输入是任意一个自然数(0,1,2,3...),而我要求经过一个函数后我的输出的数的范围要在0-9这样一个范围之间。

79820
来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

30960
来自专栏java达人

哈希表

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接...

19970
来自专栏java架构师

金三银四跳槽季,BAT美团滴滴java面试大纲(带答案版)之一:Java基础篇

Java基础篇: 题记:本系列文章,会尽量模拟面试现场对话情景, 用口语而非书面语 ,采用问答形式来展现。另外每一个问题都附上“延伸”,这部分内容是帮助小伙伴们...

29190
来自专栏Linyb极客之路

Java程序性能优化之编程技巧总结

程序的性能受代码质量的直接影响。在本文中,主要介绍一些代码编写的小技巧和惯例,这些技巧有助于在代码级别上提升系统性能。

9120
来自专栏IMWeb前端团队

简洁的javascript编码(一)--变量、函数

本文作者:IMWeb jaychen 原文出处:IMWeb社区 未经同意,禁止转载 ? 一、变量 使用语义化的变量名称 Bad cons...

26190
来自专栏chenjx85的技术专栏

leetcode-137-Single Number II-第二种解法

5.1K120

扫码关注云+社区

领取腾讯云代金券