数据结构实验6：图的应用

发布时间：2024年01月18日

一、实验目的

1．掌握图的邻接矩阵的存储定义；

2．掌握图的最短路径（Dijsktra）算法的实现。

二、实验原理

1. 邻接矩阵

邻接矩阵是一种表示图的方法。它是一个二维数组，用于表示图中各个顶点之间的连接关系。如果图是有向图，那么邻接矩阵是对称的；如果是无向图，邻接矩阵可能不是对称的。

顶点的编号： 假设图有n个顶点，通常是从1到n。

构建矩阵： 创建一个n x n的矩阵，其中元素a[i][j]表示顶点i到顶点j是否有边。如果存在边，通常用1表示；如果不存在边，通常用0表示。

例如，对于无向图，如果顶点i和顶点j之间有边，则a[i][j]和a[j][i]都设置为1。对于有向图，只需设置a[i][j]为1表示从顶点i到顶点j有一条有向边。

权重： 如果图中的边有权重，可以在矩阵中存储这些权重。矩阵的元素a[i][j]可以表示从顶点i到顶点j的权重值。

2. 邻接矩阵表示图的结构定义

#define MAX_SIZE 100

struct Graph {
    int numVertices;//节点数
    int adjMatrix[MAX_SIZE][MAX_SIZE];//邻接矩阵
};

?3. 图的初始化

创建一个空的图数据结构并为其设置初始状态。

void InitializeGraph(struct Graph* graph,int num) {
    int i, j;
    graph->numVertices = num;
    for (i = 0; i < num; i++) {
        for (j = 0; j < num; j++) {
            graph->adjMatrix[i][j] = 0;
        }
    }
}

4. 边的添加

?在图中增加边，将该边置为1，表示存在，或者权值

若是无向图，由于对称性，则需要改变两条边

//添加边
void addEdge(struct Graph* graph, int startVertex, int endVertex) {
    graph->adjMatrix[startVertex][endVertex] = 1;
    //若是无向图
    graph->adjMatrix[endVertex][startVertex] = 1;
}

?5. 边的删除

置为0(不存在)或者无限大的权值

void deleteEdge(struct Graph* graph, int startVertex, int endVertex) {
    graph->adjMatrix[startVertex][endVertex] = 0;
    //若是无向图
    graph->adjMatrix[endVertex][startVertex] = 0;
}

6.?Dijkstra算法?

Dijkstra算法是一种用于在带有非负权重的图中找到单源最短路径的算法。该算法的基本思想是从起始顶点开始，逐步扩展到离起始顶点的距离最短的顶点，直到到达目标顶点为止。

初始化： 对于每个顶点v，初始化距离值dist[v]为无穷大（表示尚未到达该顶点），并将起始顶点的距离值dist[start]设置为0。创建一个优先队列（最小堆），将起始顶点加入队列。

更新距离值： 从优先队列中取出距离值最小的顶点u。对于u的每个邻接顶点v，如果通过u可以缩短到达v的距离（dist[start] + weight(u, v) < dist[v]），则更新dist[v]的值。更新后，将v加入优先队列。

重复步骤2： 重复上述步骤，直到优先队列为空。这样，对于每个顶点，dist数组中存储的值就是从起始顶点到达该顶点的最短路径距离。

Dijkstra算法的关键在于通过贪心策略，每次选择距离起始顶点最近的顶点进行扩展。这确保了每个顶点的最短路径被逐步确定，直到到达目标顶点

//Dijkstra算法
void dijkstra(struct Graph* graph, int startVertex) {
    int dist[MAX_SIZE];  // 存储从起始节点到各节点的最短距离
    int visited[MAX_SIZE] = { 0 };  // 标记节点是否被访问过

    // 初始化距离数组
    for (int i = 0; i < graph->numVertices; i++) {
        dist[i] = INT_MAX;
    }

    // 起始节点到自身的距离为0
    dist[startVertex] = 0;

    for (int count = 0; count < graph->numVertices - 1; count++) {
        int minDist = 9999;
        int minIndex;

        // 选择距离最小的未访问节点
        for (int v = 0; v < graph->numVertices; v++) {
            if (!visited[v] && dist[v] < minDist) {
                minDist = dist[v];//当前最短距离
                minIndex = v;//当前最短的点
            }
        }

        // 标记节点为已访问
        visited[minIndex] = 1;

        // 更新最短距离数组
        //!visited[v]：检查节点 v 是否已经被访问过，如果节点已经被访问过，则不需要更新最短距离。
        //graph->adjacencyMatrix[minIndex][v] != 9999：检查从当前节点 minIndex 到节点 v 是否存在边。9999 表示两个节点之间没有直接的连接，因此如果这个条件为真，说明节点 minIndex 和节点 v 之间存在边。
        // dist[minIndex] != 9999：检查起始节点到节点 minIndex 的最短距离是否已经被初始化，如果没有被初始化，说明当前节点 minIndex 不可达，无法通过它来更新其他节点的距离。
        //(dist[minIndex] + graph->adjMatrix[minIndex][v] < dist[v])：检查通过当前节点 minIndex 更新节点 v 的距离是否比已知的最短距离 dist[v] 更短。如果是，就更新 dist[v] 为更短的距离。
        for (int v = 0; v < graph->numVertices; v++) {
            if (!visited[v] && graph->adjMatrix[minIndex][v] != 9999 && dist[minIndex] != 9999 && (dist[minIndex] + graph->adjMatrix[minIndex][v] < dist[v])) {
                dist[v] = dist[minIndex] + graph->adjMatrix[minIndex][v];
            }
        }
    }

    // 打印最短距离
    cout<<"从"<< startVertex<<"节点为起点"<<endl;
    for (int i = 0; i < graph->numVertices; i++) {
        cout<<"到"<<i<<"节点的最短距离为：" << dist[i]<<endl;
    }
}

