图 - 《C语言数据结构》

1.无向图邻接矩阵
2.有向图的邻接矩阵
3.无向图的邻接表

1.无向图邻接矩阵

无向图的特点：

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

GraphModel.h

#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;

MatrixGraph.h

//数组(邻接矩阵)表示法
#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();

MatrixGraph.cpp

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

main.cpp

#include "MatrixGraph.h"

int main(){
    TestMatrixGraph();

    return 0;
}

2.有向图的邻接矩阵

特点：

有向图的邻接矩阵可能是不对称的
顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
顶点的度=第i行元素之和+第i列元素之和

注：第i行含义：以结点Vi为尾的弧(即出度边)
第i列含义：以结点Vi为尾的弧(即入度边)
GraphModel.h

#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;

MatrixGraph.h

//数组(邻接矩阵)表示法
#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 CreateDG(MatrixGraph *G);

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

//
void TestMatrixGraph();

MatrixGraph.cpp

#include "MatrixGraph.h"

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

//使用邻接矩阵表示法创建有向图
status CreateDG(MatrixGraph *G){
    G->kind=DG;//设置当前创建图的类型为有向图
    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=CreateDG(&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");
    }
}

main.cpp

#include "MatrixGraph.h"

int main(){
    TestMatrixGraph();

    return 0;
}

2021.11.24 21:35

3.无向图的邻接表

GraphModel.h

#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;

AdjListGraph.h

//图的邻接表表示法
#include "GraphModel.h"
#include <stdlib.h>
#include <stdio.h>


//边/弧的顶点、弧/边的结点结构
typedef struct node{
    int adjVex;//该边指向这条边邻接点的下标
    struct node *nextEdge;//指向下一条边结点的指针
    struct node *nextArc;//指向下一个弧结点的指针
    ArcType weight;//权重
}EdgeNode,ArcNode;

//顶点的结点结构
typedef struct vexNode{
    VerTexType vex;               //顶点的取值
    EdgeNode *firstEdge;          //指向第一条边的指针
    ArcNode *firstArc;            //指向第一条弧的指针
}VNode,AdjList[MAX_VERTEX];       //AdjList表示邻接表类型

//邻接表实现的图结构
typedef struct adjGraph{
    AdjList vexes;                 //顶点数组
    int VexCount;                  //顶点数量
    int degeCount;                 //图的边数
    int arcCount;                  //图的弧数
    GraphKind kind;                //图的类型

    /*
    union{
    int degeCount;                 //图的边数
    int arcCount;                  //图的弧数
    }
    */
}AdjListGraph;

//采用邻接表表示法创建无向图
status CreateUDG_AdjList(AdjListGraph *G); 

//返回顶点vex在顶点数组中的下标，没有找到就返回-1
int LocateVex_AdjList(AdjListGraph *G,VerTexType vex);

//测试函数
void TestAdjGraph();

AdjListGraph.cpp

#include "AdjListGraph.h"
#include <string.h>


//采用邻接表表示法创建无向图
status CreateUDG_AdjList(AdjListGraph *G){
    G->kind=UDG;
    printf("请输入顶点数量：");
    scanf("%d",&G->VexCount);
    printf("请输入边的数量：");
    scanf("%d",&G->degeCount);
    printf("请依次输入顶点信息：\n");
    for(int i=0;i<G->VexCount;i++){
        G->vexes[i].vex=(VerTexType)malloc(sizeof(char) *10);
        printf("顶点%d:",i+1);
        scanf("%s",G->vexes[i].vex);
        //初始化邻接表，把边置空
        G->vexes[i].firstEdge=NULL;    
    }
    printf("请输入顶点和邻接点信息，构建邻接表\n");
    for(int i=0;i<G->degeCount;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_AdjList(G,vex1);
        int y=LocateVex_AdjList(G,vex2);
        if(x==-1||y==-1){
            free(vex1);
            free(vex2);
            return ERROR;
        }


        EdgeNode *edgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        edgeNode->adjVex=x;
        edgeNode->nextEdge=G->vexes[y].firstEdge;
        edgeNode->weight=0;
        G->vexes[y].firstEdge=edgeNode;

        edgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        edgeNode->adjVex=y;
        edgeNode->nextEdge=G->vexes[x].firstEdge;
        edgeNode->weight=0;
        G->vexes[x].firstEdge=edgeNode;

        free(vex1);
        free(vex2);
    }
    return OK;
}

//测试函数
void TestAdjGraph(){
    AdjListGraph G;
    status status=CreateUDG_AdjList(&G);
    for(int i=0;i<G.VexCount;i++){
    VNode vNode=G.vexes[i];
    printf("顶点：%s",vNode.vex);
    EdgeNode * eNode=vNode.firstEdge;
    while(eNode){
        printf("->%d",eNode->adjVex);
        eNode=eNode->nextEdge;
    }
    printf("\n");
    }
}

//返回顶点vex在顶点数组中的下标，没有找到就返回-1
int LocateVex_AdjList(AdjListGraph *G,VerTexType vex){
int index=-1;
for(int i=0;i<G->VexCount;i++){
    if(strcmp(vex,G->vexes[i].vex)==0){
    index=i;
    break;
    }
}
    return index;
}

main.cpp

#include "AdjListGraph.h"

int main(){
    TestAdjGraph();
    return 0;
}

2021.11.25