数据结构之图

一、浅谈
图的内容非常的多，包括各种概念和算法。想要一次性全部拿下是非常难的，尤其是里面的算法，比如最小生成树算法这些，就很像KMP算法，属于一时懂，但后来就很容易忘光的算法。关于图内容的总结，需要较长时间，所以，这篇博文会动态更新。

二、图的种类
把图的全部分类总结如下：
有向图：顶点间的连线是有方向的
无向图：顶点间的连线是无向的
完全图：任意两顶点间都存在连线（有向时则需要来回两条，无向时则只需一条）
连通图：任意两顶点间都存在通路
强连通图：任意两顶点间都存在直接的通路
弱连通图：任意两顶点间都存在通路，但是不一定是直接的通路
AOV网：有向无环图(DAG)中，用顶点表示活动，用有向边表示活动之间的先后顺序的网络（拓扑排序）
AOE网：在AOV网的边上加上权值表示完成该活动所需时间的网络

三、图的操作
(1) 建立、插入和删除
建立一个图，需要记录顶点和边。记录顶点的方式，可以是顺序存储(数组)和链式存储(链表)。
边的记录方式，就比较多了。第一种，可以是直接用邻接矩阵，即表征两个点直接是否有边存在。
第二种，可以用邻接表，就是用一个存链表的数组，数组存的是每个顶点连接的顶点组成的链表的头节点，
第三种，可以用十字链表法，比较复杂，总之就是可以同时表示入度和出度的改进邻接表。

//链表
struct ListNode {
    int val;
    ListNode* next;
    ListNode* tail;
    ListNode():val(0),next(nullptr), tail(nullptr) {}
    ListNode(int n) :val(n), next(nullptr), tail(this) {}
};
//图
struct Gragh {
    //顶点---顺序存储
    vector<int>points;
    //边---邻接表法
    vector<ListNode*>edges;
    //构造
    Gragh(vector<vector<int>>connects) {
        for (int i = 0; i < connects.size(); ++i) {
            points.push_back(connects[i][0]);
            ListNode* cur = new ListNode(connects[i][0]);
            while (i < connects.size() - 1 && connects[i].size()>1&&connects[i][0] == connects[i+1][0]) {
                cur->tail->next = new ListNode(connects[i][1]);
                cur->tail = cur->tail->next;
                ++i;
            }
            if (i < connects.size() - 1 && connects[i].size()>1) {
                cur->tail->next = new ListNode(connects[i][1]);
                cur->tail = cur->tail->next;
            }
            edges.push_back(cur);
        }
    }
    //插入
    void insert(vector<int>connect) {
        int i = 0;
        for (i; i < points.size(); ++i) {
            if (points[i] == connect[0]) {
                edges[i]->tail->next = new ListNode(connect[1]);
                edges[i]->tail = edges[i]->tail->next;
                break;
            }
        }
        if (i == points.size()) {
            points.push_back(connect[0]);
            ListNode* cur = new ListNode(connect[0]);
            if (connect.size() > 1) {
                cur->tail->next = new ListNode(connect[1]);
                cur->tail = cur->tail->next;    
            }
            edges.push_back(cur);
        }
    }
    //删除
    void deletes(int num) {
        for (int i = 0; i < points.size(); ++i) {
            if (points[i] == num) {
                points.erase(points.begin() + i);
                edges.erase(edges.begin() + i);
                break;
            }
        }
        for (int i = 0; i < edges.size(); ++i) {
            ListNode* cur = edges[i];
            while (cur->next) {
                if (cur->next->val == num) {
                    ListNode* tmp = cur->next;
                    cur->next = tmp->next;
                    delete tmp;
                }
                cur = cur->next;
            }
        }
    }
    //显示
    void show() {
        for (int i = 0; i < points.size(); ++i) {
            cout << points[i] << ":  ";
            if (edges[i]) {
                ListNode* tmp = edges[i]->next;
                while (tmp) {
                    cout << tmp->val;
                    if (tmp->next)    cout << " -> ";
                    tmp = tmp->next;
                }
            }
            cout << endl;
        }
    }
    //获取顶点数
    int getpoints() {
        return points.size();
    }
};

(2) 遍历
遍历分为两种，一种是DFS遍历，一种是BFS遍历
DFS遍历就是“见异思迁，遇到新的顶点就跑到新的顶点”---表现为类似树的前序遍历
BFS遍历就是“一心一意，把该顶点所有信息遍历完再进入下一个”---表现为类似树的层序遍历

数据结构之图

全站热榜