数据结构——有向图和无向图用邻接矩阵储存及代码实现

谁借莪１个温暖的怀抱￠ 2023-06-21 03:58 43阅读 0赞

一般存储图的方式有两种：一是用邻接矩阵表示，二是用邻接链表。  
所谓用邻接矩阵，是用一个二维数组存储，边使用矩阵来构建模型，这使得每一个顶点和其它顶点之间都有边的有无 的 表示的机会。若有边，则他们交点 为1 ，否则为0。当然，如果是一副边有权值的图，交点存储的是他们边的权值。

## 1、无向图的存储： ##

无向图的边的矩阵一定是一个对称矩阵，因为无向图只关心边是否存在，而不关心方向，V0和V1有边，那么V1和V0也有边。

因为这里不研究有圈图，所以主对角线都是0，输入V0和V1边的关系后，就不必输入V1和V0的关系了。

图解如下：  
![这里写图片描述][SouthEast]

代码实现如下：

#include<stdio.h>  
    
    #define  MAX_VERTEX  4  
    
    typedef char DataType;                 //图中元素的目标数据类型   
    
    typedef struct      
    {                    
        DataType vertexArr[MAX_VERTEX];        //顶点元素数组   
    
        int arcArr[MAX_VERTEX][MAX_VERTEX];   //弧矩阵二维数组   
    
    
    }ArrayGraph;  
    
    void ArrayGraph_init(ArrayGraph *pGraph);  
    void ArrayGraph_create(ArrayGraph *pGraph);  
    void ArrayGraph_show(ArrayGraph *pGraph);  
    
    int main()  
    {  
        ArrayGraph g;  
        ArrayGraph_init(&g);  
        ArrayGraph_create(&g);  
        ArrayGraph_show(&g);  
        return 0;  
    }  
    
    //初始化为一个无圈图 ，也就是弧矩阵中，主对角线元素都是0   
    void ArrayGraph_init(ArrayGraph *pGraph)  
    {  
    
        for (int i = 0; i < MAX_VERTEX; i++)  
    
            pGraph->arcArr[i][i] = 0;  
    
    }  
    
    
    void ArrayGraph_create(ArrayGraph *pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组  
        {  
            printf("输入第%d个顶点值\n",i+1);  
    
            scanf(" %c",&(pGraph->vertexArr[i]));   
    
        }  
    
        for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系   
        {  
            for (int i = j+1; i < MAX_VERTEX; ++i)  
            {  
    
                printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[i],pGraph->vertexArr[j]);  
                scanf("%d",&( pGraph->arcArr[j][i]));  
    
                printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);  
                scanf("%d",&( pGraph->arcArr[i][j]));  
            }  
        }  
    }  
    
    
    void ArrayGraph_show(ArrayGraph *pGraph)  
    {  
        printf("\n\n顶点元素如下\n");  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
    
            printf("%-5c", pGraph->vertexArr[i]);  
        }  
        printf("\n\n");  
        puts("弧矩阵如下\n\n");   
        printf("%-2c",' ');  
        for(int i=0;i<MAX_VERTEX;++i)  
          printf("%-5c",pGraph->vertexArr[i]);  
        putchar('\n');    
    
        for (int j = 0; j <MAX_VERTEX; ++j)  
        {  
            printf("%-2c",pGraph->vertexArr[j]);  
            for (int i = 0; i < MAX_VERTEX; ++i)  
            {  
                printf("%-5d",pGraph->arcArr[i][j]);  
    
            }  
            putchar('\n');  
        }  
        putchar('\n');    
    }

## 2、有向图的邻接矩阵存储： ##

使用邻接矩阵呢存储时，有向图和无向图的区别在与 边和弧矩阵的差别。因为弧是有方向的，所以我们 以对角线为界，将矩阵划分为2个区域：

左下区域表示出弧标记区域，坐上区域代表入弧标记区域

如 若代表弧的矩阵为arcArr

arcArr\[V2\]\[V3\] 为1，且在出弧标记区域，则说明 V3<——V2

arcArr\[V3\]\[V2\] 为0，且在入弧标记区域，则说明 V2——>V3  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

