邻接表中的深度优先或广度算法

Question

我最近开始进行 C++ 编程，我想知道如何实现深度优先或广度算法。我一直在尝试这样做，但我失败得很厉害，所以如果您可以使用提供的示例向我展示，那将非常有帮助。

#include <iostream>
#include <cstdlib>
using namespace std;

struct AdjancancyListNode
{
 int destination;
 struct AdjancancyListNode* next;
};

struct AdjancancyList
{
 struct AdjancancyListNode *head;
 };

class Graph
{
private:
    int V;
    struct AdjancancyList* array;
    void DFSUtil(int v, bool visited[]);

public:
    Graph(int V)
    {
        this->V = V;
        array = new AdjancancyList [V];
        for (int i = 0; i < V; ++i)
            array[i].head = 0;
    }

    /*
     * Adding Edge to Graph
     */
    void addEdge(int s, int destination)
    {
        AdjancancyListNode* newNode = newAdjListNode(destination);
        newNode->next = array[s].head;
        array[s].head = newNode;
        newNode = newAdjListNode(s);
        newNode->next = array[destination].head;
        array[destination].head = newNode;
    }
            /*
     * Creating New Adjacency List Node
     */
    AdjancancyListNode* newAdjListNode(int destination)
    {
        AdjancancyListNode* newNode = new AdjancancyListNode;
        newNode->destination = destination;
        newNode->next = 0;
        return newNode;
    }

    /*
     * Print the graph
     */
    void printGraph()
    {
        int v;
        for (v = 0; v < V; ++v)  /* going through the edges */
        {
            AdjancancyListNode* pCrawl = array[v].head;
            cout<<endl<<" Adjacency list of vertex |"<<v<<"|"<<endl<<" head ";
            while (pCrawl)
            {
                cout<<"-> |"<<pCrawl->destination<<"|";
                pCrawl = pCrawl->next;
            }
            cout<<endl;

        }
    }



 };
 int main()
{
   Graph gh(9); /* declaring the graph with 5 vertexes */
   gh.addEdge(0, 1);/* Adding edges */
   gh.addEdge(0, 3);
   gh.addEdge(1, 2);
   gh.addEdge(1, 3);
gh.addEdge(2, 4);
gh.addEdge(2, 3);
gh.addEdge(4, 5);
gh.addEdge(5, 6);
gh.addEdge(5, 1);
gh.addEdge(3, 9);
 gh.addEdge(8, 7);
 gh.addEdge(7, 0);
     gh.addEdge(9, 1);
     // print the adjacency list representation of the above graph
     gh.printGraph(); /* showing the graph*/


return 0;
}

Answer 1

你可以像这样用向量实现邻接表，比用指针简单多了。查看代码，也更容易理解它是如何工作的。

#include <bits/stdc++.h>

using namespace std;

vector<int> edges[5];
bool visited[5];

void dfs(int x)
{
    visited[x] = true;
    for(int i=0; i < edges[x].size(); i++)
        if(!visited[edges[x][i]])
            dfs(edges[x][i]);
}

int main()
{
    for(int i=0; i < 5; i++)
        visited[i] = false;
    vector<pair<int, int> > inputEdges{{0, 1}, {1, 2}, {0, 3}, {3, 4}, {1, 4}};
    for(int i=0; i < inputEdges.size(); i++)
    {
        edges[inputEdges[i].first].push_back(inputEdges[i].second);
        edges[inputEdges[i].second].push_back(inputEdges[i].first);
    }
    dfs(0);
    return 0;
}

邻接表中的深度优先或广度算法

Depth first or breadth algorithm in adjacency List

c

c++

algorithm

breadth-first-search

depth-first-search