如何将邻接矩阵算法设计转化为长尾词？
- 内容介绍
- 文章标签
- 相关推荐
本文共计973个文字，预计阅读时间需要4分钟。
题目描述：采用邻接矩阵存储图，分别设计实现以下算法：
1. 输出每个顶点的入度
2.输出每个顶点的出度
3.求出度最大的一个顶点，输出其编号
4.计算图中出度为0的顶点数
结果输出：每个算法的结果分别输出，不超过100字。
题目描述
假设图G采用邻接矩阵存储，分别设计实现以下要求的算法：
1.输出每个顶点的入度
2.输出每个顶点的出度
3.求出度最大的一个顶点，输出其编号
4.计算图中出度为0的顶点数
5.判断图中是否有边<i,j>
解决思路
1.入度是邻接矩阵中第i列的元素之和
在函数InDegree（）中，我们需要设置一个循环来遍历所有的结点，计算出每个结点的入度，并输出结果。在输出每个顶点的入度时，应该输出顶点的编号，而不是顶点的名称。在主函数中，调用InGegree()函数时，传入的也是顶点的编号，而不是顶点的名称。
2.求每个顶点的出度和求入度类似，求出度和行有关，求入度和列有关。
3.4.5我用的都是标志大法~~~~~
代码实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"my.h"
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char InfoType;
typedef char VertexType [10];
typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind Kind;
}MGraph;
int LocateVex(MGraph G,VertexType v)
{
int i;
for(i=0;i<G.arcnum;i++)
if(!strcmp(G.vexs[i],v))
return i;
return -1;
}
Status CreateUDN(MGraph *G)
{
int i,j,k;
char v1[20],v2[20];
printf("请输入顶点和弧的个数：");
scanf("%d%d",&G->vexnum,&G->arcnum);
for(i=0;i<G->vexnum;i++)
scanf("%s",G->vexs[i]);
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
G->arcs[i][j].adj=0;
G->arcs[i][j].info=NULL;
}
printf("请输入边依附的顶点：\n");
for(k=0;k<G->arcnum;k++)
{
scanf("%s%s",&v1,&v2);
i=LocateVex(*G,v1);
j=LocateVex(*G,v2);
G->arcs[i][j].adj=G->arcs[j][i].adj=1;
}
}
void InDegree(MGraph G)
{
int i;
int j;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[j][i].adj==1)
count++;
}
printf("%s的入度为%d\n",G.vexs[i],count);
}
}
void OutDegree(MGraph G)
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
count++;
}
printf("%s的出度为%d\n",G.vexs[i],count);
}
}
void MaxOutDegree(MGraph G)
{
int i,j;
int max=-1;
int *p;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
count++;
}
if(count > max)
{
max = count;
*p= i+1;
}
}
printf("出度最大的顶点编号为：%d\n", *p);
}
void zerooutDegree(MGraph G)
{
int i,j,count=0;
for(i=0;i<G.vexnum;i++)
{
int flag=1;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
{
flag=0;
break;
}
}
if(flag)
count++;
}
printf("出度为0的顶点数为%d\n",count);
}
void hasEdge(MGraph G)
{
int i, j;
int flag = 0; // 标记是否找到边
printf("请输入要查询的边<i,j>:");
scanf("%d%d", &i, &j);
if (i <= 0 || i > G.vexnum || j <= 0 || j > G.vexnum) {
printf("输入的顶点编号不合法！\n");
return;
}
if (G.arcs[i-1][j-1].adj== 1) {
printf("存在边<v%d,v%d>。\n", i, j);
flag = 1;
}
if (!flag) {
printf("不存在边<v%d,v%d>。\n", i, j);
}
}
int main()
{
MGraph G;
int i,j;
CreateUDN(&G);
printf("建立的邻接矩阵为：\n");
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%3d",G.arcs[i][j].adj);
printf("\n");
}
InDegree(G);
printf("\n");
OutDegree(G);
printf("\n");
MaxOutDegree(G);
printf("\n");
zerooutDegree(G);
printf("\n");
hasEdge(G);
printf("\n");
}
本文共计973个文字，预计阅读时间需要4分钟。
题目描述：采用邻接矩阵存储图，分别设计实现以下算法：
1. 输出每个顶点的入度
2.输出每个顶点的出度
3.求出度最大的一个顶点，输出其编号
4.计算图中出度为0的顶点数
结果输出：每个算法的结果分别输出，不超过100字。
题目描述
假设图G采用邻接矩阵存储，分别设计实现以下要求的算法：
1.输出每个顶点的入度
2.输出每个顶点的出度
3.求出度最大的一个顶点，输出其编号
4.计算图中出度为0的顶点数
5.判断图中是否有边<i,j>
解决思路
1.入度是邻接矩阵中第i列的元素之和
在函数InDegree（）中，我们需要设置一个循环来遍历所有的结点，计算出每个结点的入度，并输出结果。在输出每个顶点的入度时，应该输出顶点的编号，而不是顶点的名称。在主函数中，调用InGegree()函数时，传入的也是顶点的编号，而不是顶点的名称。
2.求每个顶点的出度和求入度类似，求出度和行有关，求入度和列有关。
3.4.5我用的都是标志大法~~~~~
代码实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"my.h"
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char InfoType;
typedef char VertexType [10];
typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind Kind;
}MGraph;
int LocateVex(MGraph G,VertexType v)
{
int i;
for(i=0;i<G.arcnum;i++)
if(!strcmp(G.vexs[i],v))
return i;
return -1;
}
Status CreateUDN(MGraph *G)
{
int i,j,k;
char v1[20],v2[20];
printf("请输入顶点和弧的个数：");
scanf("%d%d",&G->vexnum,&G->arcnum);
for(i=0;i<G->vexnum;i++)
scanf("%s",G->vexs[i]);
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
G->arcs[i][j].adj=0;
G->arcs[i][j].info=NULL;
}
printf("请输入边依附的顶点：\n");
for(k=0;k<G->arcnum;k++)
{
scanf("%s%s",&v1,&v2);
i=LocateVex(*G,v1);
j=LocateVex(*G,v2);
G->arcs[i][j].adj=G->arcs[j][i].adj=1;
}
}
void InDegree(MGraph G)
{
int i;
int j;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[j][i].adj==1)
count++;
}
printf("%s的入度为%d\n",G.vexs[i],count);
}
}
void OutDegree(MGraph G)
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
count++;
}
printf("%s的出度为%d\n",G.vexs[i],count);
}
}
void MaxOutDegree(MGraph G)
{
int i,j;
int max=-1;
int *p;
for(i=0;i<G.vexnum;i++)
{
int count=0;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
count++;
}
if(count > max)
{
max = count;
*p= i+1;
}
}
printf("出度最大的顶点编号为：%d\n", *p);
}
void zerooutDegree(MGraph G)
{
int i,j,count=0;
for(i=0;i<G.vexnum;i++)
{
int flag=1;
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==1)
{
flag=0;
break;
}
}
if(flag)
count++;
}
printf("出度为0的顶点数为%d\n",count);
}
void hasEdge(MGraph G)
{
int i, j;
int flag = 0; // 标记是否找到边
printf("请输入要查询的边<i,j>:");
scanf("%d%d", &i, &j);
if (i <= 0 || i > G.vexnum || j <= 0 || j > G.vexnum) {
printf("输入的顶点编号不合法！\n");
return;
}
if (G.arcs[i-1][j-1].adj== 1) {
printf("存在边<v%d,v%d>。\n", i, j);
flag = 1;
}
if (!flag) {
printf("不存在边<v%d,v%d>。\n", i, j);
}
}
int main()
{
MGraph G;
int i,j;
CreateUDN(&G);
printf("建立的邻接矩阵为：\n");
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%3d",G.arcs[i][j].adj);
printf("\n");
}
InDegree(G);
printf("\n");
OutDegree(G);
printf("\n");
MaxOutDegree(G);
printf("\n");
zerooutDegree(G);
printf("\n");
hasEdge(G);
printf("\n");
}