#include<stdio.h>  
    
    #define  MAX_VERTEX  4  
    
    typedef char DataType;                 //图中元素的目标数据类型   
    
    typedef struct      
    {                    
        DataType vertexArr[MAX_VERTEX];        //顶点元素数组   
    
        int arcArr[MAX_VERTEX][MAX_VERTEX];   //弧矩阵二维数组   
    
    }ArrayGraph;  
    
    void ArrayGraph_init(ArrayGraph *pGraph);  
    void ArrayGraph_create(ArrayGraph *pGraph);  
    void ArrayGraph_show(ArrayGraph *pGraph);  
    
    
    int main()  
    {  
        ArrayGraph g;  
        ArrayGraph_init(&g);  
        ArrayGraph_create(&g);  
        ArrayGraph_show(&g);  
        return 0;  
    }  
    
    
    //初始化为一个无圈图 ，也就是弧矩阵中，主对角线元素都是0   
    void ArrayGraph_init(ArrayGraph *pGraph)  
    {  
    
        for (int i = 0; i < MAX_VERTEX; i++)  
    
            pGraph->arcArr[i][i] = 0;  
    
    }  
    
    
    void ArrayGraph_create(ArrayGraph *pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组  
        {  
            printf("输入第%d个顶点值\n",i+1);  
    
            scanf(" %c",&(pGraph->vertexArr[i]));   
    
        }  
    
        for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系   
        {  
            for (int i = j+1; i < MAX_VERTEX; ++i)  
            {  
    
                printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[i],pGraph->vertexArr[j]);  
                scanf("%d",&( pGraph->arcArr[j][i]));  
    
                printf("若元素%c有指向%c的弧，则输入1，否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);  
                scanf("%d",&( pGraph->arcArr[i][j]));  
            }  
        }  
    }  
    
    void ArrayGraph_show(ArrayGraph *pGraph)  
    {  
    
    
        printf("\n\n顶点元素如下\n");  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
    
            printf("%-5c", pGraph->vertexArr[i]);  
        }  
        printf("\n\n");  
        puts("弧矩阵如下\n\n");   
        printf("%-2c",' ');  
        for(int i=0;i<MAX_VERTEX;++i)  
          printf("%-5c",pGraph->vertexArr[i]);  
        putchar('\n');    
        for (int j = 0; j <MAX_VERTEX; ++j)  
        {  
            printf("%-2c",pGraph->vertexArr[j]);  
            for (int i = 0; i < MAX_VERTEX; ++i)  
            {  
                printf("%-5d",pGraph->arcArr[i][j]);  
    
            }  
            putchar('\n');  
        }  
        putchar('\n');    
    }

## 3、有权值无向图（无向网）的邻接矩阵存储： ##

无向网的边是有权值的，这个值可以是任何一个合法的值，什么样的值是合法的呢？这需要根据图的具体用途来定。所以，我们不能用简单的0,1来代表边。

如果2个顶点无关联，他们也不能用0表示，因为0也可能是一个合法的wieght值。可有类比一下：如何地球上2个地方之间不可互通，那么他们之间的车程费是不是无穷大呢？

所以，我们来要根据图权值类型定义一个相应类型的最大值，来代表2个顶点之间不关联。

同样用一个例子。

V0 V1之间的权值为12

V0 V2之间的权值为1

V0 V3之间的权值为5

V2 V3之间的权值为7

![这里写图片描述][SouthEast 3]![这里写图片描述][SouthEast 4]  
代码实现如下：

#include<stdio.h>  
    
    
    #define MAX_VERTEX 4       
    
    #define INFINITY  65535  
    
    typedef char DataType;     //存储的元素类型   
    typedef int WeightType;    //权值的类型   
    
    typedef struct  
    {  
        DataType vertexArr[MAX_VERTEX];             //存储顶点的数组   
    
        WeightType edgeArr[MAX_VERTEX][MAX_VERTEX]; //存储边的二维数组   
    
    }UArrayNet;     //数据结构类型：无向网   
    void UArrayNet_init(UArrayNet*pGraph);  
    void UArrayNet_create(UArrayNet*pGraph);  
    void UArrayNet_show(UArrayNet *pGraph);  
    
    int main()  
    {  
        UArrayNet net;  
        UArrayNet_init(&net);  
    
        UArrayNet_create(&net);  
        UArrayNet_show(&net);  
        return 0;  
    }  
    
    void UArrayNet_init(UArrayNet*pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
            pGraph->edgeArr[i][i] = INFINITY;  
        }  
    }  
    
    
    void UArrayNet_create(UArrayNet*pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组  
        {  
            printf("输入第%d个顶点值\n", i + 1);  
    
            scanf(" %c", &(pGraph->vertexArr[i]));  
    
        }  
    
        for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系   
        {  
            for (int i = j + 1; i < MAX_VERTEX; ++i)  
            {  
    
                printf("若元素%c和%c有边，则输入权值，否则输入无效值%d\t", pGraph->vertexArr[j], pGraph->vertexArr[i], INFINITY);  
    
                scanf("%d", &(pGraph->edgeArr[j][i]));  
                pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i];     //对称   
            }  
        }  
    }  
    
    void UArrayNet_show(UArrayNet *pGraph)  
    {  
        printf("\n\n顶点元素如下\n");  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
    
            printf("%-5c", pGraph->vertexArr[i]);  
        }  
        printf("\n\n");  
    
        puts("边矩阵如下");  
        printf("%-2c", ' ');  
        for (int i = 0; i<MAX_VERTEX; ++i)  
            printf("%-5c", pGraph->vertexArr[i]);  
        putchar('\n');  
    
        for (int j = 0; j <MAX_VERTEX; ++j)  
        {  
            printf("%-2c", pGraph->vertexArr[j]);  
            for (int i = 0; i < MAX_VERTEX; ++i)  
            {  
                if(pGraph->edgeArr[i][j]==INFINITY)  
                {  
                    printf("%-5c", '#');  
                }   
                else  
                    printf("%-5d", pGraph->edgeArr[i][j]);  
            }  
            putchar('\n');  
        }  
    }

