データ構造網図(C++)

2685 ワード

初めてブログを書くので、今日習ったC++データ構造の授業後の宿題を書きましょう.授業後の宿題は本のコードに基づいて方向性のないネット図を書くことです.授業で先生はいくつかの問題について話しました(1.深さ優先ループを使用してから広さ優先ループを使用する場合は、タグ配列visited[MaxSize]を0に初期化する必要があります.2.次にvisited[]を宣言します.結局、本に声明がないので、どちらも読みやすいと思います).しかし、夜、自分で書いたときに先生の言ったことに注意してから問題が発生しました.深度優先ループに問題が発生し、自分の望む結果が出力されません.そして半日見て、初期化の問題かと思った.の半日見てから再帰関数に問題があり,jの値が前回の大サイクルに戻ってこない値を変えて結果に問題があることが分かった.説明がはっきりしていませんが、結局初めて使います.直接コードを添付しましょう.の
#include 

using namespace std;
const int MaxSize = 10;

template 
class MGraph
{
public:
    MGraph(T a[], int n, int e);
    ~MGraph(){}
    void DF(int v);
    void BF(int v);
    void chushi();
private:
    T vertex[MaxSize];
    int arc[MaxSize][MaxSize], visited[MaxSize], Q[MaxSize], b[MaxSize];
    int vertexNum, arcNum;
    int i, j, m, k, front, rear;
};

template 
MGraph::MGraph(T a[], int n, int e)
{
    vertexNum = n; arcNum = e;
    for(i = 0; i < vertexNum; i++)
        vertex[i] = a[i];
    for(i = 0; i < vertexNum; i++)
        for(j = 0; j < vertexNum; j++)
            arc[i][j] = 0;
    for(k = 0; k < arcNum; k++)
    {
        cin >> i >> j;
        arc[i][j] = 1; arc[j][i] = 1;
    }
}

template 
void MGraph::chushi()
{
    for(i = 0; i < vertexNum; i++)
        visited[i] = 0;
    m = 0;
}

template 
void MGraph::DF(int v)
{
    cout << vertex[v]; visited[v] = 1;
    for(j = 0; j < vertexNum; j++)
        if(arc[v][j] == 1 && visited[j] == 0)
        {
            b[m++] = j;
            DF(j);
        }
    j = b[m--] + 1;
}

template 
void MGraph::BF(int v)
{
    for(i = 0; i < vertexNum; i++)
        visited[i] = 0;
    front = rear = -1;
    cout << vertex[v]; visited[v] = 1; Q[++rear] = v;
    while(front != rear)
    {
        v = Q[++front];
        for(j = 0; j < vertexNum; j++)
            if(arc[v][j] == 1 && visited[j] == 0)
            {
                cout << vertex[j]; visited[j] = 1; Q[++rear] = j;
            }
    }
}

int main()
{
    int str[4] = {1, 2, 3, 4};
    MGraph Tu(str, 4, 3);
    Tu.chushi();
    Tu.DF(2);
    cout << endl;
    Tu.BF(0);
    return 0;
}

//             
template 
void MGraph::DF(int v)
{
    cout << vertex[v]; visited[v] = 1;
    for(j = 0; j < vertexNum; j++)
        if(arc[v][j] == 1 && visited[j] == 0)
            DF(j);
}