c2c电子商务网站定制开发,西安网站设计开发,网络公司网站创建,旅游网站建设 pig1.邻接矩阵的实现
邻接矩阵的定义#xff1a;在无向图和有向图中#xff0c;使用二维数组表示各个顶点的相邻情况#xff1a;1代表相邻#xff0c;0表示不相邻。 代码实现#xff1a;
#define MaxVertexNum 100//顶点数目的最大值
typedef struct {char Vex [MaxVertexN…1.邻接矩阵的实现
邻接矩阵的定义在无向图和有向图中使用二维数组表示各个顶点的相邻情况1代表相邻0表示不相邻。 代码实现
#define MaxVertexNum 100//顶点数目的最大值
typedef struct {char Vex [MaxVertexNum];//顶点表int Edge [MaxVertexNum] [MaxVertexNum] ;//邻接矩阵边表int vexnum, arcnum;//图的当前顶点数和边数/弧数
}MGraph;;注意
顶点中可以存更复杂的信息边可以用bool型或枚举型变量
2.求顶点的度入度出度
1.无向图
第i个结点的度第i行或第i列的非零元素个数。时间复杂度为O(N)
2.有向图
第i个结点的出度第i行的非零元素个数。第i个结点的入度第i列的非零元素个数。第i个结点的度第i行、第i列的非零元素个数之和。
3.邻接矩阵法存储带权图网)
分为有向网和无向网。 同样使用二维矩阵存储无穷代表没有路径可达反之值代表路径的长度。 代码实现
#define MaxVertexNum 100//顶点数目的最大值
#define INFINITY 1000000//最大的int值 宏定义常量无穷
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; // 带权图中边上权值的数据类型
typedef struct {VertexType Vex [MaxVertexNum];//顶点EdgeType Edge[MaxVertexNum][MaxVertexNum]; //边的权int vexnum, arcnum;//图的当前顶点数和弧数
}MGraph;;4.临接矩阵的性能分析
1.空间复杂度
On2:只和顶点数相关和实际的边数无关。
适合用于存储稠密图无向图的邻接矩阵是对称矩阵可以压缩存储只存储上三角区/下三角区)
5.邻接矩阵法的性质
设图G的邻接矩阵为A矩阵元素为0/1 则A的元素A[i][]等于由顶点i到顶点j的长度为n的路径的数目。
