c++ - 尝试为每个节点创建一个具有连接节点的数组失败

Question

除了应该记住每个节点的连接节点的数组之外，一切都很好，尽管它只计算了其中的一些，我不知道为什么。我相信问题出在这里：

if (G->v[j] != NULL || G->v[i] != NULL)

但是，我不确定如何更改它。

#include <iostream>
#include <time.h>
#include <list>
#include <iterator>
#include <stack>
#include <queue>
#include "Profiler.h"
using namespace std;

# define MAX_SIZE 20

class Node
{
public:
    int key;
    int colour; // -1 not visited(white), 0 under visit(gray), 1 visited(black)
    Node* p;
    int d, f;
    list<Node*> adj;
};

Node* newNode(int key)  //constructor
{
    Node* node = new Node();
    node->key = key;
    node->colour = -1;  // white, not visited
    node->d = 0;
    node->f = 0;
    node->p = NULL;
    return node;
}

class Edge
{
public:
    Node *v1,*v2;
};

Edge* newEdge(Node* u, Node* v)
{
    Edge* edge = new Edge();
    edge->v1 = u;
    edge->v2 = v;
    return edge;
}

class Graph
{
public:
    Node* v[MAX_SIZE];
    list<Edge*> e;
};

Graph* newGraph(int nb_of_vertices, int nb_of_edges)
{
    Graph* G = new Graph();
    int i, j;
    for (i = 0; i < nb_of_vertices; i++)
    {
        G->v[i] = NULL;
    }
    for (i = 0; i < nb_of_vertices; i++)
    {
        Node* v1 = newNode(i);
        G->v[i] = v1;
        do
            j = rand() % (nb_of_vertices-1);
        while (j == i);
        if (G->v[j] != NULL || G->v[i] != NULL)
        {
            Node* v2 = newNode(j);
            G->v[j] = v2;
            G->v[i]->adj.push_back(v2);
            Edge* edge = newEdge(v1, v2);
            G->e.push_back(edge);
        }


    }
    return G;
}

void printGraph(Graph* G, int n)
{
    list <Node*> ::iterator it;
    for (int i = 0; i < n; i++)
    {
        cout << G->v[i]->key << '\t' << G->v[i]->colour << '\t' << G->v[i]->d << '\t' << G->v[i]->f << '\t';// << G->v[i]->p << '\t';
        for (it = G->v[i]->adj.begin(); it != G->v[i]->adj.end(); ++it)
        {
            cout << (*it)->key << ' ';
        }
        cout << '\n';
    }
    list <Edge*> ::iterator it2;
    for (it2 = G->e.begin(); it2 != G->e.end(); ++it2)
    {
        cout << (*it2)->v1->key << "-" << (*it2)->v2->key << ' ';
    }
    cout << '\n';
}

queue <Node*> solution;
stack <Node*> topsort;
int no_cycle = 1;

void DFSvisit(Graph* G, Node* v, int& time)
{
    Node* node = newNode(0);
    time++;
    v->d = time;
    v->colour = 0;
    while (!v->adj.empty())
    {
        node = v->adj.front();
        v->adj.pop_front();
        if (v->colour == 0)
            no_cycle = 0;

        if (node->colour == -1)
        {
            node->p = v;
            DFSvisit(G, node, time);
        }

    }
    v->colour = 1;
    time++;
    v->f = time;
    solution.push(v);
    topsort.push(v);
}

void DFS(Graph* G, int n)
{
    int time = 0, i;
    for (i = 0; i < n; i++)
    {
        if (G->v[i]->colour == -1)
            DFSvisit(G, G->v[i], time);
    }
}

int main()
{
    srand(time(NULL));
    int nb_of_vertices = 10, nb_of_edges = 3;
    Graph* G = newGraph(nb_of_vertices, nb_of_edges);
    printGraph(G, nb_of_vertices);
    DFS(G, nb_of_vertices);
    printGraph(G, nb_of_vertices);

    // DFS traversal
    cout << "\nDFS TRAVERSAL\n";
    while (!solution.empty())
    {
        cout << solution.front()->key << " ";
        solution.pop();
    }
    cout << '\n';

    // Tarjan's algorithm


    // Topological sort
    if (no_cycle)
    {
        cout << "\nTOPOLOGICAL SORTING\n";
        while (!topsort.empty())
        {
            cout << topsort.top()->key << " ";
            topsort.pop();
        }
    }
    else 
        cout << "\nImpossible to perform topological sort, the generated graph contains cycles.\n";

    return 0;
}

标签： c++