三、实验内容

实验内容

必做内容：

设计安徽大学的校园平面图，所含景点不少于 8 个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件 graph.txt 中，系统执行时所处理的数据要对此文件分别进行读写操作。

1．从文件 graph.txt 中读取相应数据, 创建一个图,使用邻接矩阵表示图；

2．景点信息查询：为来访客人提供校园任意景点相关信息的介绍；

3．问路查询：为来访客人提供校园任意两个景点之间的一条最短路径；

选做内容（对文件进行操作，相应信息变化后，再次进行景点信息查询和

问路查询时应该有所体现）：

1. 修改一个已有景点的相关信息；

2. 增加一个新景点及其相关信息；

3. 增加一条新的路径；

4. 删除一个景点及其相关信息；

5. 删除一条路径。

代码

#define _CRT_SECURE_NO_WARNINGS
#include<fstream>
#include<iostream>
using namespace std;

#define MAX_SIZE 100

struct Graph {
    int numVertices;//节点数
    int adjMatrix[MAX_SIZE][MAX_SIZE];//邻接矩阵，用来储存距离
    char address[MAX_SIZE][MAX_SIZE];//景点名称
    char intro[MAX_SIZE][MAX_SIZE];//景点介绍
};

//图的初始化
void InitializeGraph(struct Graph* graph,int num) {
    int i, j;
    graph->numVertices = num;
    for (i = 0; i < num; i++) {
        for (j = 0; j < num; j++) {
            graph->adjMatrix[i][j] = 9999;
        }
    }
}

//添加边
void addEdge(struct Graph* graph, int startVertex, int endVertex,int length) {
    graph->adjMatrix[startVertex][endVertex] = length;
    //若是无向图
    graph->adjMatrix[endVertex][startVertex] = length;
}

//删除边
void deleteEdge(struct Graph* graph, int startVertex, int endVertex) {
    graph->adjMatrix[startVertex][endVertex] = 0;
    //若是无向图
    graph->adjMatrix[endVertex][startVertex] = 0;
}

//找到编号对应的景点名称
void find_address(struct Graph* graph, int index) {
    cout << graph->address[index];
}

