1. #define OK 1
    2. #define ERROR 0
    3. #define    MAX_VERTEX 100
    4. #define VISIT 1
    5. #define UNVISITED 0
    7. //图的类型枚举
    8. typedef enum{
    9.     DG,//有向图
    10.     UDG,//无向图
    11.     DN,//有向网
    12.     UDN//无向网
    13.     //网是带权的图
    14. }GraphKind;
    16. //设置顶点的数据类型为字符串型，使用时记得分配内存
    17. typedef char * VerTexType;
    18. //设置权值类型为整数类型
    19. typedef int ArcType;
    20. //返回的状态类型
    21. typedef int status;
    1. //数组(邻接矩阵)表示法
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4. #include "GraphModel.h"
    5. #include <String.h>
    7. //图的邻接矩阵存储表示
    8. typedef struct{
    9.     VerTexType verTexs[MAX_VERTEX];//顶点数组
    10.     ArcType arcs[MAX_VERTEX][MAX_VERTEX]; //邻接矩阵
    11.     int verTexCount;//图的顶点数
    12.     int arcCount;//图的边/弧数
    13.     GraphKind kind;//图的类型
    14. }MatrixGraph;
    16. //使用邻接矩阵表示法创建无向图
    17. status CreateUDG(MatrixGraph *G);
    19. //返回某个顶点在顶点集合中的下标(从0开始)，不存在返回-1
    20. int LocateVex(MatrixGraph *G,VerTexType vex);
    22. //
    23. void TestMatrixGraph();
    25. //使用邻接矩阵表示法创建有向图
    26. status CreateDG(MatrixGraph *G);
    1. #include "MatrixGraph.h"
    3. /*
    4. 无向图的特点：
    5. 1.无向图的邻接矩阵是对称的
    6. 2.顶点i的度=第i行(列)中1的个数
    7. */
    9. //使用邻接矩阵表示法创建无向图
    10. status CreateUDG(MatrixGraph *G){
    11.     G->kind=UDG;//设置当前创建图的类型为无向图
    12.     printf("请输入无向图的顶点数：");
    13.     scanf("%d",&G->verTexCount);
    14.     printf("请输入边的数量：");
    15.     scanf("%d",&G->arcCount);
    16.     printf("依次输入顶点信息：\n");
    17.     for(int i=0;i<G->verTexCount;i++){
    18.         G->verTexs[i]=(VerTexType)malloc(sizeof(char)*10);
    19.         printf("顶点%d:",i+1);
    20.         scanf("%s",G->verTexs[i]);
    22.     }
    23.     //初始化邻接矩阵，所有边的权值设置为0
    24.     for(int i=0;i<G->verTexCount;i++){
    25.         for(int j=0;j<G->verTexCount;j++){
    26.             G->arcs[i][j]=0;
    27.         }
    28.         }
    29.     printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
    30.     for(int i=0;i<G->arcCount;i++){
    31.     VerTexType vex1=(VerTexType)malloc(sizeof(char)*10);
    32.     VerTexType vex2=(VerTexType)malloc(sizeof(char)*10);
    33.     printf("顶点：");
    34.     scanf("%s",vex1);
    35.     printf("邻接点：");
    36.     scanf("%s",vex2);
    37.     //分别获得两个顶点在顶点数组中的坐标
    38.     int x=LocateVex(G,vex1);
    39.     int y=LocateVex(G,vex2);
    40.     if(x==-1||y==-1){
    41.     return ERROR;
    42.     }
    43.     G->arcs[x][y]=1;
    44.     G->arcs[y][x]=G->arcs[x][y];//无向图的邻接矩阵是对称的
    46.     free(vex1);
    47.     free(vex2);
    49.     }
    50.     return OK;
    52. }
    56. //返回某个顶点在顶点集合中的下标(从0开始)，不存在返回-1
    57. int LocateVex(MatrixGraph *G,VerTexType vex){
    58.     int index=0;
    59.     while(index<G->verTexCount){
    60.         if(strcmp(G->verTexs[index],vex)==0){
    61.             break;
    62.         }
    63.         index++;
    64.     }
    65.     return index==G->verTexCount ? -1:index;
    66. }
    70. void TestMatrixGraph(){
    71.     MatrixGraph G;
    72.     //创建无向图
    73.     //status status=CreateUDG(&G);
    74.     //创建有向图
    75.     status status=CreateDG(&G);
    76.     if(status ==ERROR){
    77.     printf("创建图失败，请检查后重试");
    78.     return;
    79.     }
    80.     printf("打印图的邻接矩阵：\n");
    81.     printf("\t");
    82.     for(int i=0;i<G.verTexCount;i++){
    83.     printf("\t%s",G.verTexs[i]);
    84.     }
    85.     printf("\n");
    86.     for(int i=0;i<G.verTexCount;i++){
    87.         printf("\t%s",G.verTexs[i]);
    88.         for(int j=0;j<G.verTexCount;j++){
    89.         printf("\t%d",G.arcs[i][j]);
    90.     }
    91.         printf("\n");
    92.     }
    93. }
    96. //使用邻接矩阵表示法创建有向图
    97. /*
    98. 有向图特点：
    99. 1. 有向图的邻接矩阵可能是不对称的
    100. 2. 顶点的出度=第i行元素之和
    101. 3. 顶点的入度=第i列元素之和
    102. 4. 顶点的度=第i行元素之和+第i列元素之和
    103. */
    104. status CreateDG(MatrixGraph *G){
    105.     G->kind=DG;//设置当前创建图的类型为有向图
    106.     printf("请输入有向图的顶点数：");
    107.     scanf("%d",&G->verTexCount);
    108.     printf("请输入边的数量：");
    109.     scanf("%d",&G->arcCount);
    110.     printf("依次输入顶点信息：\n");
    111.     for(int i=0;i<G->verTexCount;i++){
    112.         G->verTexs[i]=(VerTexType)malloc(sizeof(char)*10);
    113.         printf("顶点%d:",i+1);
    114.         scanf("%s",G->verTexs[i]);
    116.     }
    117.     //初始化邻接矩阵，所有边的权值设置为0
    118.     for(int i=0;i<G->verTexCount;i++){
    119.         for(int j=0;j<G->verTexCount;j++){
    120.             G->arcs[i][j]=0;
    121.         }
    122.         }
    123.     printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
    124.     for(int i=0;i<G->arcCount;i++){
    125.     VerTexType vex1=(VerTexType)malloc(sizeof(char)*10);
    126.     VerTexType vex2=(VerTexType)malloc(sizeof(char)*10);
    127.     printf("顶点：");
    128.     scanf("%s",vex1);
    129.     printf("邻接点：");
    130.     scanf("%s",vex2);
    131.     //分别获得两个顶点在顶点数组中的坐标
    132.     int x=LocateVex(G,vex1);
    133.     int y=LocateVex(G,vex2);
    134.     if(x==-1||y==-1){
    135.     return ERROR;
    136.     }
    137.     G->arcs[x][y]=1;
    138.     //G->arcs[y][x]=G->arcs[x][y];//有向图的邻接矩阵有可能不对称
    140.     free(vex1);
    141.     free(vex2);
    143.     }
    144.     return OK;
    146. }
    #include "MatrixGraph.h"

int main(){
    TestMatrixGraph();

    return 0;
}