#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

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

Edited 8 Months Ago by brandon66

This question has already been answered. Start a new discussion instead.