#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

class graph
{
public:
    graph();
    graph(int);
    //graph(int, int);
    void setEdge(int src, int dst);
    void printGraph();//print graph
    void bfs(int);//Breadth First Search
    void dfs(int);//Depth First Search
    void bfsSpan(int);//Breadth First Search Spanning Tree
    void dfsSpan(int);//DepthFirt Search Spanning Tree
private:
    //internal struct to represent the node of the adjecency list
    struct node
    {
        int val;
        node *next;
    };

    int nodeCount;
    int edgeCount;

    //pointer to dynamically allocate an array of nodes
    node* list;
};
graph::graph()
{
    nodeCount = 0;
    edgeCount = 0;
    list = NULL;
}
graph::graph(int nodes)
{
    int i;
    nodeCount = nodes + 1;

    //allocate the array portion of the adjecnecy list
    //notice each node has a next pointer that will be use for
    //the linked list of adjacent nodes
    list = new node[nodeCount];

    //init the pointer of each index, notice we dont init the variable on the index
    for (i = 0; i<nodeCount; i++)
    {
        //give the value of the array index either some dummy val or the val of the node
        //we can choose either because in this interpretation our arrayy index is the val
        //of the node
        list[i].val = -1;
        list[i].next = NULL;
    }
}

void graph::setEdge(int source, int destination)
{
    node *temp;
    temp = new node;
    temp->val = destination;


    //add to the front of the list
    temp->next = list[source].next;
    list[source].next = temp;

    //increment edgecount
    edgeCount++;

}
void graph::bfs(int startVal)
{
    queue<int> q;
    vector<bool> visited;
    node * tmp;
    int i = 0;
    int node;

    for (i = 0; i<nodeCount; i++)
    {
        visited.push_back(false);
    }
    q.push(startVal);

    while (!q.empty())
    {
        node = q.front();
        q.pop();
        if (!visited[node])
        {
            cout << setw(3) << node;
            visited[node] = true;
            tmp = list[node].next;
            while (tmp != NULL)
            {
                if (!visited[tmp->val])
                {
                    q.push(tmp->val);

                }
                tmp = tmp->next;
            }
        }
    }cout << endl;

}
void graph::dfs(int startVal)
{
    stack<int> s;
    vector<bool> visited;
    node * tmp;
    int i = 0;
    int node;

    for (i = 0; i<nodeCount; i++)
    {
        visited.push_back(false);
    }
    s.push(startVal);

    while (!s.empty())
    {
        node = s.top();
        s.pop();
        if (!visited[node])
        {
            cout << setw(3) << node;
            visited[node] = true;
            tmp = list[node].next;
            while (tmp != NULL)
            {
                if (!visited[tmp->val])
                {
                    s.push(tmp->val);

                }
                tmp = tmp->next;
            }
        }
    }cout << endl;
}
void graph::bfsSpan(int startVal)
{
    queue<int> q;
    vector<bool> visited;
    vector<int> tree;
    node * tmp;
    int i = 0;
    int node;

    for (i = 0; i<nodeCount; i++)
    {
        visited.push_back(false);
        tree.push_back(-1);
    }
    q.push(startVal);

    while (!q.empty())
    {
        node = q.front();
        q.pop();
        if (!visited[node])
        {
            if (tree[node] != -1)
                cout << "(" << tree[node] << ", " << node << ")";

            visited[node] = true;
            tmp = list[node].next;
            while (tmp != NULL)
            {
                if (!visited[tmp->val])
                {
                    q.push(tmp->val);
                    if (tree[tmp->val] == -1)
                        tree[tmp->val] = node;
                }
                tmp = tmp->next;
            }
        }
    }cout << endl;
}
void graph::dfsSpan(int startVal)
{
    stack<int> s;
    vector<bool> visited;
    vector<int> tree;
    node * tmp;
    int i = 0;
    int node;

    for (i = 0; i<nodeCount; i++)
    {
        visited.push_back(false);
        tree.push_back(-1);
    }
    s.push(startVal);

    while (!s.empty())
    {
        node = s.top();
        s.pop();
        if (!visited[node])
        {
            if (tree[node] != -1)
                cout << "(" << tree[node] << ", " << node << ")";

            visited[node] = true;
            tmp = list[node].next;
            while (tmp != NULL)
            {
                if (!visited[tmp->val])
                {
                    s.push(tmp->val);
                    tree[tmp->val] = node;
                }
                tmp = tmp->next;
            }
        }
    }cout << endl;
}

void graph::printGraph()
{
    int i;
    node *tmp;

    cout << "Adjacency List" << endl;
    for (i = 0; i<nodeCount; i++)
    {
        cout << i << " | ";
        //get the font of the list for the index
        tmp = list[i].next;
        //walk the list and print off its values
        while (tmp != NULL)
        {
            cout << " ->" << setw(2) << tmp->val;
            tmp = tmp->next;
        }
        cout << " -> NULL" << endl;
    }
}

int main()//main
{
    graph *g1;
    int command;
    int numNodes;
    int numEdges;
    int sourceNode;
    int destinationNode;
    int directed;
    int start;

    ifstream myFile;

    myFile.open("dat.txt");//open dat.txt

    //get the number of nodes from the file
    myFile >> numNodes;

    //see whether the graph is directed or undirected
    //0 directed 1 undirected
    myFile >> directed;


    //init graph
    g1 = new graph(numNodes);

    while (myFile >> sourceNode)
    {
        myFile >> destinationNode;
        if (directed == 0)
        {
            //graph is directed
            g1->setEdge(sourceNode, destinationNode);
        }
        else 
        {
            //graph is undirected
            g1->setEdge(sourceNode, destinationNode);
            g1->setEdge(destinationNode, sourceNode);
        }
    }

    //should be done with the first file so close it
    myFile.close();

    //open the  command file
    myFile.open("cmd.txt");

    if (myFile)//if the command file opened successfully, process it.
    {
        while (myFile >> command)
        {
            if (command == 1)
            {
                myFile >> start;
                cout << "BFS Start: " << start << endl;
                g1->bfs(start);

            }
            else if (command == 2)
            {
                myFile >> start;
                cout << "DFS Start: " << start << endl;
                g1->dfs(start);

            }
            else if (command == 3)
            {
                myFile >> start;
                cout << "BFS Span Tree Start: " << start << endl;
                g1->bfsSpan(start);

            }
            else if (command == 4)
            {
                myFile >> start;
                cout << "DFS Span Tree Start: " << start << endl;
                g1->dfsSpan(start);

            }
            else
            {
                cout << "Error processing command. " << endl;
            }
        }
    }
    else//Display an error message
    {
        cout << "Error opening file. " << endl;
    }

    myFile.close();//close the file

    return 0;
}//end of main



dat.txt

7
1
1 3
1 4
1 2
2 4
2 5
3 4
3 6
4 5
4 6
4 7
5 7
6 7



cmd.txt

1 1
2 1
3 1
4 1

Having some trouble getting the right output here.
For BFS i am getting 1,2,4,5,7,6 Should i be getting 1,2,3,4,5,6?

Also for DFS i am getting 1,3,4,2,5,7,6 should i be getting 1,4,7,6,3,5,2?

if those two are wrong then my spanning trees are wrong.
Can someone point me in the right direction here

Thanks

Recommended Answers

All 3 Replies

Please post the contents of the node class.

Everything is included it should be towards the top Thanks :)

Anyone have any suggestions?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.