数据结构第五次上机实习

实习题目：图的三种算法的同步演示

一、 上机实习题目与要求

问题描述

分别写出深度优先遍历、Prim算法与Dijkstra算法这三个算法，同时动态显示出相应的构造过程。

基本要求

（1）基于第3页ppt的图例构造图（权值可以自行设计添加）；

（2）分别使用深度优先遍历(DFS)、Prim、Dijkstra算法从任意用户输入的顶点开始对图进行遍历、求MST及最短路径；

（3）三个算法同时动态显示构造过程；

（4）每一步都要求显示/打印所有试探的路径(见第4页 ppt)；

（5）掌握单步调试；

二、数据结构设计

选择图的邻接表作为存储结构。因为邻接矩阵大量的元素都为0，这么多的冗余的零元素会造成存储空间的巨大浪费，但是邻接表可以解决这个问题，并且与邻接矩阵相比，邻接表更加的灵活，更便于操作。

三、源代码

stdfx.h

#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>
#include <stdlib.h>
#include <stack>
#include <string>
#include <iomanip>
#include <queue>
using namespace std;
#endif // !SYDFAX_H_INCLUDE

graph.h

#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#include "stdfax.h"

template <class T, class E>
//图中边结点的定义
struct Edge 
{ 
    int dest;               //边的另一顶点位置
    E weight;               //表上的权值
    Edge<T, E>* link;       //下一条边链的指针
};

template <class T, class E>
//顶点的定义
struct Vertex 
{ 
    T data;                 //顶点的关键值
    Edge<T, E>* ptr;        //边链表的头指针
};

template <class T, class E>
//用邻接表表示的图的类定义
class Graphlnk 
{
private:
    int maxVertices;            //图中顶点的最大数量
    int numEdges;               //当前的边数
    int numVertices;            //当前的顶点个数
    Vertex<T, E>* NodeTable;    //顶点表

public:       
    const E maxWeight = 5000;     //无穷大的值

    //构造函数
    Graphlnk(int sz = 30) 
    {   //默认数据大小为30个
        maxVertices = sz;           //顶点的最大数量为sz
        numEdges = 0;               //当前的边数为0
        numVertices = 0;            //当前顶点数为0
        NodeTable = new Vertex<T, E>[maxVertices]; // 创建顶点表数组
        if (NodeTable == NULL) 
        {   //分配失败时报错
            cerr << "存储空间分配错误！" << endl;
            exit(1);
        }
        for (int i = 0; i < maxVertices; i++)
        {   //将顶点表数组初始化
            NodeTable[i].ptr = NULL;
        }
    }

    //析构函数
    ~Graphlnk()
    { // 删除每个边链表中的结点
        for (int i = 0; i < numVertices; i++) 
        {   
            Edge<T, E>* p = NodeTable[i].ptr; //p为对应链表的首结点
            while (p != NULL) 
            { //重复删除第一个结点，直到删除完毕
                NodeTable[i].ptr = p->link;
                delete p;       //释放掉p的空间
                p = NodeTable[i].ptr;
            }
        }
        delete[] NodeTable; // 删除顶点表的数组
    }

    //获取顶点vertex在图中的位置
    int getVertexPos(T vertex)
    {
        for (int i = 0; i < numVertices; i++)
        {
            //在顶点表中遍历，找到即返回在图中的位置信息
            if (NodeTable[i].data == vertex)
                return i;
        }
        return -1;
    }

    //插入顶点
    bool insertVertex(T& vertex)
    {
        //如果顶点表满，不能插入图中
        if (numVertices == maxVertices)
        {
            return false;
        }
        NodeTable[numVertices].data = vertex; //将这个顶点放在表的最后位置
        numVertices++;                        //当前顶点数量增加1个
        return true;
    }

    //插入边
    bool insertEdge(int vertex1, int vertex2, E weight)
    {
        //首先要确保边的两个顶点是否合理
        if (vertex1 >= 0 && vertex1 < numVertices && vertex2 >= 0 && vertex2 < numVertices)
        {
            Edge<T, E>* q;
            Edge<T, E>* p = NodeTable[vertex1].ptr; //获取vertex1对应的边链表头指针
            while (p != NULL && p->dest != vertex2) //寻找邻接顶点vertex2
                p = p->link;
            if (p != NULL) //如果这条边已经存在，不插入，返回false
                return false;
            p = new Edge<T, E>; // 创建新的结点
            p->dest = vertex2;
            p->weight = weight;
            p->link = NodeTable[vertex1].ptr; //将其链入vertex1的边链表
            NodeTable[vertex1].ptr = p;
            q = new Edge<T, E>;
            q->dest = vertex1;
            q->weight = weight;
            q->link = NodeTable[vertex2].ptr; //将其链入v2边链表
            NodeTable[vertex2].ptr = q;
            numEdges++;                         //当前的边数增加1个
            return true;
        }
        return false;
    }

