【图论入门】图的存储
1.邻接矩阵
邻接矩阵是图论中用于表示图（Graph）结构的一种重要数据结构，特别适用于表示顶点之间连接关系的图形。在计算机科学和数学领域，它被广泛应用来编码无向图和有向图的信息。
特点：
1、无向图的邻接矩阵是对称的，且主对角线元素全为0(因为自己到自己没有边）
2、顶点i的度=第i行(列)中1的个数。
3、完全图的邻接矩阵中，主对角元素为0，其余全为1.
有向图的邻接矩阵
在图论中，网（Network）是指带有权重的图，其中边或弧可以具有非零的权值，通常代表距离、成本或其他度量。对于这样的带权图，其邻接矩阵的表示会包含每个顶点对之间的权值信息。
网的邻接矩阵 是一个 n×n 的矩阵 A，对于有向网：
- 矩阵中的元素 (A[i][j]) 表示从顶点 i 到顶点 j 的有向边的权值。
- 如果没有从顶点 i 到顶点 j 的边，则 (A[i][j]) 可以被赋值为无穷大（一般用极大整数表示）或者一个特殊值（如
null或-1），表示不存在路径或无法到达。对于无向网：
- 矩阵仍然是对称的，即如果顶点 i 和顶点 j 之间存在一条无向边且带有一个权值 w，那么 (A[i][j] = A[j][i] = w)。
举例来说，假设有一个无向网，其中有三条边连接着三个顶点，并且边的权值分别为：(顶点1, 顶点2) 权重为3，(顶点1, 顶点3) 权重为5，(顶点2, 顶点3) 权重为1，则对应的邻接矩阵可能是：
| 0 3 5 |
| 3 0 1 |
| 5 1 0 |通过邻接矩阵，我们可以直观地看出任意两点间的直接连通性和权值大小，便于进行诸如最短路径计算等图算法的操作。
优缺点：
邻接矩阵表示法的优缺点
优点：
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
- 方便计算任一顶点的“度”。
缺点：
- 不便于增加和删除顶点
- 浪费空间——存稀疏图(点很多而边很少)有大量无效元素
- 对稠密图(特别是完全图)还是很合算的
- 浪费时间——统计稀疏图中一共有多少条边
#include<iostream>
using namespace std;
#define INF 65535 //表示无穷大，其他合理的值也可
#define MaxVerNum 1000 //定义顶点最大数量
typedef int cellType; //定义邻接矩阵元素数据类型，即权值的数据类型
//定义图的类型分别为无向图，无向带权图，有向图，有向带权图
typedef enum{
UDG,UDN,DG,DN
}GraphKind;
class GraphAdjMatrix
{
private:
int VerNum;//顶点数量
int ArcNum;//边数量
GraphKind gKind; //图类型
cellType** AdjMatrix;//邻接矩阵
public:
GraphAdjMatrix();
void createGraph();//构建图
void GraphSet(int VerNum,int ArcNum,int kind);//图属性设置
int getVerNum() {return VerNum;}
int getArcNum() {return ArcNum;}
GraphKind geyGraphKind() {return gKind;};
void setMatrix(int i,int j,int w) ; //邻接矩阵设置
void printMatrix();//打印邻接矩阵
};
GraphAdjMatrix::GraphAdjMatrix()//构造函数
{
AdjMatrix = new cellType*[MaxVerNum];
for(int i=0;i<MaxVerNum;i++)// 为邻接矩阵分配内存
AdjMatrix[i] = new cellType[MaxVerNum];
}
void GraphAdjMatrix::setMatrix(int i,int j,int w)
{
AdjMatrix[i][j]=w;
if(gKind==UDG||gKind==UDN) //如果是无向图，则设置对称位置权重
AdjMatrix[j][i]=w;
};
void GraphAdjMatrix::createGraph()
{
int vn,an,k;//分别代表顶点数量，边数量，以及图类型
cout<<"输入顶点数量,边数量，图类型用空格隔开"<<endl;
cout<<"0-无向无权图 1-无向带权图 2-有向无权图 3-有向带权图"<<endl;
cin>>vn>>an>>k;
VerNum = vn;
ArcNum = an;
gKind = (GraphKind)k;
int i,j,w;
//初始化邻接矩阵
for(int i=1;i<=vn;i++)
{
for(int j=1;j<=vn;j++)
{
AdjMatrix[i][j]=INF;
}
}
/*无向图，无向带权图，有向图，有向带权图 */
GraphKind gk;
while(an--)
{
if (k == UDG || k == DG)//如果是无权图，则将边权重设为1
{
cin>>i>>j;
AdjMatrix[i][j]=1;
if (k==UDG)//如果是无向图，对称位置设置权重
AdjMatrix[j][i]=1;
}
else
{
cin>>i>>j>>w;
AdjMatrix[i][j]=w;
if (k == UDN)//如果是无向图，对称位置设置权重
AdjMatrix[j][i]=w;
}
}
}
void GraphAdjMatrix::printMatrix()
{
for(int i=1;i<=VerNum;i++)
{
for(int j=1;j<=VerNum;j++)
{
if (AdjMatrix[i][j]==INF)
cout<<"*"<<"\t";
else
cout<<AdjMatrix[i][j]<<"\t";
}
cout<<endl;
}
}
int main()
{
GraphAdjMatrix cg;
cg.createGraph();
cg.printMatrix();
return 0;
}2.邻接表
这里简单介绍算法题中常用的建表方式（自己使用的）
在理解邻接表时，先入为主地按照了尾插法去思考，所以总是对不上。实际上最重要的是它使用的是头插法。
因为抽象思考能力很差（没错就是这么菜），这里用一个形象的方式模拟观察一下。
add函数：
void add(int a, int b, int c) // 添加一条边a->b，距离为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
// e = dst, ne = h(from), h(from) = idx
}3.链式前向星（具体注释在代码里）
为了更好的节约空间，使用静态数组模拟邻接表，使得空间效率变高，不造成任何的浪费
下面代码用addedge（）函数存储一条新的边
1.idx 记录边的序号
2、邻接表包括四个数组：e、w、ne、h
e[idx] = b：表示第 idx 条边通向 b 点
w[idx] = c：表示第 idx 条边的权值为 c
ne[idx] = h[a]：表示以a为起点的第 idx 条边的下一条边为 h[a]（-1表示无边）
h[a] = idx++：表示点 a 的上一条边为 idx
其中 h 数组的大小是点数，其他三个数组的大小都是边数。
代码实现：
// 加入有向边 (a, b)，权值为 c
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}访问操作
// 访问从x出发的所有边
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i], z = w[i];
// 找到了一条有向边 (x, y)，权值为z
}4.拓扑排序
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,d[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 邻接表模板
// d 代表每个元素的入度
// top是拓扑排序的序列，cnt代表top中有多少个元素
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool topsort()
{
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列
if(d[i] == 0) q.push(i);
while(q.size())
{
t = q.front();//每次取出队列的首部
top[cnt] = t;//加入到 拓扑序列中
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i])
{
// 遍历 t 点的出边
int j = e[i];
d[j] --;// j 的入度 --
if(d[j] == 0) q.push(j); //如果 j 入度为0，加入队列当中
}
}
return cnt - 1 == n;
}
int main()
{
int a,b;
cin >> n >> m;
memset(h,-1,sizeof h);
while(m--)
{
cin >> a >> b;
add(a,b);
d[b] ++;// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1";
else
{
for(int i = 1;i <= n; ++i)
{
cout << top[i] <<" ";
}
}
return 0;
}