一些概念：

• 连通图：在无向图中，若任意两个顶点v与u都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点v与u都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

图的存储结构

• 邻接矩阵（Adjacency Matrix）
  若图中有N个确定的顶点，则用一个N x N的数组来存储点之间的关系（边）。
• 邻接表（Adjacency List）
  代码来自geeksforgeeks owo哇这个stl用的厉害了

// A simple representation of graph using STL
#include<iostream>
#include<vector>
using namespace std;

// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
    for (int v = 0; v < V; ++v)
    {
        cout << "\n Adjacency list of vertex "
            << v << "\n head ";
        for (auto x : adj[v])
            cout << "-> " << x;
        printf("\n");
    }
}

// Driver code
int main()
{
    const int V = 5;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 4);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    printGraph(adj, V);
    return 0;
}

然后是自己写的

/*图的存储邻接矩阵*/
#include<iostream>
#define UNVISTED -1;
using namespace std;
class Edge {
public:
    int start, end;
    int weight;//边的权重
    Edge();
    Edge(int st, int en, int w) :start(st), end(en), weight(w) {};//构造边
    bool operator >(Edge oneEdge);//重载运算符比较边的大小
    bool operator <(Edge oneEdge);
};

bool Edge::operator>(Edge oneEdge) {
    return weight > oneEdge.weight;
}
bool Edge::operator<(Edge oneEdge) {
    return weight < oneEdge.weight;
}
class Graph {
public:
    int vetexNum;//顶点数目
    int edgeNum;//边数目
    int *Mark;//标记某顶点是否被访问过
    Graph(int vNum) {//constructor
        vetexNum = vNum;
        edgeNum = 0;
        Mark = new int[vetexNum];
        for (int i = 0; i < vetexNum; i++) {
            Mark[i] = UNVISTED;
        }
    }
    ~Graph() {
        delete[] Mark;
    }
    virtual Edge FirstEdge(int oneVertex) = 0;
    virtual Edge NextEdge(Edge oneEdge) = 0;
    int VertexNum() { return vetexNum; }
    int EdgesNum() { return edgeNum; }
    bool isEdge(Edge oneEdge) {
        if (oneEdge.weight > 0 && oneEdge.weight < INFINITY&&oneEdge.end >= 0) {
            return true;
        }
        else {
            return false;
        }
    }
    virtual void setEdge(int start, int end, int weight) = 0;
    virtual void deleteEdge(int start, int end) = 0;

};
class AdjGraph:public Graph
{
private:
    int **matrix;//指向领接矩阵的指针
public:
    AdjGraph(int vNum) :Graph(vNum) {
        int i, j;
        matrix = (int**) new int*[vetexNum];
        for (i = 0; i < vetexNum; i++) {
            matrix[i] = new int[vetexNum];
            for (j = 0; j < vetexNum; j++) {//初始化领接矩阵的元素
                matrix[i][j] = 0;
            }
        }
    }
    ~AdjGraph()
    {
        for (int i = 0; i < vetexNum; i++) {
            delete[] matrix[i];//释放每个matrix[i]申请的空间
        }
        delete[] matrix;//释放matrix指针指向的空间
    }
    void showGrapgh() {
        for (int i = 0; i < vetexNum; i++) {
            for (int j = 0; j < vetexNum; j++) {
                cout<<matrix[i][j]<<" ";
            }
            cout << endl;
        }
    }
    Edge FirstEdge(int oneVertex) {//返回顶点oneVertex的第一条边
        Edge tmpEdge;//边tmpEdge作为函数的返回值
        tmpEdge.start = oneVertex;
        for (int i = 0; i < vetexNum; i++) {
            //找和start相连的第一个点
            if (matrix[oneVertex][i] != 0) {
                tmpEdge.end = i;
                tmpEdge.weight = matrix[oneVertex][i];
                break;
            }
        }
        return tmpEdge;
    }
    Edge NextEdge(Edge oneEdge) {
        //返回与边oneEdge有相同起点的下一条边
        Edge tmpEdge;
        tmpEdge.start = oneEdge.start;
        for (int i = oneEdge.end + 1; i < vetexNum; i++) {
            if (matrix[tmpEdge.start][i] != 0) {
                tmpEdge.end = i;
                tmpEdge.weight = matrix[tmpEdge.start][i];
                break;
            }
        }
        return tmpEdge;
    }
    void setEdge(int start, int end, int weight) {//增加一条边
        if (matrix[start][end] == 0) {
            edgeNum++;
            
        }
        matrix[start][end] = weight;
    }
    void deleteEdge(int start, int end) {//删除一条边
        if (matrix[start][end] != 0) {
            edgeNum--;
        }
        matrix[start][end] = 0;
    }
    //图的遍历：BFS & DFS
};
int main()
{
    AdjGraph G(6);
    G.setEdge(0, 1, 2);
    G.setEdge(1, 3, 2);
    G.setEdge(1, 4, 4);
    G.setEdge(1, 2, 1);
    G.setEdge(2, 5, 3);
    G.setEdge(5, 3, 8);
    G.setEdge(4, 3, 5);
    G.showGrapgh();
    return 0;
}

图的遍历

BFS
广度优先搜索（类似树的层序遍历，都是用队列实现的）

代码实现：

DFS
深度优先搜索（类似树的前三种遍历方式，用栈来实现，其实树算一种图吧。。。）

最小生成树（Minimum-Cost Spanning Tree,MST）

概念：对于带权无向图(无向网)，其所有生成树中，边上权值之和最小的称为最小生成树。
最小生成树生成算法的基本原理-MST性质
MST性质：假设G＝(V, E)是一个连通网，U是顶点V的一个非空子集。若(u, v)是满足条件u∈U且v∈V－U的所有边中一条具有最小权值的边，则必存在一棵包含边(u, v)的最小生成树。