    //建立邻接表表示的图
    void CreatGraph()
    {
        int m, n;                   //分别存储顶点树和边数
        int i, j, k;                //i用于控制循环，j与k存储顶点在图中的位置
        T vertex1, vertex2;        //顶点
        E weight;                  //边的权值
        //获取用户输入的顶点数量和边的数量
        cout << "请输入顶点数和边数：";
        cin >> m >> n;
        cout << "请输入所有的顶点：" << endl;
        for (i = 0; i < m; i++)
        {
            cin >> vertex1;
            insertVertex(vertex1);  //将这个顶点插入图中
        }
        //获取图中的边信息
        cout << "请输入图的各边的信息：" << endl;
        i = 0;
        while (i < n) 
        {
            cin >> vertex1 >> vertex2 >> weight;
            //获取两个顶点的位置信息
            j = getVertexPos(vertex1);
            k = getVertexPos(vertex2);
            if (j == -1 || k == -1)
            {
                //不存在这两个定点时报错
                cout << "边两端点信息有误，请重新输入！" << endl;
            }
            else 
            {
                insertEdge(j, k, weight);       //在图中插入这条边
                i++;
            }
        }
    }

    //返回当前顶点数
    int numberOfVertices()
    {
        return numVertices;
    }

    //获取顶点v的第一个邻接顶点
    int getFirstNeighbor(int vertex)
    {
        if (vertex != -1) 
        {
            Edge<T, E>* p = NodeTable[vertex].ptr; //p为对应链表第一个边结点
            if (p != NULL)      
            {//如果边结点不为空，则返回第一个邻接顶点
                return p->dest;
            }
        }
        return -1; //否则第一个邻接顶点不存在，返回-1
    }

    //获取顶点v的邻接顶点w的下一邻接顶点
    int getNextNeighbor(int vertex, int w)
    {
        if (vertex != -1)
        {
            Edge<T, E>* p = NodeTable[vertex].ptr; //p为对应链表第一个边结点
            while (p != NULL && p->dest != w) 
            {//寻找vertex的邻接顶点w
                p = p->link;
            }
            if (p != NULL && p->link != NULL)
            {
                //返回vertex的下一个邻接顶点
                return p->link->dest; 
            }
        }
        return -1; //否则下一个邻接顶点不存在，返回-1
    }

    //获取位置为x的顶点的值
    T getValue(int x)
    {
        //x为合法位置时返回对应位置的值
        if (x >= 0 && x < numVertices)
            return NodeTable[x].data;
        return NULL;        //否则返回-1
    }

    //返回边（vertex1，vertex2）上的权值 
    E getWeight(int vertex1, int vertex2)
    {
        //两个顶点必须在图中存在
        if (vertex1 != -1 && vertex2 != -1)
        {
            Edge<T, E>* p = NodeTable[vertex1].ptr; //p为vertex1第一条关联的边
            while (p != NULL && p->dest != vertex2)
            { //寻找邻接顶点vertex2
                p = p->link;
            }
            if (p != NULL)
            {   //符合条件，返回两个顶点之间的权值
                return p->weight;
            }
        }
        return maxWeight; //否则边(vertex1, vertex2)不存在
    }

    //深度优先搜索
    void DFS(const T& vertex)
    {
        int i, loc, n = numberOfVertices();         //获取图中的顶点个数
        bool* visited = new bool[n];                 //创建辅助数组
        for (i = 0; i < n; i++)                     
        {   //辅助数组visited初始化
            visited[i] = false;
        }
        loc = getVertexPos(vertex);         //获取当前顶点的位置
        DFS(loc, visited);                  //从顶点vertex开始深度优先搜索
        cout << endl;
        delete[] visited;                   //遍历完成后释放辅助数组visited的空间
    }

