1
resposta

Como eu posso fazer para alterar esse codigo em C++ para C?

// C++ program to print all paths from a source to destination.
#include<iostream>
#include <list>
using namespace std;

// A directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices in graph
    list<int> *adj; // Pointer to an array containing adjacency lists

    // A recursive function used by printAllPaths()
    void printAllPathsUtil(int , int , bool [], int [], int &);

public:
    Graph(int V);   // Constructor
    void addEdge(int u, int v);
    void printAllPaths(int s, int d);
};

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

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

// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];

    // Create an array to store paths
    int *path = new int[V];
    int path_index = 0; // Initialize path[] as empty

    // Initialize all vertices as not visited
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print all paths
    printAllPathsUtil(s, d, visited, path, path_index);
}

// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
                              int path[], int &path_index)
{
    // Mark the current node and store it in path[]
    visited[u] = true;
    path[path_index] = u;
    path_index++;

    // If current vertex is same as destination, then print
    // current path[]
    if (u == d)
    {
        for (int i = 0; i<path_index; i++)
            cout << path[i] << " ";
        cout << endl;
    }
    else // If current vertex is not destination
    {
        // Recur for all the vertices adjacent to current vertex
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                printAllPathsUtil(*i, d, visited, path, path_index);
    }

    // Remove current vertex from path[] and mark it as unvisited
    path_index--;
    visited[u] = false;
}

// Driver program
int main()
{
    // Create a graph given in the above diagram
    Graph g(8);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 6);
    g.addEdge(5, 6);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(5, 7);
    g.addEdge(4, 7);

    int s = 1, d = 6;
    cout << "Following are all different paths from " << s
         << " to " << d << endl;
    g.printAllPaths(s, d);

    return 0;
}
1 resposta

Falta fazer a desalocação de memória.

#define false 0
#define true 1
#define bool int
#include <stdlib.h>
#include <stdio.h>

typedef struct node {
    int val;
    struct node *next;
} node_t;

void push(node_t **head, int val) {
    node_t *new_node;
    new_node = (node_t *) malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}

int V = 0;
node_t **adj = NULL;

void initGraph() {
    adj = (node_t **) malloc(V * sizeof(node_t *));
    for (int i = 0; i < V; i++) {
        adj[i] = NULL;
    }
}

void addEdge(int u, int v) {
    push(&adj[u], v);
}

void printAllPathsUtil(int u, int d, bool visited[], int path[], int path_index) {
    visited[u] = true;
    path[path_index] = u;
    path_index++;
    if (u == d) {
        for (int i = 0; i < path_index; i++)
            printf("%d ", path[i]);
        printf("\n");
    } else {
        node_t *it;
        for (it = adj[u]; it != NULL; it = it->next)
            if (!visited[it->val])
                printAllPathsUtil(it->val, d, visited, path, path_index);
    }
    path_index--;
    visited[u] = false;
}

void printAllPaths(int s, int d) {
    bool *visited;
    visited = (bool *) malloc(V * sizeof(bool));
    int *path;
    path = (int *) malloc(V * sizeof(int));
    int path_index = 0;
    for (int i = 0; i < V; i++)
        visited[i] = false;
    printAllPathsUtil(s, d, visited, path, path_index);
}

int main() {
    V = 8;
    initGraph();
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
    addEdge(4, 6);
    addEdge(5, 6);
    addEdge(2, 3);
    addEdge(2, 4);
    addEdge(5, 7);
    addEdge(4, 7);
    int s = 1, d = 6;
    printf("Following are all different paths from %d to %d \n", s, d);
    printAllPaths(s, d);
    return 0;
}