西南科技大学SWUST OJ 数据结构 图相关题题解 图.zip

//有向图的最大出度计算 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #include <ctype.h> typedef int InfoType; #define MAXV 100 //最大顶点个数 int DEG[MAXV]; //保存顶点的出度 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 //以下定义邻接表类型 typedef struct ANode //弧的结点结构类型 { int adjvex; //该弧的终点位置 struct ANode *nextarc; //指向下一条弧的指针 InfoType info; //该弧的相关信息,这里用于存放权值 } ArcNode; typedef int Vertex; typedef struct Vnode //邻接表头结点的类型 { Vertex data; //顶点信息 int count; //存放顶点入度,只在拓扑排序中用 ArcNode *firstarc; //指向第一条弧 } VNode; typedef struct { VNode adjlist[MAXV]; //邻接表 int n,e; //图中顶点数n和边数e } ALGraph; //图的邻接表类型 void MatToList(MGraph g,ALGraph *G) //将邻接矩阵g转换成邻接表G { int i,j,n=g.n; //n为顶点数 ArcNode *p; for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值 G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++) //检查邻接矩阵中每个元素 for(j=n-1;j>=0;j--) if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0 { p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后 G->adjlist[i].firstarc=p; } G->n=n;G->e=g.e; } void CalDegree(ALGraph *G) { int i,d,n; ArcNode *p; n=G->n; for (i=0;i<n;i++) { d=0; p=G->adjlist[i].firstarc; while(p!=NULL) { p=p->nextarc; d=d+1; } DEG[i]=d; } } int main() { int n,m; int i,j,row,col; int dmax=0; MGraph g; //邻接矩阵 ALGraph *G; //邻接表 scanf("%d\n", &n); //输入总的结点数 scanf("%d\n", &m); //输入总的边数 g.n=n; for(i=0;i<n;i++) for(j=0;j<n;j++) g.edges[i][j]=0; //矩阵初始化 for (i=0;i<m;i++) //将输入转换为邻接矩阵 { scanf("%d%d",&row,&col); g.edges[row][col]=1; } G=(ALGraph *)malloc(sizeof(ALGraph)); //初始化G MatToList(g,G); CalDegree(G); //计算最大出度 dmax=0; for(i=0;i<n;i++) if(DEG[i]>dmax) dmax=DEG[i]; printf("%d\r\n",dmax); for(i=0;i<n;i++) if(DEG[i]==dmax) printf("%d",i); // printf("\r\n"); return 0; } //***code2 #include<iostream> using namespace std; #include<cstdio> int map[105][105],vis[105]; int m,n,ans,maxx=0,k; int main() { scanf("%d\n",&m); scanf("%d",&n); int a,b,i,j; for(i=0;i<n;i++) { scanf("%d%d",&a,&b); map[a][b]=1; } k=0; for(i=0;i<n;i++) { ans=0; for(j=0;j<n;j++) { if(map[i][j]==1) ans++; } vis[i]=ans; if(ans>=maxx) maxx=ans; } cout<<maxx<<"\r\n"; for(i=0;i<n;i++) if(vis[i]==maxx) cout<<i; return 0; } /******** //有向图的最大出度计算 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> #include <ctype.h> typedef int InfoType; #define MAXV 100 //最大顶点个数 int DEG[MAXV]; //保存顶点的出度 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 //以下定义邻接表类型 typedef struct ANode //弧的结点结构类型 { int adjvex; //该弧的终点位置 struct ANode *nextarc; //指向下一条弧的指针 InfoType info; //该弧的相关信息,这里用于存放权值 } ArcNode; typedef int Vertex; typedef struct Vnode //邻接表头结点的类型 { Vertex data; //顶点信息 int count; //存放顶点入度,只在拓扑排序中用 ArcNode *firstarc; //指向第一条弧 } VNode; typedef struct { VNode adjlist[MAXV]; //邻接表 int n,e; //图中顶点数n和边数e } ALGraph; //图的邻接表类型 void MatToList(MGraph g,ALGraph *G) //将邻接矩阵g转换成邻接表G { int i,j,n=g.n; //n为顶点数 ArcNode *p; for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值 G->adjlist[i].firstarc=NULL; for(i=0;i<n;i++) //检查邻接矩阵中每个元素 for(j=n-1;j>=0;j--) if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0 { p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后 G->adjlist[i].firstarc=p; } G->n=n;G->e=g.e; } void CalDegree(ALGraph *G) { int i,d,n; ArcNode *p; n=G->n; for (i=0;i<n;i++) { d=0; p=G->adjlist[i].firstarc; while(p!=NULL) { p=p->nextarc; d=d+1; } DEG[i]=d; } } int main() { int n; int i,j,index,s,len; char temp[100]; //输入一行字符 int dmax=0; MGraph g; //邻接矩阵 ALGraph *G; //邻接表 scanf("%d", &n); //输入总的结点数 getchar(); getchar(); //读入\r\n g.n=n; for(i=0;i<n;i++) for(j=0;j<n;j++) g.edges[i][j]=0; //矩阵初始化 for (i=0;i<n;i++) //将输入转换为邻接矩阵 { gets(temp); len=strlen(temp); // s=temp[0]-'0'; if(isdigit(temp[0])&&len>0) s=temp[0]-'0'; // else { printf("input error!"); exit(0) ; } for (j=1; j<len; j++) { if (isdigit(temp[j])) //只能输入一位数的整数 { index = temp[j] - '0'; g.edges[s][index] = 1; } } } G=(ALGraph *)malloc(sizeof(ALGraph)); //初始化G MatToList(g,G); CalDegree(G); //计算最大出度 dmax=0; for(i=0;i<n;i++) if(DEG[i]>dmax) dmax=DEG[i]; printf("%d\r\n",dmax); for(i=0;i<n;i++) if(DEG[i]==dmax) printf("%d",i); // printf("\r\n"); return 0; }