首页 > 代码库 > 构建带权路网

构建带权路网

2024-08-17 18:08:44   218人阅读

    今天来回顾一下带权路网的存储构建方法。    如今交通四通八达，路网密集，从一个地方到达另外一个地方，可以有很多条路径可以选择，今天我讲的就是路网的连通与不连通以及路线的代价（如路程或者颠簸程度等等作为评估路线的标准，取取值）在计算机中怎么存储起来，以及如何再现出来。

技术分享

假设有6个地点，点与点之间有8条直接相连的道路，那么在txt文件中主要分为三部分：

第一部分存储点数和直接相连的路线数，第二部分存储点的坐标值，第三部分存储路线（如：2  4  5，表示2号点与4好点直接相连，这条路线分配的权值是5），如左图。

那么这些关系如何在程序的结构中表现出来呢？

我们可以用一个数组vertex a[点数]来存储每个点的坐标，数组的下标对应点号；接着用一个二维数组int weight[点数][点数]来对应表示点与点之间的连接关系以及权值，如2  4  5，表示成 weight[2][4]=weight[4][2]=5。

好了，话不多说，直接上代码吧来得更简单粗暴一点（调皮脸）~^.^~

 

 

 

#include"stdafx.h"
#include<stdlib.h>
#include"Graph.h"
#include"targetver.h"
#define MAX_VERTEX_NUM 20

typedef struct Vertex
{
    double x, y;
}vertex;

typedef struct Graph
{
    vertex ver[MAX_VERTEX_NUM];
    int weight[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum;
    int arcnum;
}graph;

void main()
{
    graph *G;
    
    G = (graph *)malloc(sizeof(graph));

    FILE* fp = fopen("information.txt", "r");
    if (fp)
    {
        fscanf(fp, "%d", &(G->vexnum));  //顶点数
        fscanf(fp, "%d", &(G->arcnum));  //边数

        for (int i = 0; i <G->vexnum ; i++)  //顶点数组
            fscanf(fp, "%lf,%lf", &(G->ver[i].x),&(G->ver[i].y));

        int v1, v2, w;  //v1,v2从0开始  
        for (int i = 0; i < G->arcnum ; i++)  //构造邻接矩阵,边的权值关系
        {
            fscanf(fp, "%d %d %d", &v1, &v2, &w);
            G->weight[v1][v2] = w;
        }
    }fclose(fp);

    setOrig(0, 0);

    for (int i = 0; i < G->vexnum; i++)
    {
        drawRectangle(G->ver[i].x,G->ver[i].y);
        
        char label[5];
        sprintf(label, "%d", i);
        
        drawText(G->ver[i].x, G->ver[i].y, label);
        
        for (int j = 0; j <G->vexnum; j++)
        {
            if (G->weight[i][j]>0)
            {
                moveTo(G->ver[i].x, G->ver[i].y);
                lineTo(G->ver[j].x,G->ver[j].y);
            }
        }
    }

    getchar();
}

接下来就是见证奇迹的时刻！duang~~duang~~duang~~

技术分享

构建带权路网


联系
我们