我有一个矩形格式的字母无向图，其中每个节点都有一条到相邻相邻节点的边。例如:
d x f p
o y a a
z t i b
l z t z
在这个图节点"d"与[x, y, o]相邻。我想检查节点的序列是否。存在于图中，其中每个后续节点与下一个相邻。它的主要应用是一个单词搜索游戏，只有字母相邻的单词才算数。例如，序列"zap"不算数，因为节点不是相邻的。我不需要检查序列是否为实字，只需要检查它在图中是否相邻。我的图表如下:
// graph.h
#include <queue>
#include "SLList.h"
#include "DynArray.h"
template<typename Type>
class Graph {
public:
struct Edge {
unsigned int toVertex; // index to vertex the edge connects to
};
struct Vertex {
// the data that this vertex is storing
Type element;
// the list of edges that connect this vertex to another vertex
SLList<Edge> edges;
///////////////////////////////////////////////////////////////////////////
// Function : addEdge
// Parameters : toVertex - the index of the vertex we are adjacent to
///////////////////////////////////////////////////////////////////////////
void addEdge(const unsigned int& toVertex) {
Edge e;
e.toVertex = toVertex;
edges.addHead(e);
}
};
private:
// dynarray of vertices
DynArray<Vertex> vertices;
// helper function to check if a vertex is a in a queue
bool IsInQueue(DynArray<Edge> arrayOfEdges, unsigned int _toVertex) {
for (unsigned int i = 0; i < arrayOfEdges.size(); ++i) {
if (arrayOfEdges[i].toVertex == _toVertex)
return true;
}
return false;
}
public:
/////////////////////////////////////////////////////////////////////////////
// Function : addVertex
// Parameters : value - the data to store in this vertex
// Return : unsigned int - the index this vertex was added at
/////////////////////////////////////////////////////////////////////////////
unsigned int addVertex(const Type& value) {
Vertex v;
v.element = value;
vertices.append(v);
return vertices.size();
}
/////////////////////////////////////////////////////////////////////////////
// Function : operator[]
// Parameters : index - the index in the graph to access
// Return : Vertex& - the vertex stored at the specified index
/////////////////////////////////////////////////////////////////////////////
Vertex& operator[](const unsigned int& index) {
return vertices[index];
}
/////////////////////////////////////////////////////////////////////////////
// Function : size
// Return : unsiged int - the number of vertices in the graph
/////////////////////////////////////////////////////////////////////////////
unsigned int size() const {
return vertices.size();
}
/////////////////////////////////////////////////////////////////////////////
// Function : clear
// Notes : clears the graph and readies it for re-use
/////////////////////////////////////////////////////////////////////////////
void clear() {
// for each node, remove all its edges
// then remove the node from the array
for (unsigned int i = 0; i < vertices.size(); ++i) {
vertices[i].edges.clear();
}
vertices.clear();
}
};
So far I try:
my algorithm:
finding the starting node
setting a current node to this start node
searching all edges of the current node for the next node in sequence without visiting nodes that have been visited
if next node in sequence is found then current is set to next and next is incremented
if current == end and next == null then return true
else false
然而，这并不是每次都有效。例如，它适用于"dot"，但不适用"pay"在上图中。这是因为一旦它访问第二个"它标记为已访问，无法找到"y"了。我相信这个算法还有其他问题。我在这里搜索了其他答案，但它们只解释了如何找到从开始节点到结束节点的路径，其中路径无关紧要。在这种情况下，路径才是关键。
在c++中使用my graph.h解决方案。
下面是一个简单的基于深度优先搜索的过程，它试图查找在字符网格中创建指定字符串的路径。这个DFS是一个基本的蛮力算法的例子，因为它只是尝试所有可能正确的路径。在下面的程序中，我使用我自己的Graph类(抱歉)，但它应该足够简单，易于理解。下面是我的c++代码:
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
struct Graph{
int rows, cols;
vector <vector<char>> grid;
// DFS: Recursively tries all possible paths - SEE THE BELOW FUNCTION FIRST
void dfs(int r, int c, size_t len, string &str, bool &done, auto &vis, auto &path){
// if (len == str.size()), that means that we've found a path that
// corresponds to the whole string, meaning that we are done.
if(len == str.size()){
done = true;
return;
}
// Check all nodes surrounding the node at row r and column c
for(int next_r = r-1; next_r <= r+1; ++next_r){
for(int next_c = c-1; next_c <= c+1; ++next_c){
// Bounds check on next_r and next_c
if(next_r < 0 || next_r >= rows){continue;}
else if(next_c < 0 || next_c >= cols){continue;}
// KEY: We don't visit nodes that we have visited before!
if(vis[next_r][next_c]){
continue;
}
// ONLY if grid[next_r][next_c] happens to be the next character in str
// that we are looking for, recurse.
if(grid[next_r][next_c] == str[len]){
vis[next_r][next_c] = true;
path.push_back({next_r, next_c});
dfs(next_r, next_c, len + 1, str, done, vis, path);
// If done is true, that means we must've set it to true in
// the previous function call, which means we have found
// a valid path. This means we should keep return-ing.
if(done){return;}
vis[next_r][next_c] = false;
path.pop_back();
}
}
if(done){return;} // see the above comment
}
}
// Returns a vector <pair<int, int>> detailing the path, if any, in the grid
// that would produce str.
vector <pair<int, int>> get_path_of(string &str){
bool done = false;
vector <pair<int, int>> path;
// Try starting a DFS from every possible starting point until we find a valid
// path
for(int r = 0; r < rows; ++r){
for(int c = 0; c < cols; ++c){
vector <vector<bool>> vis(rows, vector <bool> (cols, false));
dfs(r, c, 0, str, done, vis, path);
// Found a path during the above function call! We can return now
if(done){
return path;
}
}
}
return {};
}
Graph(int r, int c){
rows = r;
cols = c;
grid = vector <vector<char>> (r, vector <char> (c));
}
};
int main()
{
// Input in the number of rows and columns in the grid
int R, C;
cin >> R >> C;
Graph G(R, C);
// Input the letters of the grid to G
for(int i = 0; i < R; ++i){
for(int j = 0; j < C; ++j){
cin >> G.grid[i][j];
}
}
// Input the strings to find in G
string str;
while(cin >> str){
vector <pair<int, int>> path = G.get_path_of(str);
cout << "PATH OF " << str << ": ";
for(const pair <int, int> &item : path){
cout << "{" << item.first << ", " << item.second << "} ";
}
cout << "n";
}
return 0;
}
如果你有任何问题，请不要犹豫，问我!