//Dijkstra算法
void dijkstra(struct Graph* graph, int startVertex, int endVertex) {
    int visited[MAX_SIZE] = { 0 };//记录是否被访问过

    int pre[MAX_SIZE] = { startVertex };//记录前驱点编号
    int min_leng[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
        min_leng[i] = 9999;
    }
    visited[startVertex] = 1;
    int min_length = 9999;
    int min_index = startVertex;
    //第一轮
    for (int j = 0; j < graph->numVertices; j++) {
        if (visited[j] == 0) {//如果未被访问过
            //cout << graph->adjMatrix[startVertex][j] << "   " << min_leng[j] << endl;
            if (graph->adjMatrix[startVertex][j]  < min_leng[j]) {//如果新的起始点到达终点的距离更短，则前驱节点为新的起始点
                //find_address(graph, j);
                pre[j] = startVertex;
                min_leng[j] = graph->adjMatrix[startVertex][j] ;
            }
        }
        //cout << endl;
        for (int j = 0; j < graph->numVertices; j++) {//找最短路径作为新一轮的起始点
            if (visited[j] == 0) {//如果未被访问过
                if (min_leng[j] < min_length) {
                    min_length = min_leng[j];
                    min_index = j;
                }
            }
        }
        visited[min_index] = 1;
    }

    for (int i = 0; i < graph->numVertices - 2; i++) {//共顶点数-2轮    
        for (int j = 0; j < graph->numVertices; j++) {
            if (visited[j] == 0) {//如果未被访问过
                //cout <<graph-> adjMatrix[min_index][j]<<"   " << min_leng[j] << endl;
                if ((graph->adjMatrix[min_index][j] + min_length) < min_leng[j]) {//如果新的起始点到达终点的距离更短，则前驱节点为新的起始点
                    //find_address(graph, j);
                    pre[j] = min_index;
                    min_leng[j] = graph->adjMatrix[min_index][j] + min_length;
                }
            }
            //cout << endl;
        }
        //cout << "更新一轮"<<endl;
        for (int j = 0; j < graph->numVertices; j++) {
            //cout << min_leng[j] << " ";
        }
        min_length = 9999;
        min_index = startVertex;
        for (int j = 0; j < graph->numVertices; j++) {//找最短路径作为新一轮的起始点
            if (visited[j] == 0) {//如果未被访问过
                if (min_leng[j] < min_length) {
                    min_length = min_leng[j];
                    min_index = j;
                }
            }
        }
        visited[min_index] = 1;
        //cout << "这一轮起始点为";
        //find_address(graph, min_index);
       // cout << endl << "到达起始点距离为" << min_length << endl;
    }
    cout <<"最短距离为："<< min_leng[endVertex]<<endl;
    //输出最短路径，从后往前找前驱
    cout << "最短路径为：";
    int count = 2;
    int road[MAX_SIZE] ;
    for (int i = 0; i < MAX_SIZE; i++) {
        road[i] = endVertex;
    }
    road[0] = startVertex;
    int end = endVertex;//尾
    while (pre[end] != startVertex) {//计算路径中的景点数
        count++;
        end = pre[end];
    }
    end = endVertex;
    for (int i = count - 2; i >= 0; i--) {
        road[i] = pre[end];
        end = pre[end];
    }
    int flag = 1;
    for (int i = 0; i < count; i++) {
        if (flag == 0) {
            cout << "->";
        }
        find_address(graph, road[i]);
        flag = 0;
    }
    return;
}

//找到该景点对应的编号
int find_index(struct Graph* graph, char string[]) {
    for (int i = 0; i < graph->numVertices; i++) {
        if (strcmp(string, graph->address[i]) == 0) {
            return i;
        }
    }
    cout << "不存在该景点" << endl;
    return -1;
}

//景点信息查询
void volun1(struct Graph* graph) {
    cout << "本校景点有：" << endl;
    for (int i = 0; i < graph->numVertices; i++) {
        cout <<i<<":"<< graph->address[i] << endl;
    }
    char string1[MAX_SIZE];
    cout << "请输入你要查询的景点:";
    cin >> string1;
    int index = find_index(graph, string1);
    cout << graph->intro[index] << endl;
}

//最短路径查询
void volun2(struct Graph* graph) {
    char source[MAX_SIZE], destination[MAX_SIZE];
    cout << "请输入起始景点和目的景点:";
    cin >> source >> destination;
    int start = 0, end = 0;
    start = find_index(graph, source);
    end = find_index(graph, destination);
    dijkstra(graph, start, end);
    cout << endl;
}

//增加景点相关信息
void volun3(struct Graph* graph) {
    char address[MAX_SIZE], intro[MAX_SIZE];
    cout << "请输入你要增加的景点名称及其相关信息："<<endl;
    cin >> address >> intro;
    //将信息复制进去
    strcpy(graph->address[graph->numVertices], address);
    strcpy(graph->intro[graph->numVertices], intro);
    graph->numVertices++;//修改节点数
    //相关路径全改为无穷大
    for (int i = 0; i < graph->numVertices; i++) {
        graph->adjMatrix[i][graph->numVertices - 1] = 9999;
    }
    for (int i = 0; i < graph->numVertices; i++) {
        graph->adjMatrix[graph->numVertices - 1][i] = 9999;
    }
}

//修改景点的相关信息
void volun4(struct Graph* graph) {
    char address[MAX_SIZE], intro[MAX_SIZE];
    cout << "请输入你要修改的景点名称及其相关信息：" << endl;
    cin >> address >> intro;
    //找到编号
    int des_index = find_index(graph, address);
    //修改
    memset(graph->intro[des_index], MAX_SIZE, sizeof(char));//清空
    strcpy(graph->intro[des_index], intro);
}

//增加路径
void volun5(struct Graph* graph) {
    char source[MAX_SIZE], destination[MAX_SIZE]; 
    int length;
    cout << "请输入你要增加的路径:" << endl;
    cin >> source >> destination >> length;
    int start = find_index(graph, source);
    int end = find_index(graph, destination);
    addEdge(graph, start, end, length);
}

//删除一个景点及其相关信息
void volun6(struct Graph* graph) {
    char address[MAX_SIZE];
    cout << "请输入你要删除的景点：" << endl;
    cin >> address;
    int index = find_index(graph, address);
    //清空
    memset(graph->address[index], MAX_SIZE, sizeof(char));
    memset(graph->intro[index], MAX_SIZE, sizeof(char));
}

