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";elsecout<<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;
}
