邻接矩阵实现图的存储
目录
一. 前言
二. 用邻接矩阵来实现图的存储
一. 前言
1. 图的定义
所谓图就是包含顶点和边的集合，是一种多对多的关系。用符号表示为：G=(V,E)。其中，V代表顶点（数据元素）的有穷非空集合，E代表边的有穷集合。也就是说一个图可以没有边，但顶点不能没有。
2. 有向图和无向图
顶点之间靠一个带有方向的弧连接的图就叫有向图，无向图则相反，边并没有方向。
3. 完全图
任意两个点都有一条边相连的图。如下所示：
4.稀疏图和稠密图
稀疏图就是有很少边或弧的图。而稠密图则是有较多边和弧的图。
5. 权和网
图中边或弧所具有的相关数称为权。表明从一个顶点到另外一个顶点的距离或耗费。而网就是边或者弧带权的图，也就分为无向网和有向网。
6.连通图（强连通图）
在无（有）向图G中，若对任何两个顶点v,u都存在从v到u的路径，则称G是连通图（强连通图）。
7. 连通分量（强连通分量）
无向图（有向图）的极大连通子图称为G的连通分量（强连通分量）。其中，极大连通子图的含义为：该子图是G连通子图，但如果将G的任何不在该子图中的顶点加入，那么这个子图将不再连通，我们就称这样的连通子图为极大连通子图。
8. 极小连通子图
该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。
9. 邻接矩阵
所谓邻接矩阵，拿无向图来举例，就如下所示：
因为v1和v2是相连的，并且这是一个无向图，并没有权值。所以就在v1行v2列的数字为1。邻接矩阵中为0的地方，就代表那两个顶点并没有直接相连。
如果是无向网（表示有权值的图），就不是在相连的地方赋值1了，而是赋值这两个顶点所连边的权值。如下所示：
二. 用邻接矩阵来实现图的存储
我们上面知道了这个存储结构的原理之后，就可以考虑用代码来实现了。用邻接矩阵来创建一个无向图的代码如下所示：
#include<iostream>
using namespace std;#define MAXnum 100//邻接矩阵的结构类型定义
typedef struct{char vexs[MAXnum]; //定义一个数组存放顶点，作为顶点表int arcs[MAXnum][MAXnum]; //邻接矩阵int vexnum,arcnum; //图当前的顶点数和边数
}AMGraph; //Adjacency Matrix Graphint LocateGraph(AMGraph G,char c);int Create(AMGraph &G){cout<<"请输入总的顶点数和边数（中间用空格隔开）:"; cin>>G.vexnum>>G.arcnum; //先输入总的顶点数和边数for(int i=0;i<G.vexnum;i++){ //依次输入顶点信息，有几个顶点就输入几个cout<<"请输入顶点信息（顶点名称）:";cin>>G.vexs[i];}//接着给所有的边的权值赋一个最大值for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=65536;}}//开始录入边的信息for(int i=0;i<G.arcnum;i++){char v1; //用这两个变量来接收两个顶点的值char v2;int w; //接收权值cout<<"请输入其中一条边两边的顶点和权值:";cin>>v1>>v2>>w;int n=LocateGraph(G,v1); //通过这个函数来获取这两个顶点在顶点表中的序号int m=LocateGraph(G,v2);G.arcs[n][m]=w; //给邻接矩阵重新赋值G.arcs[m][n]=w;}
return 1;
}int LocateGraph(AMGraph G,char c){for(int i=0;i<G.vexnum;i++){if(G.vexs[i]==c) return i;}return -1;
}int main(){AMGraph G;Create(G); //这里我们在创建好了我们想要的邻接矩阵之后就可以进行相关操作cout<<G.vexs[1]; //比如我这里进行一个小测试，让它输出我们的第二个顶点名称，看是否是我们所创建的邻接矩阵
}这里我们举了如何用邻接矩阵来实现无向网，我们要是想要用邻接矩阵来创建无向图的话，首先就得初始化邻接矩阵的权值都为0，如果有相连的再赋值为1。只需要在上面代码的基础上修改这部分的内容就行。如下所示为修改之后的部分代码（其他代码一样）：
for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=0}
}G.arcs[n][m]=1;
G.arcs[n][m]=1;下面我们继续看看用邻接矩阵来实现有向图跟有向网，因为无向图的邻接矩阵是对称的，所以上面的代码就得出现这样的代码：
G.arcs[n][m]=w;
G.arcs[m][n]=w;
但在我们有向图中就不再需要这样了，只需要上面一行代码就行了。也就是G.arcs[n][m]=w;就够了。并且跟上面无向图一样，相连顶点的边权值为1。