欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

邻接矩阵无向图

程序员文章站 2023-12-23 19:22:58
...

邻接矩阵

邻接矩阵无向图 
无向图和有向图在邻接矩阵中的表示方法: 
邻接矩阵无向图

无向图和有向图大同小异,在这里只以无向图为例,代码部分通过简单调整即可对应编译有向图

邻接矩阵数据类型定义

#define MaxVertices 100 //定义最大容量
typedef struct{ //包含权的邻接矩阵的的定义
    int Vertices[MaxVertices];  //顶点信息的数组
    int Edge[MaxVertices][MaxVertices]; //边信息的数组
    int numV; //顶点数
    int numE; //边数
}AdjMatrix;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

以如关系图为例 
邻接矩阵无向图 
根据上图,我们可以写出对应的邻接矩阵: 
邻接矩阵无向图 
通过这个图可以看出,无向图对角线划分出来的两部分是互相对称的,由此即可通过创建无向图的邻接矩阵:

void CreateGraph(AdjMatrix *G) //图的生成函数
{ 
    int n,e,vi,vj,w,i,j;
    printf("请输入图的顶点数和边数(以空格分隔):");
    scanf("%d%d",&n,&e);
    G->numV=n;G->numE=e;
    for(i=0;i<n;i++) //图的初始化
        for(j=0;j<n;j++)
            { 
            if(i==j)
                G->Edge[i][j]=0;
            else 
                G->Edge[i][j]=32767;
            }
    for(i=0;i<n;i++)
        for(i=0;i<G->numV;i++) //将顶点存入数组中
        { 
        printf("请输入第%d个顶点的信息:",i+1);
        scanf("%d",&G->Vertices[i]);
        }
    printf("\n");

    for(i=0;i<G->numE;i++)
    { 
        printf("请输入边的信息i,j,w(以空格分隔):");
        scanf("%d%d%d",&vi,&vj,&w); 
        //若为不带权值的图,则w输入1
        //若为带权值的图,则w输入对应权值

        G->Edge[vi-1][vj-1]=w;//①
        G->Edge[vj-1][vi-1]=w;//②
        //无向图具有对称性的规律,通过①②实现
        //有向图不具备此性质,所以只需要①
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

创建完无向图对应的邻接矩阵,我们需要对输出的格式进行一下控制,使其尽量按照普通手写的方式输出

void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{ 
    int i,j;
    printf("\n输出顶点的信息(整型):\n");
    for(i=0;i<G.numV;i++)
        printf("%8d",G.Vertices[i]);

    printf("\n输出邻接矩阵:\n");
    printf("\t");
    for(i=0;i<G.numV;i++)
        printf("%8d",G.Vertices[i]);

    for(i=0;i<G.numV;i++)
    { 
        printf("\n%8d",i+1);
        for(j=0;j<G.numV;j++)
        { 
        if(G.Edge[i][j]==32767) //两点之间无连接时权值为默认的32767,但输出时为了方便输出 "∞"
            printf("%8s", "∞");
        else
            printf("%8d",G.Edge[i][j]);
        }
        printf("\n");   
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

完整程序如下:

#include<stdio.h>
#include<stdlib.h>
#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767,但输出时用 "∞"
typedef struct{ //包含权的邻接矩阵的的定义
    int Vertices[MaxVertices];  //顶点信息的数组
    int Edge[MaxVertices][MaxVertices]; //边的权信息的数组
    int numV; //当前的顶点数
    int numE; //当前的边数
}AdjMatrix;

void CreateGraph(AdjMatrix *G) //图的生成函数
{ 
    int n,e,vi,vj,w,i,j;
    printf("请输入图的顶点数和边数(以空格分隔):");
    scanf("%d%d",&n,&e);
    G->numV=n;G->numE=e;
    for(i=0;i<n;i++) //图的初始化
        for(j=0;j<n;j++)
            { 
            if(i==j)
                G->Edge[i][j]=0;
            else 
                G->Edge[i][j]=32767;
            }
    for(i=0;i<n;i++)
        for(i=0;i<G->numV;i++) //将顶点存入数组中
        { 
        printf("请输入第%d个顶点的信息(整型):",i+1);
        scanf("%d",&G->Vertices[i]);
        }
    printf("\n");

    for(i=0;i<G->numE;i++)
    { 
        printf("请输入边的信息i,j,w(以空格分隔):");
        scanf("%d%d%d",&vi,&vj,&w); 
        //若为不带权值的图,则w输入1
        //若为带权值的图,则w输入对应权值

        G->Edge[vi-1][vj-1]=w;//①
        G->Edge[vj-1][vi-1]=w;//②
        //无向图具有对称性的规律,通过①②实现
        //有向图不具备此性质,所以只需要①
    }
}
void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{ 
    int i,j;
    printf("\n输出顶点的信息(整型):\n");
    for(i=0;i<G.numV;i++)
        printf("%8d",G.Vertices[i]);

    printf("\n输出邻接矩阵:\n");
    printf("\t");
    for(i=0;i<G.numV;i++)
        printf("%8d",G.Vertices[i]);

    for(i=0;i<G.numV;i++)
    { 
        printf("\n%8d",i+1);
        for(j=0;j<G.numV;j++)
        { 
        if(G.Edge[i][j]==32767) 
        //两点之间无连接时权值为默认的32767,
        在无向图中一般用"0"表示,在有向图中一般用"∞",
        这里为了方便统一输出 "∞"
            printf("%8s", "∞");
        else
            printf("%8d",G.Edge[i][j]);
        }
        printf("\n");   
    }
}
int main()
{ 
    AdjMatrix G;
    CreateGraph(&G);
    DispGraph(G);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

运行结果如下: 

邻接矩阵无向图


http://blog.csdn.net/qq_39630587/article/details/77374857



上一篇:

下一篇: