一些概念：
- 连通图：在无向图中，若任意两个顶点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;
}
}
