好像又是接近半个月没有更新，这半个月忙着结婚的各项事情，本来预计的学习任务也拖拖拉拉，进度缓慢。吐槽一句，拍婚纱照真的是最非常非常累的一件事情，不想再有下次了。
好吧，言归正传，今天就在这周缓慢的学习进度中，抽取出来一个比较有代表性的知识点，记录一下吧。
首先，首次接触图这个类型的数据结构，我们先来看一下图的定义，了解一下到底什么是图。
图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为: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(" -> ");
}
}
}
}
今天的无权图的路径问题就讲解到这里，之后的知识点等学习整理之后，再行记录。