数据结构->图的邻接表存储(C语言)

109 阅读 0 评论 72 点赞

我是靠谱客的博主等待世界，最近开发中收集的这篇文章主要介绍数据结构->图的邻接表存储(C语言)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一个无向图G，五个顶点，8条边，用邻接表形式表示该图

那么该如何用C语言来表达呢？

首先看看我们的无向图的头文件ALGraph.h
其中最关键的是边表和顶点表
边表是关联顶点与其他顶点之间的关联
而顶点表是一个数组，保存所有的顶点，每个顶点内保存着顶点编号、权值以及边表头

聪明的你不难看出，这其实类似一个二维数组，只不过最里层的是一个不定长数组

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef ALGRAPH_H_INCLUDED
#define ALGRAPH_H_INCLUDED

#define MAXVERTEXNUM 1000 //最大顶点数

//定义一个顶点类型
typedef unsigned char VertexType;
typedef unsigned char WeightType;

//边表结点
typedef struct EDGENODE
{
    int adjVertex;//边编号
    struct EDGENODE * nextNode;
} EdgeNode;

//顶点表结点
typedef struct VERTEXNODE
{
    VertexType vertex; //顶点值
    WeightType weight;//权值
    EdgeNode * FirstEdge;//第一边结点
} VertexNode;

//顶点表类型
typedef VertexNode AdjList[MAXVERTEXNUM];

//图
typedef struct ALGRAPH
{
    AdjList adjlist;
    int VertexNum;//顶点数
    int EdgeNum;//边数
} ALGraph;

/**
* 函数的定义
*/
//图的初始化
int ALGraph_init(ALGraph ** pg);
//创建图
int Create_ALGraph(ALGraph * g);
//输出图结构
void Output_ALGraph(ALGraph *g);

#endif // ALGRAPH_H_INCLUDED

接下来是源文件ALGraph.c，用于实现创建图等操作，重要地方都有注释，最后遍历邻接表的方法类似二维不定长数组的遍历

#include "ALGraph.h"

//图的初始化
int ALGraph_init(ALGraph ** pg)
{
    *pg = (ALGraph *)malloc(sizeof(ALGraph));
    if(*pg==NULL)//内存分配失败
    {
        return -1;
    }
    memset(*pg,0,sizeof(ALGraph));//内存内容全部填充为0
    return 0;
}

//创建图
int Create_ALGraph(ALGraph * g)
{
    if(g==NULL)
    {
        printf("创建图时发现错误，未完成初始化操作！n");
        return -1;
    }
    printf("请输入顶点数: ");
    scanf("%d",&(g->VertexNum));
    fflush(stdin);

    printf("请输入边数: ");
    scanf("%d",&(g->EdgeNum));
    fflush(stdin);

    if(g->EdgeNum < g->VertexNum - 1) // N个结点至少需要N-1条边
    {
        printf("边数的值不合法！n");
        return -1;
    }

    //*****************************************************************
    printf("开始创建顶点表vertexlistn");
    int n;
    for(n=0; n<g->VertexNum; n++)
    {
        fflush(stdin);
        printf("vertexlist 第%d项是V",n);
        scanf("%d",&(g->adjlist[n].vertex)); //取值范围为0-65535
        g->adjlist[n].weight = 0;
        g->adjlist[n].FirstEdge = NULL;
    }
    printf("创建顶点表完成!n");

    //*****************************************************************
    EdgeNode * p = NULL;
    printf("n开始创建边表edgelistn");
    int i,j;
    for(n=0; n<g->EdgeNum; n++)
    {
        fflush(stdin);
        printf("请输入边（Vi,Vj）的顶点序号：");
        scanf("%d,%d",&i,&j);
        if(i<0 || j<0||i>(g->VertexNum)||j>(g->VertexNum))
        {
            printf("输入的值存在非法，操作失败！n");
            return -1;
        }
        //在g->adjlist[i]处建立与j的关系
        p = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(p==NULL)
        {
            printf("初始化结构体EdgeNode变量p失败");
            return -1;
        }
        p->adjVertex = j;
        p->nextNode = g->adjlist[i].FirstEdge;
        g->adjlist[i].FirstEdge = p;

        //在g->adjlist[j]处建立与i的关系
        p = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(p==NULL)
        {
            printf("初始化结构体EdgeNode变量p失败");
            return -1;
        }
        p->adjVertex = i;
        p->nextNode = g->adjlist[j].FirstEdge;
        g->adjlist[j].FirstEdge = p;
    }
    printf("创建边表完成!n");
    return 0;
}

//输出图结构
void Output_ALGraph(ALGraph *g)
{
   printf("n邻接表输出如下: n");
   EdgeNode  * p;
   int n;
   for(n=0 ; n<g->VertexNum ; n++)
   {
       printf("%d ",g->adjlist[n].vertex);//输出顶点值
        p = g->adjlist[n].FirstEdge;
        while(p!=NULL)
        {
            printf("->");
            printf("%d ",p->adjVertex);
            p = p->nextNode;
        }
        printf("n");
   }
}

我们最重要的main方法

#include "ALGraph.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *arg[])
{
	printf("尝试将一个无向图转为一个邻接表！nn");
	int ret;
	ALGraph *g = NULL;
	ret = ALGraph_init(&g);//初始化邻接表内存区
	if(ret<0)
	{
		perror("初始化图时发现错误：没有完成初始化操作n");
		return -1;
	}

	ret  = Create_ALGraph(g);//创建邻接表
	if(ret<0)
	{
		printf("创建邻接表失败！n");
		return -1;
	}
	Output_ALGraph(g);//输出邻接表

    return 0;
}

最后放上程序运行过程，怎么样，是不是挺简单的呢！其实这个并不单单对这个简单的无向图，你可以去试一下，如果有什么改进意见可以在评论告诉我