//删除一条路径
void volun7(struct Graph* graph) {
    char source[MAX_SIZE], destination[MAX_SIZE];
    cout << "请输入你要删除的路径:" << endl;
    cin >> source >> destination;
    int start = find_index(graph, source);
    int end = find_index(graph, destination);
    deleteEdge(graph, start, end);
}

int main() {
    struct Graph q;
    int num_V, num_a;//顶点数目，边的个数
    FILE* filePointer;
    filePointer = fopen("C:\\Users\\Administrator\\Desktop\\graph.txt", "r");
    // 检查文件是否成功打开
    if (filePointer == NULL) {
        cout << "无法打开文件";
        return 1; // 退出程序
    }
    char buffer[1000];
    char Address[MAX_SIZE], Intro[MAX_SIZE];
    // 读取一行数据
    if (fgets(buffer, sizeof(buffer), filePointer) != NULL) {
        if (sscanf(buffer, "%d %d", &num_V, &num_a) == 2) {
            q.numVertices = num_V;
             //cout << num_V << " " << num_a<<endl;
        }
        else {
            cout<<"错误：无法从字符串中提取两个数字。" << endl;
        }
    } 
    else {
        cout<<"错误：文件为空或无法读取。" << endl;
    }

    InitializeGraph(&q, num_V);//初始化图
    //读取景点名称及其介绍
    for (int i = 0; i < num_V; i++) {
        if (fgets(buffer, sizeof(buffer), filePointer) != NULL) {
            if (sscanf(buffer, "%s %s", Address, Intro) == 2) {
                strcpy(q.address[i], Address);
                strcpy(q.intro[i], Intro);
                //cout << q.address[i] << endl;
                //cout << q.intro[i] << endl;
            }
            else {
                printf("错误：无法从字符串中提取两个字符串。\n");
            }
        }
        else {
            cout << "错误：文件为空或无法读取。" << endl;
        }
    }
    //读取景点之间距离
    char source[MAX_SIZE], destination[MAX_SIZE];
    int length=0;
    for (int i = 0; i < num_a; i++) {
        if (fgets(buffer, sizeof(buffer), filePointer) != NULL) {
            if (sscanf(buffer, "%s %s %d", source, destination,&length) == 3) {
                int index1 = find_index(&q, source);
                int index2 = find_index(&q, destination);
                q.adjMatrix[index1][index2] = length;
                q.adjMatrix[index2][index1] = length;
                //cout << index1 << " " << index2 << " " << length << endl;
            }
            else {
                cout<<"错误：无法从字符串中提取两个字符串，一个数字。"<<endl;
            }
        }
        else {
            cout << "错误：文件为空或无法读取。" << endl;
        }
    }
    // 关闭文件
    fclose(filePointer);

    //信息填充完毕，接下来是查阅环节
    int code;
    cout << "********************欢迎来到安徽大学！********************" << endl;
    cout << "               1.查询景点信息" << endl;
    cout << "               2.问路查询" << endl;
    cout << "               3.增加一个景点及其相关信息" << endl;
    cout << "               4.修改一个景点的相关信息" << endl;
    cout << "               5.增加一个新的路径" << endl;
    cout << "               6.删除一个景点及其相关信息" << endl;
    cout << "               7.删除一条路径" << endl;
    cout << "               8.退出" << endl;
    cout << "********************安大校园导游系统*********************" << endl;
    cout << "请选择需要的服务：(1-8)" << endl;
    cin >> code;
    while (code != 8) {
        switch (code)
        {
        case 1: volun1(&q);          break;
        case 2: volun2(&q);          break;
        case 3: volun3(&q);          break;
        case 4: volun4(&q);          break;
        case 5: volun5(&q);          break;
        case 6: volun6(&q);          break;
        case 7: volun7(&q);          break;
        }
        cin >> code;
    }
    cout << "退出" << endl;
    return 0;
}

截图

分析

对于上述代码，是存在一个问题的，比如增加一个节点，删除俩个节点，总数目减少，但是最大索引值是在增加的，所以再次实现其他功能的时候是不切实际的

way1：提供一个有效位数组，按最大索引值的范围查找

way2: 当删除时，后面的节点索引值应该加以改变，但是很麻烦

此外上述代码提到了sscanf函数

sscanf函数接受一个字符串作为输入，并根据指定的格式从该字符串中读取数据，然后将数据存储在相应的变量中。
#include <stdio.h>

int sscanf(const char *str, const char *format, ...);
str是包含格式化数据的输入字符串。
format是描述输入字符串中数据格式的格式字符串。
可变参数（...）是用于存储从输入字符串中读取的数据的变量列表。

文章来源:https://blog.csdn.net/weixin_58628068/article/details/135569045
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！