无向图邻接矩阵

#define OK 1
#define ERROR 0
#define    MAX_VERTEX 100
//图的类型枚举
typedef enum{
    DG,//有向图
    UDG,//无向图
    DN,//有向网
    UDN//无向网
    //网是带权的图
}GraphKind;
//设置顶点的数据类型为字符串型，使用时记得分配内存
typedef char * VerTexType;
//设置权值类型为整数类型
typedef int ArcType;
//返回的状态类型
typedef int status;

//数组(邻接矩阵)表示法
#include <stdio.h>
#include <stdlib.h>
#include "GraphModel.h"
#include <String.h>

//图的邻接矩阵存储表示
typedef struct{
    VerTexType verTexs[MAX_VERTEX];//顶点数组
    ArcType arcs[MAX_VERTEX][MAX_VERTEX]; //邻接矩阵
    int verTexCount;//图的顶点数
    int arcCount;//图的边/弧数
    GraphKind kind;//图的类型
}MatrixGraph;

//使用邻接矩阵表示法创建无向图
status CreateUDG(MatrixGraph *G);

//返回某个顶点在顶点集合中的下标(从0开始)，不存在返回-1
int LocateVex(MatrixGraph *G,VerTexType vex);

//
void TestMatrixGraph();

#include "MatrixGraph.h"

/*
无向图的特点：
1.无向图的邻接矩阵是对称的
2.顶点i的度=第i行(列)中1的个数
*/

//使用邻接矩阵表示法创建无向图
status CreateUDG(MatrixGraph *G){
    G->kind=UDG;//设置当前创建图的类型为无向图
    printf("请输入无向图的顶点数：");
    scanf("%d",&G->verTexCount);
    printf("请输入边的数量：");
    scanf("%d",&G->arcCount);
    printf("依次输入顶点信息：\n");
    for(int i=0;i<G->verTexCount;i++){
        G->verTexs[i]=(VerTexType)malloc(sizeof(char)*10);
        printf("顶点%d:",i);
        scanf("%s",G->verTexs[i]);

    }
    //初始化邻接矩阵，所有边的权值设置为0
    for(int i=0;i<G->verTexCount;i++){
        for(int j=0;j<G->verTexCount;j++){
            G->arcs[i][j]=0;
        }
        }
    printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
    for(int i=0;i<G->arcCount;i++){
    VerTexType vex1=(VerTexType)malloc(sizeof(char)*10);
    VerTexType vex2=(VerTexType)malloc(sizeof(char)*10);
    printf("顶点：");
    scanf("%s",vex1);
    printf("邻接点：");
    scanf("%s",vex2);
    //分别获得两个顶点在顶点数组中的坐标
    int x=LocateVex(G,vex1);
    int y=LocateVex(G,vex2);
    if(x==-1||y==-1){
    return ERROR;
    }
    G->arcs[x][y]=1;
    G->arcs[y][x]=G->arcs[x][y];//无向图的邻接矩阵是对称的

    free(vex1);
    free(vex2);

    }
    return OK;

}



//返回某个顶点在顶点集合中的下标(从0开始)，不存在返回-1
int LocateVex(MatrixGraph *G,VerTexType vex){
    int index=0;
    while(index<G->verTexCount){
        if(strcmp(G->verTexs[index],vex)==0){
            break;
        }
        index++;
    }
    return index==G->verTexCount ? -1:index;
}

void TestMatrixGraph(){
    MatrixGraph G;
    //创建无向图
    status status=CreateUDG(&G);
    if(status ==ERROR){
    printf("创建图失败，请检查后重试");
    return;
    }
    printf("打印图的邻接矩阵：\n");
    printf("\t");
    for(int i=0;i<G.verTexCount;i++){
    printf("\t%s",G.verTexs[i]);
    }
    printf("\n");
    for(int i=0;i<G.verTexCount;i++){
        printf("\t%s",G.verTexs[i]);
        for(int j=0;j<G.verTexCount;j++){
        printf("\t%d",G.arcs[i][j]);
    }
        printf("\n");
    }
}

#include "MatrixGraph.h"

int main(){
    TestMatrixGraph();

    return 0;
}