## 4、有向网邻接矩阵存储 ##

有向网的实现与无向网思路一致，就不重复累赘了，直接上代码吧。

#include<stdio.h>  
    #define MAX_VERTEX 4       
    
    #define INFINITY  65535  
    
    typedef char DataType;     //存储的元素类型   
    typedef int WeightType;    //权值的类型   
    
    typedef struct  
    {  
        DataType vertexArr[MAX_VERTEX];             //存储顶点的数组   
    
        WeightType arcArr[MAX_VERTEX][MAX_VERTEX]; //存储边的二维数组   
    
    }UArrayNet;     //数据结构类型：无向网   
    void UArrayNet_init(UArrayNet*pGraph);  
    void UArrayNet_create(UArrayNet*pGraph);  
    void UArrayNet_show(UArrayNet *pGraph);  
    
    int main()  
    {  
        UArrayNet net;  
        UArrayNet_init(&net);  
    
        UArrayNet_create(&net);  
        UArrayNet_show(&net);  
        return 0;  
    }  
    
    void UArrayNet_init(UArrayNet*pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
            pGraph->arcArr[i][i] = INFINITY;  
        }  
    }  
    
    
    void UArrayNet_create(UArrayNet*pGraph)  
    {  
        for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组  
        {  
            printf("输入第%d个顶点值\n", i + 1);  
    
            scanf(" %c", &(pGraph->vertexArr[i]));  
    
        }  
    
        for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系   
        {  
            for (int i = j + 1; i < MAX_VERTEX; ++i)  
            {  
    
                printf("若元素%c有指向%c有边，则输入权值，否则输入无效值%d\t", pGraph->vertexArr[j], pGraph->vertexArr[i], INFINITY);  
                scanf("%d",&( pGraph->arcArr[j][i]));  
                printf("若元素%c有指向%c有边，则输入权值，否则输入无效值%d\t", pGraph->vertexArr[i], pGraph->vertexArr[j], INFINITY);  
                scanf("%d",&( pGraph->arcArr[i][j]));  
            }  
        }  
    }  
    
    void UArrayNet_show(UArrayNet *pGraph)  
    {  
        printf("\n\n顶点元素如下\n");  
        for (int i = 0; i < MAX_VERTEX; ++i)  
        {  
    
            printf("%-5c", pGraph->vertexArr[i]);  
        }  
        printf("\n\n");  
        puts("边矩阵如下");  
        printf("%-2c", ' ');  
        for (int i = 0; i<MAX_VERTEX; ++i)  
            printf("%-5c", pGraph->vertexArr[i]);  
        putchar('\n');  
    
    
    
        for (int j = 0; j <MAX_VERTEX; ++j)  
        {  
            printf("%-2c", pGraph->vertexArr[j]);  
            for (int i = 0; i < MAX_VERTEX; ++i)  
            {  
                if(pGraph->arcArr[i][j]==INFINITY)  
                {  
                    printf("%-5c", '#');  
    
                }   
                else  
                    printf("%-5d", pGraph->arcArr[i][j]);  
            }  
            putchar('\n');  
        }  
    }

[SouthEast]: https://img-blog.csdn.net/20170914171430461?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdmljZGQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20170914172950955?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdmljZGQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20170914172959730?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdmljZGQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: https://img-blog.csdn.net/20170914171816418?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdmljZGQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20170914171826355?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdmljZGQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast