嘘~ 正在从服务器偷取页面 . . .

实验五


你的任务是:

    1. 求所有顶点的入度和出度
    2. 深度优先搜索(遍历)
    3. 广度优先搜索(遍历)
    4. Dijkstra求最短路(从0点出发至其他各点)
    5. prim算法求最小支撑树(从0点出发至其他各点)
  • 你需要打开头文件grlist.h以及grmat.h,在函数getInDegree以及getOutDegree处填写相关代码,测试完成第1项任务。
  • 你需要打开头文件Graph_test.h,填写相关代码,完成第2~5项任务。
  • 除以上文件相应的位置外,请不要改变其他任何代码,否则将可能不能通过测试。

grlist.h

int getInDegree(int v) // 求顶点v的入度
    {
        int result = 0;
        //............... 在此行以下插入补充代码
        for (int i = 0; i < numVertex; i++)
        {
            if (isEdge(i, v))
                result++;
        }
        //............... 在此行以上插入补充代码
        return result;
    }

int getOutDegree(int v) // 求顶点v的出度
    {
        int result = 0;
        //............... 在此行以下插入补充代码
        result = vertex[v]->length();
        //............... 在此行以上插入补充代码
        return result;
    }

grmat.h

int getInDegree(int v) // 求顶点v的入度
    {
        int result = 0;

        //............... 在此行以下插入补充代码
        for (int i = 0; i < numVertex; i++)
        {
            if (matrix[v][i] != 0)
                result++;
        }
        //............... 在此行以上插入补充代码
        return result;
    }

int getOutDegree(int v) // 求顶点v的出度
    {
        int result = 0;
        //............... 在此行以下插入补充代码
        for (int i = 0; i < numVertex; i++)
        {
            if (matrix[i][v] != 0)
                result++;
        }
        //............... 在此行以上插入补充代码
        return result;
    }

Graph_test.h

//深度优先算法
void DFS(int v, void (*PreVisit)(int v), void (*PostVisit)(int v), void (*Visiting)(int v)) // Depth first search
    {
        PreVisit(v);
        G->setMark(v, VISITED);
        Visiting(v);
        for (int nbr = G->first(v); nbr < G->n(); nbr = G->next(v, nbr))
        {
            if (G->getMark(nbr) == UNVISITED)
                DFS(nbr, PreVisit, PostVisit, Visiting);
        }
        PostVisit(v);
    }

//广度优先算法
void BFS(int start, void (*PreVisit)(int v), void (*PostVisit)(int v), void (*Visiting)(int v))
    {
        queue q;
        q.push(start);
        PreVisit(start);
        G->setMark(start, VISITED);
        while (!q.empty())
        {
            int it = q.front();
            q.pop();
            Visiting(it);
            for (int nbr = G->first(it); nbr < G->n(); nbr = G->next(it, nbr))
            {
                if (G->getMark(nbr) == UNVISITED)
                {
                    PreVisit(nbr);
                    G->setMark(nbr, VISITED);
                    q.push(nbr);
                }
            }
            PostVisit(it);
        }
    }

void Dijkstra1(int *D, int s)
    {
        bool q[G->n()];
        memset(q, 0, sizeof(q));
        while (!all_visited(q))
        {
            int it = minVertex(D);
            q[it] = VISITED;
            G->setMark(it, VISITED);
            for (int nbr = G->first(it); nbr < G->n(); nbr = G->next(it, nbr))
            {
                if (D[it] + G->weight(it, nbr) < D[nbr])
                    D[nbr] = D[it] + G->weight(it, nbr);
            }
        }
    }

文章作者: 目棃
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 目棃 !
评论
  目录