邻接矩阵存储无向图

simpleset / 2023-08-29 / 原文

没有使用矩阵的压缩存储

#include <stdlib.h>
#include <stdio.h>

#define MaxVertexNum 20

typedef struct{
    int Vex[MaxVertexNum];                    //存储顶点 
    int Edge[MaxVertexNum][MaxVertexNum];    //存储边 
    int VexNum;                                //顶点个数 
}Graph;

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 
}

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");
    for(i=0;i<G.VexNum;i++)
    {
        for(j=0;j<G.VexNum;j++)
            scanf("%d",&G.Edge[i][j]);
    }
}

bool isValid(Graph G)
{
    //判断是否为空 
    if(G.VexNum<=0)
    {
        printf("图空\n");
        return false;
    }
    
    //判断对角线元素是否非0 
    for(int i=0;i<G.VexNum;i++)
    {
        if(G.Edge[i][i]!=0)
        {
            printf("对角线元素非0\n");
            return false;
        }
    }
    
    //判断矩阵是否对称 
    for(int i=0;i<G.VexNum;i++)
    {
        for(int j=0;j<G.VexNum;j++)
        {
            if(G.Edge[i][j]!=G.Edge[j][i])
            {
                printf("矩阵不对称\n");
                return false;
            }
        }
    }
    return true;
}

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

int main()
{
    Graph G;
    InitGraph(G);
    CreateGraph(G);
    if(isValid(G)) 
        DisplayGraph(G);
    return 0;
}