邻接矩阵的算法设计

题目描述

假设图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");
}