    //深度优先搜索的子过程
    void DFS(int vertex, bool visited[])
    {
        cout << "搜索到的顶点为:" << getValue(vertex) << endl;    //访问顶点v
        visited[vertex] = true;                                 //将已经访问过的顶点作访问标记
        int w = getFirstNeighbor(vertex);                       //找顶点vertex的第一个邻接顶点w
        while (w != -1)                            
        {  
            if (visited[w] == true)
            {
                //如果邻接顶点w已经访问过，则需要回退
                cout << "回退的顶点为:" << getValue(w) << endl;
            }
            if (visited[w] == false)        //如果w没有访问过，递归访问顶点w
            {
                DFS(w, visited);
            }
            w = getNextNeighbor(vertex, w);    //获取vertex排在w后面的下一个邻接顶点
        }
    }
};
#endif    // !GRAPH_H_INCLUDED

prim.h

#ifndef Prim_H_INCLUDED
#define Prim_H_INCLUDED
#include "stdfax.h"
#include "graph.h"

template <class T, class E>
//最小生成树边结点结构体
struct MSTEdgeNode 
{ 
    int head, tail;         // 两顶点位置
    E weight;               // 边上权值
    //构造函数
    MSTEdgeNode() :tail(-1), head(-1), weight(0) {}; 
};

template <class T, class E>
//对<的重构
bool operator<(const MSTEdgeNode<T, E>& v1, const MSTEdgeNode<T, E>& v2) 
{
    if (v1.weight > v2.weight)
        return true;
    return false;
}

template <class T, class E>
//最小生成树的类定义
class MinSpanTree
{ 
private:
    int maxSize, currentSize;           //数组的最大的元素个数和当前元素个数
    MSTEdgeNode<T, E>* edgeValue;       //用边值数组存储树
public:
    //构造函数，默认为40个
    MinSpanTree(int sz = 40) 
    { 
        maxSize = sz;
        currentSize = 0;                        //当前元素个数为0个
        edgeValue = new MSTEdgeNode<T, E>[sz];  //创建数组存放边值
    }

    //析构函数
    ~MinSpanTree()
    { 
        delete[]edgeValue; //释放边值数组空间
    }

    //插入结点
    bool Insert(MSTEdgeNode<T, E>& value)
    {
        if (currentSize == maxSize - 1) 
        {   //数组已经满了，无法存储
            cout << "已满，无法存储！" << endl;
            return false;
        }
        //将元素插入数组
        edgeValue[currentSize++] = value;
        return true;
    }

    //Prim算法
    void Prim(Graphlnk<T, E>& G, const T vertice)
    {
        MSTEdgeNode<T, E> ed; //ed为边结点辅助单元
        int i, start, v, count;
        int n = G.numberOfVertices();           //n为图当前的顶点数
        start = G.getVertexPos(vertice);        //start为起始顶点号
        priority_queue<MSTEdgeNode<T, E>> H;    //H为最小堆
        bool* Vmst;
        Vmst = new bool[n];                     //Vmst为最小生成树顶点集合
        for (i = 0; i < n; i++)                 //初始化为未访问过
        {
            Vmst[i] = false;
        }
        Vmst[start] = true;                     //start作为第一顶点加入生成树
        count = 1;
        do { //一共有n个顶点，那么一共要找n-1条边来生成最小生成树
            //先找到与v相连并且未被访问过的邻接顶点，然后把相应的边放到最小堆中
            v = G.getFirstNeighbor(start);      //v为u的第一个邻接顶点
            while (v != -1) 
            { //检测u的所有邻接顶点
                if (Vmst[v] == false) 
                { //如果这个顶点没有被访问过，加入最小堆中
                    ed.tail = start;
                    ed.head = v;
                    ed.weight = G.getWeight(start, v);
                    H.push(ed);
                }
                v = G.getNextNeighbor(start, v); //找顶点start的邻接顶点v的下一个邻接顶点
            }
            //找当前顶点start与其他未访问的邻接顶点之间最小权值的边
            while (H.empty() == false && count < n) 
            {
                ed = H.top();           //从最小堆中删除最小权值的边ed
                H.pop();
                if (Vmst[ed.head] == false) 
                { //如果这个顶点没有被访问过，就插入到最小生成树中
                    Insert(ed); 
                    start = ed.head;
                    Vmst[start] = true; //将访问的结点标记为true
                    count++;
                    break;
                }
            }
        } while (count < n);
    }

