算法基础：图

目录

图的概念

定义

与其他数据结构的区别

分类

无向图

有向图

有环图和无环图

图的经典代码结构与算法

---

图的概念

定义

图(Graph)：是由顶点的有穷非空集合和顶点之间边的集合组成。

顶点(Vertex)：图中的数据元素。

边(Edge)：顶点之间的逻辑关系,表示为(ⅵ,vj)。

弧(Arc)：即有向边,表示为。

上述是百度对于图的定义，但是实际上图作为日常生活中最常见的结构，在程序设计中，任何一种数据结构其实都可以使用图的方式去理解。

与其他数据结构的区别

1. 线性表和树可以看做特殊的图。
2. 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点（Vertex）
3. 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点（有穷非空性）
4. 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示（边集可以为空）。

分类

无向图

顾名思义，无向图就是图上的边没有方向。上图就是一个无向图。该图的顶点集为 V = { 1 , 2 , 3 , 4 , 5 , 6 } ，边集 E = { ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 4 , 6 ) }。在无向图中，边 ( u , v )和边 ( v , u )是一样的，也就是说和方向无关。

无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有n个顶点的无向完全图有n(n-1)/2 条边。

连通图（无向图）

在无向图G中，如果从顶点u到顶点v有路径，则称u和v是连通的。

如果对于图中任意两个顶点u、v，都有(u, v)∈E（即u和v都是连通的），则称G是连通图。

无向图中的极大连通子图称为连通分量。

连通分量需要满足：

• 必须是子图；
• 必须是连通的；
• 含有极大顶点数；
• 包含依附于这些顶点的所有边。

上图中，图1是无向非连通图（因为A与E不连通，即不满足图上任意两个顶点连通），但是有两个连通分量，即图2和图3。而图4，尽管是图1的子图，但是它却不满足连通子图的极大顶点数(图2满足)。 因此它不是图1的无向图的连通分量。

这里，补充一个概念。

关节点(割点)：某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使图或者分支失去连通性，则称该顶点为关节点。如下图中的 顶点c 。

无向图的度

对于无向图G= (V, E)， 如果边(v,v’)属于E， 则称顶点v和v‘互为邻接点，即(v,v’)与顶点v和v’相关联。顶点v的度是和v相关联的边的数目。如下面这个无向图，顶点A 的度为3。各个顶点度的和=3+2+3+2=10。而此图的边数是5，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。

有向图

顾名思义，有向图就是图上的边有方向。

上图就是一个有向图。该图的顶点集为 V = { A , B , C , D } ，边集 E = { < B , A > , < B , C > , < C , A > , < A , D > }。在有向图中，边 < u , v >和边 < v , u >是不一样的。

通常情况下，有向图中的边用< >表示，无向图中的边用( )表示。

有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条边，则称该图为有向完全图。n个顶点的有向完全图含有n*(n-1)条边。

强连通图（有向图）

在有向图G中，如果对于每一对顶点vi、vj且vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
有向图中的极大强连通子图称做有向图的强连通分量。
强连通图具有如下定理：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

有向图的度

对于有向图G = (V, E)，如果边属于E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v的边和顶点v， v’相关联。

从顶点v出发的边的数目称为v的出度；到达顶点v的边的数目称为v的入度，顶点v的度=出度+入度。以下面这个有向图为例，

顶点A的入度是2 （从B到A的边，从C到A的边），出度是1（从A到D的边），所以顶点A的度为2+1=3。此有向图的边有4 条，而各顶点的出度和为1+2+1+0=4，各顶点的入度和=2+0+1+1=4。

有环图和无环图

路径(path)

依次遍历顶点序列之间的边所形成的轨迹。注意，依次就意味着有序，先1后2和先2后1不一样。

简单路径

没有重复顶点的路径称为简单路径。说白了，这一条路径中没有出现绕了一圈回到同一顶点的情况。

环

包含相同的顶点两次或者两次以上。例如，下图中路径 < 1 , 2 , 4 , 3 , 1 >，其中1出现了两次，那么这条路径就是一个环路。

有环图就是图上有环，无环图就是没有环的图。
特别地，有向无环图有，又叫做DAG(Directed Acyline Graph)，具有一些很好的性质，很多动态规划的问题都可以转化成DAG中的最长路径、最短路径或者路径计数的问题。

加权图和无权图

首先需要了解一下什么是权。有些图的边上具有与它相关的数字，这种与图的边相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。因此加权图就是边上带有权重的图，与其对应的是无权图，或叫等权图，即边上没有权重信息。如果一张图不含权重信息，我们就认为边与边之间没有差别。

通常情况下，加权图会被称为网络。

图的经典数据结构与算法

对于图相关的算法来说，搭建起图的数据结构就基本代表算法成功了一半。

#include 
#include 
#include 
#include 

using namespace std;
class Node;
class Edge {
public:
    shared_ptr from_;
    shared_ptr to_;
    int weight_;
    Edge(shared_ptr from,shared_ptr to,int weight):from_(from),to_(to),weight_(weight){}
    Edge(){}
};

class Node{
private:
    char value_;
    int in_;
    int out_;
    vector> edges_;
    vector> nexts_;
public:
    char getValue(){return value_;}
    int getIn(){return in_;}
    void setIn(int in) {in_ = in;}

    int getOut(){return out_;}
    void setOut(int out){out_ = out;}

    void addEdge(shared_ptr edge) {edges_.emplace_back(edge);}
    void removeEdge(shared_ptr edge) {
        for(auto iter = edges_.begin();iter!=edges_.end();iter++){
            if((*iter)->to_->getValue() == edge->to_->getValue() && (*iter)->from_->getValue() == edge->from_->getValue() && (*iter)->weight_ == edge->weight_) {
                edges_.erase(iter);
            }
        }
    
    }
   
    Node(){}
    Node(char value, int in, int out, vector> edges, vector> nexts):value_(value),in_(in),out_(out),edges_(edges),nexts_(nexts){}
    Node(char value):value_(value){}
    void addNext(shared_ptr next,int weight){
        for(auto a:nexts_) {
            if(a->getValue() == next->getValue()){
                return;
            }
        }
        out_++;
        next->setIn(next->getIn()+1);
        nexts_.emplace_back(next);
        addEdge(make_shared(make_shared(*this),next,weight));
    }

    void removeNext(shared_ptr next,int weight) {
        out_--;
        next->setIn(next->getIn()-1);
        removeEdge(make_shared(make_shared(*this),next,weight));
    }
};
shared_ptr findNode(char value,vector> nodes){
    for(auto a:nodes) {
        if(a->getValue() == value){
            return a;
        }
    }
    return nullptr;
}
vector>  make_graph(vector> graph_raw) {
    vector> graph;
    for(auto a: graph_raw) {
         shared_ptr node = findNode(a.first,graph);
         if(node == nullptr) {
             vector> e;
             vector> n;
             node = make_shared(a.first,0,1,e,n);
         }
         shared_ptr next = findNode(a.second,graph);
         if(next == nullptr) {
                vector> e;
                vector> n;
                next = make_shared(a.second,1,0,e,n);
         } 
        node->addNext(next,0);
        graph.emplace_back(node);

    }
    return graph;
}

int main()
{
    vector> graph_raw{{'a','b'},{'a','c'},{'a','d'},{'b','d'},{'d','c'}};
    vector> graph = make_graph(graph_raw);
    
    return 0;
}