---

1.Prim算法
假设G＝(V, E)是连通网，TE是G上最小生成树中边的集合。算法从U＝{u0} (u0∈V)且TE＝{}开始，重复执行下列操作：
1.在所有u∈U且v∈V－U的边(u, v) 中找一条权值最小的边(u', v')并入集合TE中，同时v'并入U，直到V＝U为止。
2.最后，TE中必有n-1条边。T=(V, TE)就是G的一棵最小生成树。

void Prim(AdjGraph &G,int s) {//s为起始点
    int n = G.VertexNum();//图的顶点数
    Edge* reEdge = new Edge[n];
    int index = 0;
    bool* Mst = new bool[n];//当Mst[i]=true时，表示i在最小生成树集合里
    int *nearest;//nearest[i]表示生成树到i的最小距离
    int *neighbor;//neighbor[i]和点i相连的点
    nearest = new int[n];
    neighbor = new int[n];
    for (int i = 0; i < n; i++) {//初始化
        neighbor[i] = s;
        nearest[i] = INT_MAX;
        Mst[i] = false;
    }
    Mst[s] = true;
    for (Edge e = G.FirstEdge(s); G.isEdge(e); e = G.NextEdge(e)) {
        nearest[e.end] = e.weight;
        neighbor[e.end] = s;
    }
    for (int i = 1; i < n; i++) {
        //找到离最小生成树最近的点
        int min = INT_MAX;
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (nearest[j] < min && Mst[j] == false) {
                min = nearest[j];
                v = j;
            }
        }
        if (v >= 0) {//找到了那个点
            //访问v,把v加入mst中
            Mst[v] = true;
            reEdge[index++] = Edge(neighbor[v], v, min);//加入边集合
            for (Edge e = G.FirstEdge(v); G.isEdge(e);e = G.NextEdge(e)) {
                if (Mst[e.end]==false&&nearest[e.end] > e.weight) {
                    nearest[e.end] = e.weight;
                    neighbor[e.end] = v;
                }
            }
        }
    }
    for (int i = 0; i < n-1; i++) {
        reEdge[i].printEdge();
        cout << endl;
    }
}

2.Kruskal算法
和Prim算法一样也是基于贪心准则（？），先选取权重最小的边，然后判断两个顶点是否属于两个不同的连通分量，是就加入该边到最小生成树T，否则选择下一条权重最小的边，重复以上操作，直至T中所有顶点都在一个连通分量中。

---

三个核心操作
1.确定权重最小的边<——实现：按权重组成优先队列（最小堆）/直接从小到大给边排序也行呐
2.判断这条边的两个顶点是否在一个连通分量中<——实现：Union-Find(等价类）
3.不是就合并这两个顶点的连通分量。<——同2.

//Union-Find
class UFSets
{
private:
    int n;//等价类中元素个数
    int* root;//root[i]表示元素i所在等价类的编号
    //int* next;//next[i]标书等价类i后面元素的编号
    int* length;//length表示i所代表的等价类的元素个数
public:
    UFSets(int size) {
        n = size;
        root = new int[size];
        length = new int[size];
        for (int i = 0; i < n; i++) {
            root[i] =i;
            length[i] = 1;
        }
    }
    int Find(int v) { 
        return root[v];
    }//v元素所在分量的编号
    void Union(int v, int u) {
        if (root[v] == root[u])return;
        else if (length[root[v]]>length[root[u]]) {//v分量元素更多，u并入v中
            int rt = root[u];
            length[root[v]] += length[root[u]];//把u联通分量加入v连通分量中
            root[rt] = root[v];//把root[u]的根rt连向v的根
            //u分量里的每个元素root都指向root[v]
            for (int i = 0; i < n;i++) {
                if (root[i] == root[u]) {
                    root[i] = root[v];
                }
            }

        }
        else {
            int rt = root[v];
            length[root[u]] += length[root[v]];//把v联通分量加入u连通分量中
            root[rt] = root[u];//把root[v]的根rt连向u的根
                               //v分量里的每个元素root都指向root[u]
            for (int i = 0; i < n; i++) {
                if (root[i] == root[v]) {
                    root[i] = root[u];
                }
            }
        }
    }
};

//Kruskal算法
bool edgeCmp(Edge e1, Edge e2) {//sort函数第三个参数函数，按权重升序排列边
    return e1 < e2;
}
void Kruskal(AdjGraph &G) {
    int n = G.VertexNum();//顶点数目
    int edgeNum = G.EdgesNum();//边数目
    vector<Edge> sortEdge;//给边排序的边数组
    vector<Edge> reEdge(n - 1);//储存最小生成树的边
    UFSets set(n);//等价类集合
    for (int i = 0; i < n; i++) {
        for (Edge e = G.FirstEdge(i); G.isEdge(e); e = G.NextEdge(e)) {
            if (e.start < e.end) {
                sortEdge.push_back(e);
            }
        }
    }
    sort(sortEdge.begin(), sortEdge.end(), edgeCmp);
    int curnum = 0;//生成树边个数
    int index = 0;//排序边数组下标
    while (curnum < n - 1) {
        Edge e = sortEdge[index++];
        int sr = e.start;
        int end = e.end;
        if (set.Find(sr) != set.Find(end)) {
            set.Union(sr, end);
            reEdge[curnum++] = e;//加入最小生成树数组
        }
    }
    for (int i = 0; i < n - 1; i++) {//打印边
        reEdge[i].printEdge();
        cout << endl;
    }

}