邻接矩阵存储有向图
AI验证代码逻辑没有错误。
/* 有向图的基本操作包括： 1. 初始化图：创建一个空的图数据结构，并初始化图的顶点数和边数。 2. 创建图 3. 判断图是否为空 4. 添加顶点：向图中添加一个新的顶点。 5. 添加边：在图中添加一条连接两个顶点的边。 6. 删除顶点：从图中删除一个指定的顶点，同时删除与该顶点相关联的边。 7. 删除边：从图中删除一条指定的边。 8. 判断顶点是否存在：检查图中是否存在指定的顶点。 9. 判断边是否存在：检查图中是否存在指定的边。 10. 获取顶点的出度邻居顶点：获取指定顶点指向的顶点集合。 11. 获取顶点的入度邻居顶点：获取指向指定顶点的顶点集合。 12. 获取顶点的入度：计算指定顶点的入度，即与该顶点相连的边的数量。 13. 获取顶点的出度：计算指定顶点的出度，即从该顶点出发的边的数量。 14. 获取顶点的度：计算指定顶点的度，即入度和出度的总和。 15. 打印邻接矩阵 */ #include <stdlib.h> #include <stdio.h> #define MaxVertexNum 20 typedef int VertexType; typedef int EdgeType; typedef struct{ VertexType Vex[MaxVertexNum]; //存储顶点 EdgeType Edge[MaxVertexNum][MaxVertexNum]; //存储边 int VexNum; //顶点数 int EdgeNum; //边数 }Graph; //1.初始化图 void InitGraph(Graph &G) { int i,j; for(i=0;i<MaxVertexNum;i++) { G.Vex[i]=0; //顶点值初始化为0 for(j=0;j<MaxVertexNum;j++) G.Edge[i][j]=0; //邻接矩阵中的元素初始化为0 } G.VexNum=0; //顶点个数初始化为0 G.EdgeNum=0; //边数初始化为0 } //2.创建图 bool CreateGraph(Graph &G) { int MaxNum,i,j; printf("图的顶点个数为:"); scanf("%d",&MaxNum); if(MaxNum<=0) return false; G.VexNum=MaxNum; printf("输入顶点值:\n"); for(i=0;i<G.VexNum;i++) { scanf("%d",&G.Vex[i]); } printf("输入(0/1)到邻接矩阵:\n"); int count=0; for(i=0;i<G.VexNum;i++) { for(j=0;j<G.VexNum;j++) { scanf("%d",&G.Edge[i][j]); if(G.Edge[i][j]==1) count++; } } G.EdgeNum=count/2; } //3.判断图是否为空 bool isValid(Graph G) { //判断是否为空 if(G.VexNum<=0) { printf("图空\n"); return false; } return true; } //4.添加顶点 bool AddVertex(Graph &G,VertexType ver) { if(G.VexNum==MaxVertexNum-1) return false; for(int i=0;i<G.VexNum;i++) if(G.Vex[i]==ver) return false; G.Vex[G.VexNum]=ver; G.VexNum++; for(int i=0;i<G.VexNum;i++) { G.Edge[G.VexNum-1][i]=0; G.Edge[i][G.VexNum-1]=0; } return true; } //5.添加边 bool AddEdge(Graph &G,VertexType ver1,VertexType ver2) { int v1=-1; int v2=-2; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver1) v1=i; if(G.Vex[i]==ver2) v2=i; if(v1>=0 && v2>=0) //提前结束 break; } if(v1<0 || v2<0) return false; G.Edge[v1][v2]=1; G.Edge[v2][v1]=1; G.EdgeNum++; return true; } //6.删除顶点 bool DeleteVertex(Graph &G,VertexType ver) { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v<0) return false; for(int i=v;i<G.VexNum-1;i++) { for(int j=0;j<G.VexNum;j++) { G.Edge[i][j]=G.Edge[i+1][j]; G.Edge[j][i]=G.Edge[j][i+1]; } } for(int i=v;i<G.VexNum-1;i++) G.Vex[i]=G.Vex[i+1]; G.VexNum--; int count=0; for(int i=0;i<G.VexNum;i++) for(int j=0;j<G.VexNum;j++) if(G.Edge[i][j]==1 || G.Edge[j][i]==1) count++; G.EdgeNum=count/2; return true; } //7.删除边(ver1指向ver2的边) bool DeleteEdge(Graph &G,VertexType ver1,VertexType ver2) { int v1=-1; int v2=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver1) v1=i; if(G.Vex[i]==ver2) v2=i; if(v1>=0 && v2>=0) //提前结束 break; } if(v1<0 || v2<0) return false; G.Edge[v1][v2]=0; G.EdgeNum--; return true; } //8.判断顶点是否存在 bool ExistVertex(Graph G,VertexType ver)//传入的是顶点值，不是下标 { for(int i=0;i<G.VexNum;i++) if(G.Vex[i]==ver) return true; return false; } //9.判断边是否存在(ver1指向ver2的边) bool ExistEdge(Graph G,VertexType ver1,VertexType ver2)//传入的是顶点值，不是下标 { int v1,v2; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver1) v1=i; if(G.Vex[i]==ver2) v2=i; if(v1>=0 && v2>=0) //提前结束 break; } if(G.Edge[v1][v2]==0) return false; return true; } //10.获取顶点的出度邻居顶点 bool GetInNeiborVertex(Graph G,VertexType ver) { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v==-1) { printf("顶点不存在\n"); return false; } printf("%d的出度邻居顶点为:",ver]); for(int i=0;i<G.VexNum;i++) { if(G.Edge[v][i]==1) printf("%d ",G.Vex[i]); } return true; } //11.获取顶点的入度邻居顶点 bool GetOutNeiborVertex(Graph G,VertexType ver) { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v==-1) { printf("顶点不存在\n"); return false; } printf("%d的出度邻居顶点为:",ver]); for(int i=0;i<G.VexNum;i++) { if(G.Edge[i][v]==1) printf("%d ",G.Vex[i]); } return true; } //12.求顶点的入度 int GetInDegree(Graph G,VertexType v) //注意传入的是数组的下标 { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v<0) return 0; int degree=0; for(int i=0;i<G.VexNum;i++) { if(G.Edge[v][i]==1) degree++; } return degree; } //13.求顶点的出度 int GetOutDegree(Graph G,VertexType ver) { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v<0) return 0; int degree=0; for(int i=0;i<G.VexNum;i++) { if(G.Edge[i][v]==1) degree++; } return degree; } //14.求顶点的度 int GetDegree(Graph G,VertexType ver) { int v=-1; for(int i=0;i<G.VexNum;i++) { if(G.Vex[i]==ver) { v=i; break; } } if(v<0) return 0; int degree=0; for(int i=0;i<G.VexNum;i++) { if(G.Edge[i][v]==1) degree++; if(G.Edge[v][i]==1) degree++; } return degree; } //15.打印邻接矩阵 void DisplayGraph(Graph G) { int i,j; printf("顶点结点:\n"); for(i=0;i<G.VexNum;i++) { printf("%d ",G.Vex[i]); } printf("\n"); printf("邻接矩阵:\n"); for(i=0;i<G.VexNum;i++) { for(j=0;j<G.VexNum;j++) { printf("%d ",G.Edge[i][j]); if(j==G.VexNum-1) printf("\n"); } } printf("图的边数为:%d\n",G.EdgeNum); } /*int main() { Graph G; InitGraph(G); CreateGraph(G); if(isValid(G)) DisplayGraph(G); printf("顶点1的入度为%d\n",GetInDegree(G,0)); printf("顶点1的出度为%d\n",GetOutDegree(G,0)); printf("顶点1的度为%d\n",GetDegree(G,0)); return 0; } */