当前位置：首页 > article >正文

【数据结构】图笔记

article 2024/11/15 4:15:05

树是一种特殊的图。

（单链表树有向，双链表树无向）无环，每条路径权重均为1，每个节点最多只有两条路径连通别的点。

不抽象来看，一棵树里的连通其实完全可以用矩阵来表示，但由于树每个节点只有两个直接相关节点，所以用矩阵表示太过于浪费空间。

同样的，有的图中大部分点都只有小于点总数一半的关联点，用矩阵表示太过浪费空间，那么是否可以模仿树，用链表记录和哪些点相连。

因此引出图中节点关系的两种记录方式：矩阵，链表

1. 图的构造

不要考虑节点关系是怎么记录的，先思考怎么记录点——数组

如果要频繁插入/删除，可以考虑c++容器vector

但除此之外，还要注意存放这些点是为了什么。点的名字是由编号+名字构成的，需要从编号查找名字，也要从名字找编号。前者容易，编号就是下标；后者，很容易能想到字典，map。

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
/*
void createGraph();
    void insertVertex();
    void insertEdge();
    void findEdge();
    void removeEdge();
*/
class graph{
protected:
    int nv;//一共多少个点
    bool ifD;//是否有向
    vector<string>points;//存放点的名字
    map<string,int>points_num;//存放点的编号
public:
    graph(bool D=false){//无参初始化，默认是无向图
        ifD=D;
        nv=0;
    }
    graph(vector<string>v,bool D=false){//重载，用户输入点的名字vector和是否有向，构造
        ifD=D;
        nv=v.size();
        points=v;//string类型可以直接构造
        //不要忘记反过来标记points的编号
        for(int i=0;i<nv;i++){
            points_num[points[i]]=i;
        }
    }
    graph(int n, bool D=false){//重载，用户只要指定有多少个点就可以自动命名，构造
        ifD=D;
        nv=n;
        points.resize(n);
        for(int i=0;i<nv;i++){
            points[i]=to_string(i);
        }
        for(int i=0;i<nv;i++){
            points_num[points[i]]=i;
        }
    }
    void test(){
        for(int i=0;i<nv;i++){
            cout<<points[i];
        }
    }
};
int main(){
    graph g(5);
    g.test();
}

教、学、考、评、管

科大讯飞智慧教育是科大讯飞股份有限公司旗下品牌，于2004年申请注册 [1] ，以“人工智能助力教育，因材施教成就梦想”为理念，围绕“因材施教”提供了覆盖教、学、考、评、管的教育全场景解决方案。 [2]

科大讯飞智慧教育产品已在31个省级行政区及新加坡等海外市场广泛应用，与全国3.5万所学校深度合作，服务超过1亿师生。 [3] 科大讯飞已与教育部考试中心签署战略合作协议，共建联合实验室，服务新高考等值赋分、自动批改、综合评价需求；与北师大等单位联合共建“中国基础教育质量监测协同创新中心”，通过教育大数据构建个体化实时监测和评价体系等。 [4]