    //打印MST树
    void printMST(Graphlnk<T, E>& G)
    {
        int tail, head;             //顶点所在位置
        T v1, v2;                   //两顶点
        E weight;                   //权值
        for (int i = 0; i < currentSize; i++)
        {
            tail = edgeValue[i].tail;    //找到第一个顶点所在位置
            head = edgeValue[i].head;   
            v1 = G.getValue(tail);     //获取顶点对应的值
            v2 = G.getValue(head);
            weight = G.getWeight(tail, head);   //获取(tail, head)的权值
            cout << "(" << v1 << "," << v2 << "," << weight << ")" << endl;
        }
    }
};
#endif    // !Prim_H_INCLUDED

Dijkstra.h

#ifndef DIJKSTRA_H_INCLUDED
#define DIJKSTRA_H_INCLUDED

#include "stdfax.h"
#include "graph.h"

template <class T, class E>
//Dijkstra算法
void Dijkstra(Graphlnk<T, E>& G, int v, E dist[], int path[])
{
    //G为一个带权的有向图，从v出发寻找最短路径
    //dist存放从顶点v到顶点j的最短路径的长度，path存放最短路径的路径过程
    int n = G.numberOfVertices();   //顶点数
    bool* s = new bool[n];          //s为最短路径顶点集
    int i, j, k, u;
    E w, min;
    for (i = 0; i < n; i++) 
    {
        dist[i] = G.getWeight(v, i); //用(v,i)边的权值初始化数组
        s[i] = false;               //所有顶点初始化为false表示未访问
        if (i != v && dist[i] < G.maxWeight) //顶点i为顶点v的邻接顶点
        {   //相邻时将v标记为顶点i的最短路径
            path[i] = v; 
        }
        else
        {   //不相邻时设置为-1
            path[i] = -1; 
        }
    }
    s[v] = true;    //访问过的顶点v加入s集合中
    dist[v] = 0;
    for (i = 0; i < n - 1; i++) 
    {
        min = G.maxWeight;
        u = v;           //选择不在集合S中具有最短路径的顶点u

        for (j = 0; j < n; j++) 
        { 
            if (s[j] == false && dist[j] < min) 
            { 
                u = j;
                min = dist[j];
            }
        }
        s[u] = true; //将顶点u加入到集合s
        //找到v的权值最小并且未被访问过的邻接顶点w
        for (k = 0; k < n; k++) 
        {
            w = G.getWeight(u, k);
            if (s[k] == false && w < G.maxWeight && (dist[u] + w) < dist[k]) 
            { //如果顶点k没有被访问过，并且从v->u->k的路径比v->k的路径短，则进行更新
                dist[k] = dist[u] + w;
                path[k] = u;
            }
        }
    }
}

template <class T, class E>
//输出最短路径
void print(Graphlnk<T, E>& G, int v, E dist[], int path[])
{
    int i, j, k;
    int n = G.numberOfVertices();       //获取当前的顶点个数
    int* d = new int[n];
    for (i = 0; i < n; i++) 
    {
        //输出到每个顶点的最短路径长度以及路径信息
        if (i != v) 
        { //不是顶点v时
            j = i;
            k = 0;
            while (j != v) 
            {
                d[k++] = j;
                j = path[j];
            }
            cout << "到顶点" << G.getValue(i) << "的最短路径为：" << G.getValue(v);
            while (k > 0)
            {   //依次输出最短路径的每个结点
                cout << "->" << G.getValue(d[--k]);
            }
            //输出最短路径的长度
            cout << "，其中最短路径长度为：" << dist[i] << endl;
        }
    }
}

#endif    // !DIJKSTRA_H_INCLUDED

main.cpp

#include "stdfax.h"
#include "graph.h"
#include "Dijkstra.h"
#include "prim.h"

int main()
{
    Graphlnk<int, int> G; // 声明图对象
    MinSpanTree<int, int> MST; //声明最小生成树对象
    int vertex;
    int dist[20], path[20], v;  //dist为两顶点间的最短路径长度，path为最短路径

    // 创建图
    G.CreatGraph();
    cout << "请输入第一个顶点vertex:" << endl;
    cin >> vertex;
    //深度遍历输出
    cout << "深度遍历：" << endl;
    G.DFS(vertex);

    //测试prim函数
    MST.Prim(G, vertex);
    cout << "根据Prim算法得到的最小生成树为：" << endl;
    // 打印最小生成树
    MST.printMST(G);
    cout << endl;

    //测试Dijkstra函数
    cout << "测试Dijkstra算法：" << endl;
    v = G.getVertexPos(vertex); //v为起始顶点的位置
    Dijkstra(G, v, dist, path); 
    print(G, v, dist, path); // 输出到各个顶点的最短路径

    system("pause");
    return 0;
}