邻接矩阵与邻接表的输出及其相互转换-Toy模板网

这篇具有很好参考价值的文章主要介绍了邻接矩阵与邻接表的输出及其相互转换。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

（1) 文件1： pubuse.h 是公共使用的常量定义和系统函数调用声明。

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX 等*/
#include<stdio.h> /* EOF(=^Z 或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码*/
#define TRUE  1
#define FALSE  0
#define OK  1
#define ERROR  0
#define INFEASIBLE  -1
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/
typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */

2)文件GraphDef.h定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在下面的程序中都会使用到，其代码如下：

#define MAXV 100          //最大顶点个数
//以下定义类型
typedef struct
{
    int no;                 //顶点编号
    InfoType info;           //顶点其他信息，这里用于存放边的权值
}VertexType;               //顶点类型
typedef struct                   //图的定义
{
    int edges[MAXV][MAXV];     //邻接矩阵
    int n, e;                       //顶点数、弧数
    VertexType vex[MAXV];        //存放顶点信息
}MGraph;                     //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct  Anode          //弧的结点结构类型
{
    int adjvex;                 //该弧的终点位置
    struct  Anode* nextarc;      //指向下一条弧的指针
    InfoType  info;             //该弧的相关信息，这里用于存放权值
}ArcNode;
typedef  int Vertex;
typedef struct Vnode           //邻接表头结点的类型
{
    Vertex data;                 //顶点信息
    ArcNode* firstarc;           //指向第一条弧
}VNode;
typedef  VNode  AdjList[MAXV];        //AdjList是邻接表类型
typedef struct
{
    AdjList adjlist;              //邻接表
        int n, e;                      //图中顶点数n和边数e
}ALGraph;                      //图的邻接表类型

（3）头文件GraphAlgo4-1.h包含若干图的操作函数

1.将邻接矩阵转化为邻接表

#define INF 32767                    //INF表示
void MatToList(MGraph g, ALGraph *&G)  //将邻接矩阵g转换成邻接表G
{
    int i, j, n = g.n;                           // n为顶点数
    ArcNode* p;
    G = (ALGraph*)malloc(sizeof(ALGraph));
    for (i = 0; i < n; i++)                      //给邻接表中所有头结点的指针域置初值
        G->adjlist[i].firstarc = NULL;
    for (i = 0; i < n; i++)                      //检查邻接矩阵中每个元素
        for (j = n - 1; j >= 0; j--)
            if (g.edges[i][j] != 0)               //邻接矩阵的当前元素不为0
            {
                p = (ArcNode*)malloc(sizeof(ArcNode));  //创建一个结点*p
                p->adjvex = j;
                p->info = g.edges[i][j];                 //存放边的权值    
                p->nextarc = G->adjlist[i].firstarc;        //将*p插入到链表中，头插法
                G->adjlist[i].firstarc = p;
            }
    G->n = g.n;
    G->e = g.e;
}

2.将邻接表转化为邻接矩阵

void ListToMat(ALGraph* G, MGraph& g)       //将邻接表G转换成邻接矩阵g
{
    int i, j, n = G->n;
    ArcNode* p;
    for (i = 0; i < n; i++)                             //g.edges[i][j]赋初值0
        for (j = n - 1; j >= 0; j--)
            g.edges[i][j] = 0;
    for (i = 0; i < n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)                      //对所有相邻顶点进行处理
        {
            g.edges[i][p->adjvex] = p->info;
            p = p->nextarc;
        }
    }
    g.n = n;
    g.e = G->e;
}

3.进行邻接矩阵与邻接表的输出

void DispMat(MGraph g)                       //输出邻接矩阵g
{
    int i, j;
    for (i = 0; i < g.n; i++)
    {
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] == INF)
                printf("%3s:" , "#");
            else
                printf("%3d", g.edges[i][j]);
        printf("\n");
    }
}
void DispAdj(ALGraph* G)                      //输出邻接表G
{
    int  i;
    ArcNode* p;
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        if (p != NULL)
            printf("%3d:", i);
        while (p != NULL)                        //对所有相邻顶点进行处理
        {
            printf("%3d",p->adjvex);//应该输出每个邻接表的顶点数据
            p = p->nextarc;
           
        }
        printf("\n");
    }
}

(3)源程序exp4-1.cpp 实现图的操作函数的测试文件。

#include “pubuse.h”
#include “GraphDef.h”
#include “GraphAlgo.h”
void main()
{
    int i, j;
    MGraph g,g1;
    ALGraph* G;
    printf("建立一个有向图：\n");      //自己设计一个有向图 
    printf("输入有向图的顶点数：");
    scanf_s("%d", &g.n);
    printf("建立 %d * %d的矩阵：\n", g.n, g.n);
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
        {
            printf("输入顶点 % d到顶点 % d的权值, 无弧的用0表示:\n",i,j);
            scanf_s("%d", &g.edges[i][j]);     //用矩阵存储两顶点弧上的权值

        }
    g.e = 0;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != 0)
                g.e++;
    printf("有向图G的邻接矩阵:\n");
    DispMat(g);
    G = (ALGraph*)malloc(sizeof(ALGraph));
    printf("图的邻接矩阵转换成邻接表:\n");
    MatToList(g, G);
    DispAdj(G);
    printf("图G的邻接表转换成邻接矩阵:\n");
    ListToMat(G, g1);
    DispMat(g1);
    printf("\n");
}

运行代码如下所示：

邻接矩阵与邻接表的输出及其相互转换文章来源地址https://www.toymoban.com/news/detail-505931.html