#include<bits/stdc++.h>
#define maxvertexnum 100 //最大顶点
#define infinity 65535 // ∞设为双字节无符号整数的最大值65535
using namespace std;

typedef int vertex; //用顶点下标表示顶点,为整型
typedef int weighttype; //边的权值
typedef char datatype; //顶点储存的数据类型
typedef struct enode *ptrtoenode;
struct enode{
    vertex v1,v2; //有向边<v1,v2>
    weighttype weight; //权重
};
typedef prttoenode edge; //图结点的定义
typedef gnode *ptrtognode;
struct gnode{
    int nv; //顶点数
    int ne; //边数
    weighttype g[maxvertexnum][maxvertexnum]; //邻接矩阵
    datatype data[maxvertexnum]; //存顶点的数据
    //注意:很多情况下,顶点无数据,此时data[]可以不用出现
};
typedef ptrtognode mgraph; //以邻接矩阵存储的图类型
mgraph creatgraph(int vertexnum){
    /* 初始化一个有vertexnum个顶点但没有边的图 */
    vertex v,w;
    mgraph graph;
    graph = (mgraph)malloc(sizeof(struct gnode));
    graph->nv = vertexnum;
    graph->ne = 0;//初始化邻接矩阵,这里默认顶点编号从0开始,到(graph->nv-1)
    for(v = 0; v<graph->nv; v++){
        for(w = 0; w<graph->nv; w++){
            graph->g[v][w] = infinity;
        }
    }
    return graph;
}

void insertedge(mgraph graph,edge e){
    //插入边<v1,v2>
    graph->g[e->v1][e->v2] = e->weight; 
    //若是无向图,还要插入边<v1,v2>
    //graph->g[e->v2][e->v1] = e->weight;
}

mgraph buildgraph(){
    mgraph graph;
    edge e;
    vertex v;
    int nv,i;
    scanf("%d",&nv);//读入顶点个数
    graph = creatgraph(nv);//初始化有nv个顶点但没有边的图
    scanf("%d",&(graph->ne));//边数
    if(graph->ne != 0){
        e = (edge)malloc(sizeof(struct enode));
        //建立边结点,读入边,格式化为“起点 终点 权重”,插入邻接矩阵
        for(i = 0; i<graph->ne; i++){
            scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
            //注意如果权重不是整型,%d要改
            insertedge(graph , e);
        }
    }
    for(v = 0; v<graph->nv; v++){
        scanf("%c",&(graph->data[v]));
    }
    return graph;
}

邻接矩阵

分类: 未分类

0 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注