0
J'ai un graphique créé à partir d'une liste d'adjacence, j'essaie de faire en sorte que le DFS imprime également le postorder du graphique. Est-ce que quelqu'un a des suggestions sur la façon dont je pourrais le faire dans la fonction DFS? je vous remercie beaucoupUtilisation de DFS pour l'impression d'un ordre numérique
entrée exemple:
create 6
insert 0 3 0
insert 0 1 0
insert 1 3 0
insert 1 2 0
insert 2 1 0
insert 3 5 0
insert 3 4 0
insert 3 2 0
insert 4 2 0
insert 5 2 0
DFS 0
CODE:
main.cpp
using namespace std;
#include "graph.h"
//Main Function
int main(){
string command,command1;
int src,dest,wght,start,size;
cout << "graph>";
cin>>command;
if(command=="create")
cin>>size;
graph A(size); //initial class instance
//handles all I/O
do{
cout << "graph>";
cin >> command;
//Creates an array of size "size" for nodes to be added too
//if(command == "create"){
//cin>>size;
//resize(size);
//}
//Tests for user insertion of node
if (command == "insert"){
cin >> src >> dest >> wght;
if(src <= size && dest <= size){
A.insert(src, dest, wght);
}
else{
cout<<"Error! Node does not exist!"<<endl;
}
}
//Tests for user removal of node
else if(command == "remove"){
cin >> src >> dest;
if(src <= size && dest <= size){
A.remove(src, dest);
}
else{
cout<<"Error! Node does not exist!"<<endl;
}
}
//Tests for user printing of graph
else if(command == "DFS"){
cin >> start;
A.DFS(start);
}
//Tests for user printing of graph
else if(command == "print"){
A.print();
}
else{
if(command != "quit")
cout<<"Error! Command not supported."<<endl;
}
}while(command != "quit");
return 0;
}
graph.h
//graph class file
using namespace std;
#include "node.h"
class graph{
private:
int h,f;
int state[30];
int counter[30];
class alist* array;
public:
//Initializes the Graph and fills it with NULLs
graph(int h){
this->h = h;
array = new alist [h];
for (int i = 0; i < h; ++i)
array[i].head = NULL;
}
//Creates a new node by calling instance newlist of listnode
listnode* newlist(int dest){
listnode* newnode = new listnode;
newnode->dest = dest;
newnode->next = NULL;
return newnode;
}
//Connects the node of the Graph
void insert(int src, int dest, int weight){
listnode* newnode = newlist(dest);
newnode->next = array[src].head;
newnode->weight = weight;
array[src].head = newnode;
newnode = newlist(src);
newnode->next = array[dest].head;
}
//Removes a node from the graph
void remove(int srcr, int destr){
for (int i = 0; i < h; ++i){
listnode* move = array[i].head;
while (move){
if(destr == move->dest){
if(srcr==i)
array[i].head = NULL;
}
move = move->next;
}
}
}
//Prints the Graph
void print(){
for (int i = 0; i < h; ++i){
listnode* move = array[i].head;
while (move){
cout<<"("<<i <<","<< move->dest<< ","<< move->weight <<")";
move = move->next;
}
}
cout<<endl;
}
//Traverses the graph using DFS
int DFS(int start){
state[start]=1; //marks the node as visited
if(start==(h)){ //exits once all nodes have been visited
return 0;}
listnode* move = array[start].head;
cout<<"Visited "<<start<<endl;
if(state[start]!=1){
DFS(start);}
start++;
DFS(start);
}
};
list.h
//list class file
using namespace std;
#include <iostream>
#include <cstdlib>
//Adjacency List
class alist
{
public:
class listnode *head;
};
node.h
//node class file
using namespace std;
#include "list.h"
//Nodes
class listnode
{
public:
int dest;
int weight;
class listnode* next;
};
Qu'entendez-vous par postorder? –
Comme dans LRV, visitez les noeuds gauches, visitez les bons noeuds, visitez l'origine. Donc, pour ce graphique, ce serait 2-4-5-3-1-0. Je ne peux pas l'implémenter. – armour