c++ - 广度优先搜索字符而不是整数c ++

Question

我正在尝试创建一个菜单驱动程序来生成深度优先搜索和广度优先搜索图表。我能够让它对整数起作用，但我需要它对字符或字符串而不是整数做同样的事情。

I keep getting a error zsh:segmentation fault whenever any option is selected.

任何帮助表示赞赏这是下面的代码：

#include "stdc++.h"
using namespace std;


void DFS();
//void minimumPath();
//void invalid();

struct Node
{
    char data;
    struct Node* link;
};
 
struct Node* top;
 
void push(char data)
{
     
    // Create new node temp and allocate memory
    struct Node* temp;
    temp = new Node();
 
    // Check if stack (heap) is full.
    // Then inserting an element would
    // lead to stack overflow
    if (!temp)
    {
        cout << "\nHeap Overflow";
        exit(1);
    }
 
    // Initialize data into temp data field
    temp->data = data;
 
    // Put top pointer reference into temp link
    temp->link = top;
 
    // Make temp as top of Stack
    top = temp;
}
 
// Utility function to check if
// the stack is empty or not
char isEmpty()
{
    return top == NULL;
}
 
// Utility function to return top element in a stack
char peek()
{
     
    // Check for empty stack
    if (!isEmpty())
        return top->data;
    else
        exit(1);
}
 
// Utility function to pop top
// element from the stack
void pop()
{
    struct Node* temp;
 
    // Check for stack underflow
    if (top == NULL)
    {
        cout << "\nStack Underflow" << endl;
        exit(1);
    }
    else
    {
         
        // Top assign into temp
        temp = top;
 
        // Assign second node to top
        top = top->link;
 
        // Destroy connection between
        // first and second
        temp->link = NULL;
 
        // Release memory of top node
        free(temp);
    }
}
 


// This class represents a directed graph using adjacency
// list representation
class Graph
{
int V; // No. of vertices
list<char> *adj; // adjacency lists
public:
Graph(int V); // Constructor
void addEdge(char v, char w); // to add an edge to graph
void DFS(char s); // prints all vertices in DFS manner
// from a given source.
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<char>[V];
}

void Graph::addEdge(char v, char w)
{
adj[v].push_back(w); // Add w to v’s list.
}

// prints all not yet visited vertices reachable from s
void Graph::DFS(char s)
{
// Initially mark all vertices as not visited
vector<bool> visited(V, false);

// // Create a stack for DFS
// stack<int> stack;

// Push the current source node.
push(s);

while (!isEmpty())
{
// Pop a vertex from stack and print it
char s = peek();
pop();

// Stack may contain same vertex twice. So
// we need to print the popped item only
// if it is not visited.
if (!visited[s])
{
cout << s << " ";
visited[s] = true;
}

// Get all adjacent vertices of the popped vertex s
// If a adjacent has not been visited, then push it
// to the stack.
for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
if (!visited[*i])
push(*i);


    }
   
}


void addEdgee(vector<char> adj[], char src, char dest)
{
    adj[src].push_back(dest);
    adj[dest].push_back(src);
}
 
// a modified version of BFS that stores predecessor
// of each vertex in array p
// and its distance from source in array d
bool BFS(vector<char> adj[], char src, char dest, int v,
         char pred[], char dist[])
{
    // a queue to maintain queue of vertices whose
    // adjacency list is to be scanned as per normal
    // DFS algorithm
    list<char> queue;
 
    // boolean array visited[] which stores the
    // information whether ith vertex is reached
    // at least once in the Breadth first search
    bool visited[v];
 
    // initially all vertices are unvisited
    // so v[i] for all i is false
    // and as no path is yet constructed
    // dist[i] for all i set to infinity
    for (int i = 0; i < v; i++) {
        visited[i] = false;
        dist[i] = INT_MAX;
        pred[i] = -1;
    }
 
    // now source is first to be visited and
    // distance from source to itself should be 0
    visited[src] = true;
    dist[src] = 0;
    queue.push_back(src);
 
    // standard BFS algorithm
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop_front();
        for (int i = 0; i < adj[u].size(); i++) {
            if (visited[adj[u][i]] == false) {
                visited[adj[u][i]] = true;
                dist[adj[u][i]] = dist[u] + 1;
                pred[adj[u][i]] = u;
                queue.push_back(adj[u][i]);
 
                // We stop BFS when we find
                // destination.
                if (adj[u][i] == dest)
                    return true;
            }
        }
    }
 
    return false;
}
 
// utility function to print the shortest distance
// between source vertex and destination vertex
void minimumPath(vector<char> adj[], char s,
                           char dest, int v)
{
    // predecessor[i] array stores predecessor of
    // i and distance array stores distance of i
    // from s
    char pred[v], dist[v];
 
    if (BFS(adj, s, dest, v, pred, dist) == false) {
        cout << "Given source and destination"
             << " are not connected";
        return;
    }
 
    // vector path stores the shortest path
    vector<char> path;
    char crawl = dest;
    path.push_back(crawl);
    while (pred[crawl] != -1) {
        path.push_back(pred[crawl]);
        crawl = pred[crawl];
    }
 
    // printing path from source to destination
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << " ";
}


// Main definition  
int main()
{
    int choice;
    while (1) {

        cout << "\t\t\t\t\t      M E N U \n";
        cout << "Depth-First Search (0), Minimum Path Search (1)\n";
        cout << "Exit Program (3) \n";
        cout << "\t\t\t\t\t Choose? ";
        cin >> choice;

        if (choice == 0) {
            Graph g(9);
            g.addEdge('A', 'B');
            g.addEdge('A', 'C');
            g.addEdge('A', 'D');
            g.addEdge('B', 'B');
            g.addEdge('C', 'G');
            g.addEdge('D', 'C');
            g.addEdge('D', 'G');
            g.addEdge('E', 'C');
            g.addEdge('E', 'F');
            g.addEdge('F', 'C');
            g.addEdge('F', 'H');
            g.addEdge('G', 'F');
            g.addEdge('G', 'H');
            g.addEdge('G', 'I');
            g.addEdge('H', 'E');
            g.addEdge('H', 'I');
            g.addEdge('I', 'F');
            char data;
            cin >> data;
            g.DFS(data);
        }
        else if (choice == 1) {
            int v = 9;
            vector<char> adj[v];
           
            addEdgee(adj,'A', 'B');
            addEdgee(adj,'A', 'C');
            addEdgee(adj,'A', 'D');
            addEdgee(adj,'B', 'B');
            addEdgee(adj,'C', 'G');
            addEdgee(adj,'D', 'C');
            addEdgee(adj,'D', 'G');
            addEdgee(adj,'E', 'C');
            addEdgee(adj,'E', 'F');
            addEdgee(adj,'F', 'C');
            addEdgee(adj,'F', 'H');
            addEdgee(adj,'G', 'F');
            addEdgee(adj,'G', 'H');
            addEdgee(adj,'G', 'I');
            addEdgee(adj,'H', 'E');
            addEdgee(adj,'H', 'I');
            addEdgee(adj,'I', 'F');
           
            char K,L;
            cin >> K >> L;
            minimumPath(adj, K, L, v);
        }

        else if (choice == 3) {
            exit(0);
        }
       
    }
    return 0;
}

标签： c++stringstackdepth-first-searchbreadth-first-search