devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《数据结构》-图的邻接表表示法(四)

作者：盐析白兔 | 2024-07-24 09:58:18

赞

踩

《数据结构》-图的邻接表表示法(四)

邻接表表示法(链式)

存储定义：

  • 顶点：按编号顺序将顶点数据存储在一维数组中
  • 关联同一顶点的边(以顶点为尾的弧)：用线性链表存储

无向图的邻接表

例如，如下无向图

请添加图片描述

则它的邻接表为

请添加图片描述

无向图邻接表的特点：

  • 邻接表不唯一
  • 若无向图中有 n 个顶点，e 条边，则其邻接表需要 n 个头结点和 2e 个表节点，适宜存稀疏图。
  • 无向图中顶点 Vi 的度为第 i 个单链表中的节点数。
  • 存储空间 n + 2e

有向图的邻接表

如下有向图

请添加图片描述
则它的邻接矩阵为

请添加图片描述

它的逆邻接矩阵为

请添加图片描述
有向图邻接表的特点：

  • 顶点 Vi 的出度为第 i 个单链表中结点个数
  • 顶点 Vi 的入度为整个单链表中邻接点域值是 i - 1 的节点个数
  • 找出度易，找入度难

有向图逆邻接表的特点：

  • 顶点 Vi 的入度为第 i 个单链表中结点个数
  • 顶点 Vi 的出度为整个单链表中邻接点域值是 i - 1 的节点个数
  • 找入度易，找出度难

邻接表的特点

  • 方便找任一顶点的所有邻接点
  • 节约稀疏图的空间
    • 需要 N 个头指针 + 2E 个结点(每个结点至少2个域)
  • 计算任一顶点的度
    • 无向图：方便
    • 有向图：只能计算 出度；需要构造 逆邻接表 来方便计算 入度
  • 不方便检查任意一对顶点间是否存在边

邻接矩阵和邻接表的关系

联系：

  • 邻接表中每个链表对应邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数

区别：

  • 对于任意确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)

  • 邻接矩阵的空间复杂度为O(n²)，而邻接表的空间复杂度为 O(n+e)

用途：

  • 邻接矩阵多用于稠密图；而邻接表多用于稀疏图。

邻接表的存储方式


typedef int InfoType;              // 网的权值类型
typedef char VertexType[MAX_NAME]; // 顶点类型为字符串

enum GraphKind
{
    DG,
    DN,
    UDG,
    UDN
}; // {有向图,有向网,无向图,无向网}

struct ElemType
{
    int adjvex;     // 该弧所指向的顶点的位置
    InfoType *info; // 网的权值指针
};

struct ArcNode
{
    struct ElemType data;    // 除指针以外的部分都属于ElemType
    struct ArcNode *nextarc; // 指向下一条弧的指针
};                           // 表结点
typedef struct
{
    VertexType data;              // 顶点信息
    struct ArcNode *firstarc;     // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM]; // 头结点

struct ALGraph
{
    AdjList vertices;
    int vexnum, arcnum;  // 图的当前顶点数和弧数
    enum GraphKind kind; // 图的种类标志
};


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

邻接表的代码实现

main.c

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-08.03     tyustli      first version
 */

#include "graph.h"

void visit(VertexType i)
{
    printf("%s ", i);
}

int main(int argc, char *argv[])
{
    int i, j, k, n;
    struct ALGraph g;
    VertexType v1, v2;
    printf("请顺序选择有向图,有向网,无向图,无向网\n");

    printf("this is graph\r\n");

    CreateGraphF(&g);
    Display(g);
    DFSTraverse(g, visit);
    BFSTraverse(g, visit);

    return 1;
}
/*
编译：make
运行：./obj
结果：
请顺序选择有向图,有向网,无向图,无向网
this is graph
请输入数据文件名(f7-1.txt或f7-2.txt)：graph.txt
请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 2
无向图
8个顶点：
a b c d e f g h
14条弧(边):
a→h a→g a→f a→e a→c a→b
b→h b→e b→d
c→h c→g
d→h
e→f
f→g


a h d b e f g c
a h g f e c b d
*/
/************************ end of file **************************/


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54

makefile

objects  = main.o graph.o
obj: $(objects)
	cc -o obj $(objects) -lm

main.o : graph.h
graph.o : graph.h

.PHONY : clean
clean :
	-rm obj $(objects)


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

graph.h

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-08.03     tyustli      first version
 */

#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()

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;  // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

#define MAX_VERTEX_NUM 20
#define MAX_NAME 3 // 顶点字符串的最大长度+1

typedef int InfoType;              // 网的权值类型
typedef char VertexType[MAX_NAME]; // 顶点类型为字符串

enum GraphKind
{
    DG,
    DN,
    UDG,
    UDN
}; // {有向图,有向网,无向图,无向网}

struct ElemType
{
    int adjvex;     // 该弧所指向的顶点的位置
    InfoType *info; // 网的权值指针
};

struct ArcNode
{
    struct ElemType data;    // 除指针以外的部分都属于ElemType
    struct ArcNode *nextarc; // 指向下一条弧的指针
};                           // 表结点
typedef struct
{
    VertexType data;              // 顶点信息
    struct ArcNode *firstarc;     // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM]; // 头结点

struct ALGraph
{
    AdjList vertices;
    int vexnum, arcnum;  // 图的当前顶点数和弧数
    enum GraphKind kind; // 图的种类标志
};

#define LNode struct ArcNode      // 定义单链表的结点类型是图的表结点的类型
#define next nextarc              // 定义单链表结点的指针域是表结点指向下一条弧的指针域
typedef struct ArcNode *LinkList; // 定义指向单链表结点的指针是指向图的表结点的指针

void CreateGraph(struct ALGraph *G);
void CreateGraphF(struct ALGraph *G);
void Display(struct ALGraph G);
void DFSTraverse(struct ALGraph G, void (*Visit)(char *));
void BFSTraverse(struct ALGraph G, void (*Visit)(char *));

/************************ end of file **************************/


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73

graph.c

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-08.03     tyustli      first version
 */

#include "graph.h"

#if 1
// 不带头结点的单链表的部分基本操作 邻接表中会用到链表的插入等操作
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的
void InitList(LinkList *L)
{
    *L = NULL; // 指针为空
}
void ClearList(LinkList *L)
{ // 初始条件：线性表L已存在。操作结果：将L重置为空表
    LinkList p;
    while (*L) // L不空
    {
        p = *L;          // p指向首元结点
        *L = (*L)->next; // L指向第2个结点(新首元结点)
        free(p);         // 释放首元结点
    }
}
Status ListEmpty(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
    if (L)
        return FALSE;
    else
        return TRUE;
}
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
    int i = 0;
    LinkList p = L;
    while (p) // p指向结点(没到表尾)
    {
        p = p->next; // p指向下一个结点
        i++;
    }
    return i;
}
Status GetElem(LinkList L, int i, struct ElemType *e)
{
    int j = 1;
    LinkList p = L;
    if (i < 1) // i值不合法
        return ERROR;
    while (j < i && p) // 没到第i个元素，也没到表尾
    {
        j++;
        p = p->next;
    }
    if (j == i) // 存在第i个元素
    {
        *e = p->data;
        return OK;
    }
    else
        return ERROR;
}
int LocateElem(LinkList L, struct ElemType e, Status (*compare)(struct ElemType, struct ElemType))
{
    int i = 0;
    LinkList p = L;
    while (p)
    {
        i++;
        if (compare(p->data, e)) // 找到这样的数据元素
            return i;
        p = p->next;
    }
    return 0;
}

Status ListInsert(LinkList *L, int i, struct ElemType e)
{ // 在不带头结点的单链线性表L中第i个位置之前插入元素e
    int j = 1;
    LinkList p = *L, s;
    if (i < 1) // i值不合法
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
    s->data = e;                         // 给s的data域赋值
    if (i == 1)                          // 插在表头
    {
        s->next = *L;
        *L = s; // 改变L
    }
    else
    {                          // 插在表的其余处
        while (p && j < i - 1) // 寻找第i-1个结点
        {
            p = p->next;
            j++;
        }
        if (!p) // i大于表长+1
            return ERROR;
        s->next = p->next;
        p->next = s;
    }
    return OK;
}
Status ListDelete(LinkList *L, int i, struct ElemType *e)
{ // 在不带头结点的单链线性表L中，删除第i个元素，并由e返回其值
    int j = 1;
    LinkList p = *L, q;
    if (i == 1) // 删除第1个结点
    {
        *L = p->next; // L由第2个结点开始
        *e = p->data;
        free(p); // 删除并释放第1个结点
    }
    else
    {
        while (p->next && j < i - 1) // 寻找第i个结点，并令p指向其前趋
        {
            p = p->next;
            j++;
        }
        if (!p->next || j > i - 1) // 删除位置不合理
            return ERROR;
        q = p->next; // 删除并释放结点
        p->next = q->next;
        *e = q->data;
        free(q);
    }
    return OK;
}

LinkList Point(LinkList L, struct ElemType e, Status (*equal)(struct ElemType, struct ElemType), LinkList *p)
{ // 查找表L中满足条件的结点。如找到，返回指向该结点的指针，p指向该结点的前驱(若该结点是
    // 首元结点，则p=NULL)。如表L中无满足条件的结点，则返回NULL，p无定义。
    // 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR
    int i, j;
    i = LocateElem(L, e, equal);
    if (i) // 找到
    {
        if (i == 1) // 是首元结点
        {
            *p = NULL;
            return L;
        }
        *p = L;
        for (j = 2; j < i; j++)
            *p = (*p)->next;
        return (*p)->next;
    }
    return NULL; // 没找到
}

Status DeleteElem(LinkList *L, struct ElemType *e, Status (*equal)(struct ElemType, struct ElemType))
{ // 删除表L中满足条件的结点，并返回TRUE；如无此结点，则返回FALSE。
    // 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR
    LinkList p, q;
    q = Point(*L, *e, equal, &p);
    if (q) // 找到此结点，且q指向该结点
    {
        if (p)                    // 该结点不是首元结点，p指向其前驱
            ListDelete(&p, 2, e); // 将p作为头指针,删除第2个结点
        else                      // 该结点是首元结点
            ListDelete(L, 1, e);
        return TRUE;
    }
    return FALSE;
}

void ListTraverse(LinkList L, void (*vi)(struct ElemType))
{ // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()
    LinkList p = L;
    while (p)
    {
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}
#endif

// 图的邻接表存储的基本操作

// 初始条件：图 G 存在，u 和 G 中顶点有相同特征
// 操作结果：若 G 中存在顶点 u，则返回该顶点在图中位置；否则返回 -1
int LocateVex(struct ALGraph G, VertexType u)
{
    int i;
    for (i = 0; i < G.vexnum; ++i)
        if (strcmp(u, G.vertices[i].data) == 0)
            return i;
    return -1;
}

// 采用邻接表存储结构，构造没有相关信息图或网G(用一个函数构造4种图)

void CreateGraph(struct ALGraph *G)
{                      // 采用邻接表存储结构，构造没有相关信息图或网G(用一个函数构造4种图)
    int i, j, k, w;    // w是权值
    VertexType va, vb; // 连接边或弧的2顶点
    struct ElemType e;
    printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
    scanf("%d", (int *)&G->kind);
    printf("请输入图的顶点数,边数: ");
    scanf("%d,%d", &G->vexnum, &G->arcnum);
    printf("请输入%d个顶点的值(<%d个字符):\n", G->vexnum, MAX_NAME);
    for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
    {
        scanf("%s", G->vertices[i].data);
        G->vertices[i].firstarc = NULL; // 初始化与该顶点有关的出弧链表
    }
    if (G->kind % 2) // 网
        printf("请输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
    else // 图
        printf("请输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
    for (k = 0; k < G->arcnum; ++k) // 构造相关弧链表
    {
        if (G->kind % 2) // 网
            scanf("%d%s%s", &w, va, vb);
        else // 图
            scanf("%s%s", va, vb);
        i = LocateVex(*G, va); // 弧尾
        j = LocateVex(*G, vb); // 弧头
        e.info = NULL;         // 给待插表结点e赋值，图无权
        e.adjvex = j;          // 弧头
        if (G->kind % 2)       // 网
        {
            e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
            *(e.info) = w;
        }
        ListInsert(&G->vertices[i].firstarc, 1, e); // 插在第i个元素(出弧)的表头，在bo2-8.cpp中
        if (G->kind >= 2)                           // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头
        {
            e.adjvex = i;                               // e.info不变，不必再赋值
            ListInsert(&G->vertices[j].firstarc, 1, e); // 插在第j个元素的表头，在bo2-8.cpp中
        }
    }
}

// 采用邻接表存储结构，由文件构造没有相关信息图或网G(用一个函数构造4种图)
void CreateGraphF(struct ALGraph *G)
{
    int i, j, k, w;    // w是权值
    VertexType va, vb; // 连接边或弧的2顶点
    struct ElemType e;
    char filename[13];
    FILE *graphlist;
    printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");
    scanf("%s", filename);
    printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
    scanf("%d", (int *)&G->kind);
    graphlist = fopen(filename, "r"); // 以读的方式打开数据文件，并以graphlist表示
    fscanf(graphlist, "%d", &G->vexnum);
    fscanf(graphlist, "%d", &G->arcnum);
    for (i = 0; i < G->vexnum; ++i) // 构造顶点向量
    {
        fscanf(graphlist, "%s", G->vertices[i].data);
        G->vertices[i].firstarc = NULL; // 初始化与该顶点有关的出弧链表
    }
    for (k = 0; k < G->arcnum; ++k) // 构造相关弧链表
    {
        if (G->kind % 2) // 网
            fscanf(graphlist, "%d%s%s", &w, va, vb);
        else // 图
            fscanf(graphlist, "%s%s", va, vb);
        i = LocateVex(*G, va); // 弧尾
        j = LocateVex(*G, vb); // 弧头
        e.info = NULL;         // 给待插表结点e赋值，图无权
        e.adjvex = j;          // 弧头
        if (G->kind % 2)       // 网
        {
            e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
            *(e.info) = w;
        }
        ListInsert(&G->vertices[i].firstarc, 1, e); // 插在第i个元素(出弧)的表头，在bo2-8.cpp中
        if (G->kind >= 2)                           // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头
        {
            e.adjvex = i;                               // e.info不变，不必再赋值
            ListInsert(&G->vertices[j].firstarc, 1, e); // 插在第j个元素的表头，在bo2-8.cpp中
        }
    }
    fclose(graphlist); // 关闭数据文件
}

void DestroyGraph(struct ALGraph *G)
{ // 初始条件：图G存在。操作结果：销毁图G
    int i;
    struct ElemType e;
    for (i = 0; i < G->vexnum; ++i)         // 对于所有顶点
        if (G->kind % 2)                    // 网
            while (G->vertices[i].firstarc) // 对应的弧或边链表不空
            {
                ListDelete(&G->vertices[i].firstarc, 1, &e); // 删除链表的第1个结点，并将值赋给e
                if (e.adjvex > i)                            // 顶点序号>i(保证动态生成的权值空间只释放1次)
                    free(e.info);
            }
        else                                       // 图
            DestroyList(&G->vertices[i].firstarc); // 销毁弧或边链表，在bo2-8.cpp中
    G->vexnum = 0;                                 // 顶点数为0
    G->arcnum = 0;                                 // 边或弧数为0
}

// 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值
VertexType *GetVex(struct ALGraph G, int v)
{
    if (v >= G.vexnum || v < 0)
        exit(ERROR);
    return G.vertices[v].data;
}

// 初始条件：图G存在，v是G中某个顶点。操作结果：对v赋新值value
Status PutVex(struct ALGraph *G, VertexType v, VertexType value)
{
    int i;
    i = LocateVex(*G, v);
    if (i > -1) // v是G的顶点
    {
        strcpy(G->vertices[i].data, value);
        return OK;
    }
    return ERROR;
}

// 初始条件：图G存在，v是G中某个顶点
// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
int FirstAdjVex(struct ALGraph G, VertexType v)
{
    struct ArcNode *p;
    int v1;
    v1 = LocateVex(G, v); // v1为顶点v在图G中的序号
    p = G.vertices[v1].firstarc;
    if (p)
        return p->data.adjvex;
    else
        return -1;
}

// DeleteArc()、DeleteVex()和NextAdjVex()要调用的函数
Status equalvex(struct ElemType a, struct ElemType b)
{
    if (a.adjvex == b.adjvex)
        return OK;
    else
        return ERROR;
}

// 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1
int NextAdjVex(struct ALGraph G, VertexType v, VertexType w)
{
    LinkList p, p1; // p1在Point()中用作辅助指针，Point()在func2-1.cpp中
    struct ElemType e;
    int v1;
    v1 = LocateVex(G, v);                                 // v1为顶点v在图G中的序号
    e.adjvex = LocateVex(G, w);                           // e.adjvex为顶点w在图G中的序号
    p = Point(G.vertices[v1].firstarc, e, equalvex, &p1); // p指向顶点v的链表中邻接顶点为w的结点
    if (!p || !p->next)                                   // 没找到w或w是最后一个邻接点
        return -1;
    else                             // p->data.adjvex==w
        return p->next->data.adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号
}

// 初始条件：图G存在，v和图中顶点有相同特征
// 操作结果：在图G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做)
void InsertVex(struct ALGraph *G, VertexType v)
{
    strcpy(G->vertices[G->vexnum].data, v); // 构造新顶点向量
    G->vertices[G->vexnum].firstarc = NULL;
    G->vexnum++; // 图G的顶点数加1
}

// 初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧
Status DeleteVex(struct ALGraph *G, VertexType v)
{
    int i, j, k;
    struct ElemType e;
    LinkList p, p1;
    j = LocateVex(*G, v); // j是顶点v的序号
    if (j < 0)            // v不是图G的顶点
        return ERROR;
    i = ListLength(G->vertices[j].firstarc); // 以v为出度的弧或边数，在bo2-8.cpp中
    G->arcnum -= i;                          // 边或弧数-i
    if (G->kind % 2)                         // 网
        while (G->vertices[j].firstarc)      // 对应的弧或边链表不空
        {
            ListDelete(&G->vertices[j].firstarc, 1, &e); // 删除链表的第1个结点，并将值赋给e
            free(e.info);                                // 释放动态生成的权值空间
        }
    else                                       // 图
        DestroyList(&G->vertices[j].firstarc); // 销毁弧或边链表，在bo2-8.cpp中
    G->vexnum--;                               // 顶点数减1
    for (i = j; i < G->vexnum; i++)            // 顶点v后面的顶点前移
        G->vertices[i] = G->vertices[i + 1];
    for (i = 0; i < G->vexnum; i++) // 删除以v为入度的弧或边且必要时修改表结点的顶点位置值
    {
        e.adjvex = j;
        p = Point(G->vertices[i].firstarc, e, equalvex, &p1); // Point()在func2-1.cpp中
        if (p)                                                // 顶点i的邻接表上有v为入度的结点
        {
            if (p1)                                // p1指向p所指结点的前驱
                p1->next = p->next;                // 从链表中删除p所指结点
            else                                   // p指向首元结点
                G->vertices[i].firstarc = p->next; // 头指针指向下一结点
            if (G->kind < 2)                       // 有向
            {
                G->arcnum--;            // 边或弧数-1
                if (G->kind == 1)       // 有向网
                    free(p->data.info); // 释放动态生成的权值空间
            }
            free(p); // 释放v为入度的结点
        }
        for (k = j + 1; k <= G->vexnum; k++) // 对于adjvex域>j的结点，其序号-1
        {
            e.adjvex = k;
            p = Point(G->vertices[i].firstarc, e, equalvex, &p1); // Point()在func2-1.cpp中
            if (p)
                p->data.adjvex--; // 序号-1(因为前移)
        }
    }
    return OK;
}

// 初始条件：图G存在，v和w是G中两个顶点
// 操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>
Status InsertArc(struct ALGraph *G, VertexType v, VertexType w)
{
    struct ElemType e;
    int i, j;
    i = LocateVex(*G, v); // 弧尾或边的序号
    j = LocateVex(*G, w); // 弧头或边的序号
    if (i < 0 || j < 0)
        return ERROR;
    G->arcnum++; // 图G的弧或边的数目加1
    e.adjvex = j;
    e.info = NULL;   // 初值
    if (G->kind % 2) // 网
    {
        e.info = (int *)malloc(sizeof(int)); // 动态生成存放权值的空间
        printf("请输入弧(边)%s→%s的权值: ", v, w);
        scanf("%d", e.info);
    }
    ListInsert(&G->vertices[i].firstarc, 1, e); // 将e插在弧尾的表头，在bo2-8.cpp中
    if (G->kind >= 2)                           // 无向，生成另一个表结点
    {
        e.adjvex = i;                               // e.info不变
        ListInsert(&G->vertices[j].firstarc, 1, e); // 将e插在弧头的表头
    }
    return OK;
}

// 初始条件：图G存在，v和w是G中两个顶点
// 操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>
Status DeleteArc(struct ALGraph *G, VertexType v, VertexType w)
{
    int i, j;
    Status k;
    struct ElemType e;
    i = LocateVex(*G, v); // i是顶点v(弧尾)的序号
    j = LocateVex(*G, w); // j是顶点w(弧头)的序号
    if (i < 0 || j < 0 || i == j)
        return ERROR;
    e.adjvex = j;
    k = DeleteElem(&G->vertices[i].firstarc, &e, equalvex); // 在func2-1.cpp中
    if (k)                                                  // 删除成功
    {
        G->arcnum--;     // 弧或边数减1
        if (G->kind % 2) // 网
            free(e.info);
        if (G->kind >= 2) // 无向，删除对称弧<w,v>
        {
            e.adjvex = i;
            DeleteElem(&G->vertices[j].firstarc, &e, equalvex);
        }
        return OK;
    }
    else // 没找到待删除的弧
    {
        return ERROR;
    }
}

Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
void (*VisitFunc)(char *v);      // 函数变量(全局量)
// 从第v个顶点出发递归地深度优先遍历图G。算法7.5
void DFS(struct ALGraph G, int v)
{
    int w;
    visited[v] = TRUE;             // 设置访问标志为TRUE(已访问)
    VisitFunc(G.vertices[v].data); // 访问第v个顶点
    for (w = FirstAdjVex(G, G.vertices[v].data); w >= 0; w = NextAdjVex(G, G.vertices[v].data, G.vertices[w].data))
        if (!visited[w])
            DFS(G, w); // 对v的尚未访问的邻接点w递归调用DFS
}

// 对图G作深度优先遍历。算法7.4
void DFSTraverse(struct ALGraph G, void (*Visit)(char *))
{
    int v;
    VisitFunc = Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数
    for (v = 0; v < G.vexnum; v++)
        visited[v] = FALSE; // 访问标志数组初始化
    for (v = 0; v < G.vexnum; v++)
        if (!visited[v])
            DFS(G, v); // 对尚未访问的顶点调用DFS
    printf("\n");
}

typedef int QElemType; // 队列元素类型

#if 1
typedef struct QNode
{
    QElemType data;     /* 数据域 */
    struct QNode *next; /* 指针域 */
} QNode, *QueuePtr;
typedef struct LinkQueue
{
    QueuePtr front; // 队头指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;
void InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
void ClearQueue(LinkQueue *Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemType *e);
void EnQueue(LinkQueue *Q, QElemType e);
Status DeQueue(LinkQueue *Q, QElemType *e);
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType));
void print(QElemType i);
void InitQueue(LinkQueue *Q)
{                                                         // 构造一个空队列 Q
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); /* 单链表的头结点 */

    if (Q->front == NULL)
        exit(-1);
    Q->front->next = NULL;
}
void DestroyQueue(LinkQueue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
}
void ClearQueue(LinkQueue *Q)
{
    QueuePtr p, q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
}
Status QueueEmpty(LinkQueue Q)
{
    if (Q.front->next == NULL)
        return TRUE;
    else
        return FALSE;
}
int QueueLength(LinkQueue Q)
{
    int i = 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p)
    {
        i++;
        p = p->next;
    }
    return i;
}
Status GetHead(LinkQueue Q, QElemType *e)
{
    QueuePtr p;
    if (Q.front == Q.rear)
        return ERROR;
    p = Q.front->next;
    *e = p->data;

    return OK;
}
void EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p;
    if (!(p = (QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
        exit(-1);
    p->data = e;
    p->next = NULL;    /* 新结点的 next 为空 */
    Q->rear->next = p; /* 上一次的尾指针指向新的结点 */
    Q->rear = p;       /* 新的尾指针 */
}
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;
    free(p);

    return OK;
}
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType))
{
    QueuePtr p;
    p = Q.front->next;
    while (p)
    {
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}

void print(QElemType i)
{
    // printf("%s ", i);
}
#endif

//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6
void BFSTraverse(struct ALGraph G, void (*Visit)(char *))
{
    int v, u, w;
    LinkQueue Q;
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;        // 置初值
    InitQueue(&Q);                 // 置空的辅助队列Q
    for (v = 0; v < G.vexnum; v++) // 如果是连通图，只v=0就遍历全图
        if (!visited[v])           // v尚未访问
        {
            visited[v] = TRUE;
            Visit(G.vertices[v].data);
            EnQueue(&Q, v);        // v入队列
            while (!QueueEmpty(Q)) // 队列不空
            {
                DeQueue(&Q, &u); // 队头元素出队并置为u
                for (w = FirstAdjVex(G, G.vertices[u].data); w >= 0; w = NextAdjVex(G, G.vertices[u].data, G.vertices[w].data))
                    if (!visited[w]) // w为u的尚未访问的邻接顶点
                    {
                        visited[w] = TRUE;
                        Visit(G.vertices[w].data);
                        EnQueue(&Q, w); // w入队
                    }
            }
        }
    printf("\n");
}

// 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构
void DFS1(struct ALGraph G, int v, void (*Visit)(char *))
{
    struct ArcNode *p;                               // p指向表结点
    visited[v] = TRUE;                               // 设置访问标志为TRUE(已访问)
    Visit(G.vertices[v].data);                       // 访问该顶点
    for (p = G.vertices[v].firstarc; p; p = p->next) // p依次指向v的邻接顶点
        if (!visited[p->data.adjvex])
            DFS1(G, p->data.adjvex, Visit); // 对v的尚未访问的邻接点递归调用DFS1
}

// 对图G作深度优先遍历。DFS1设函数指针参数
void DFSTraverse1(struct ALGraph G, void (*Visit)(char *))
{
    int v;
    for (v = 0; v < G.vexnum; v++)
        visited[v] = FALSE;        // 访问标志数组初始化，置初值为未被访问
    for (v = 0; v < G.vexnum; v++) // 如果是连通图，只v=0就遍历全图
        if (!visited[v])           // v尚未被访问
            DFS1(G, v, Visit);     // 对v调用DFS1
    printf("\n");
}

// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。仅适用于邻接表结构
void BFSTraverse1(struct ALGraph G, void (*Visit)(char *))
{
    int v, u;
    struct ArcNode *p; // p指向表结点
    LinkQueue Q;       // 链队列类型
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;        // 置初值为未被访问
    InitQueue(&Q);                 // 初始化辅助队列Q
    for (v = 0; v < G.vexnum; v++) // 如果是连通图，只v=0就遍历全图
        if (!visited[v])           // v尚未被访问
        {
            visited[v] = TRUE;         // 设v为已被访问
            Visit(G.vertices[v].data); // 访问v
            EnQueue(&Q, v);            // v入队列
            while (!QueueEmpty(Q))     // 队列不空
            {
                DeQueue(&Q, &u);                                 // 队头元素出队并置为u
                for (p = G.vertices[u].firstarc; p; p = p->next) // p依次指向u的邻接顶点
                    if (!visited[p->data.adjvex])                // u的邻接顶点尚未被访问
                    {
                        visited[p->data.adjvex] = TRUE;         // 该邻接顶点设为已被访问
                        Visit(G.vertices[p->data.adjvex].data); // 访问该邻接顶点
                        EnQueue(&Q, p->data.adjvex);            // 入队该邻接顶点序号
                    }
            }
        }
    printf("\n");
}

// 输出图的邻接矩阵G
void Display(struct ALGraph G)
{
    int i;
    struct ArcNode *p;
    switch (G.kind)
    {
    case DG:
        printf("有向图\n");
        break;
    case DN:
        printf("有向网\n");
        break;
    case UDG:
        printf("无向图\n");
        break;
    case UDN:
        printf("无向网\n");
    }
    printf("%d个顶点：\n", G.vexnum);
    for (i = 0; i < G.vexnum; ++i)
        printf("%s ", G.vertices[i].data);
    printf("\n%d条弧(边):\n", G.arcnum);
    for (i = 0; i < G.vexnum; i++)
    {
        p = G.vertices[i].firstarc;
        while (p)
        {
            if (G.kind <= 1 || i < p->data.adjvex) // 有向或无向两次中的一次
            {
                printf("%s→%s ", G.vertices[i].data, G.vertices[p->data.adjvex].data);
                if (G.kind % 2) // 网
                    printf(":%d ", *(p->data.info));
            }
            p = p->nextarc;
        }
        printf("\n");
    }
}

/************************ end of file **************************/


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403
  • 404
  • 405
  • 406
  • 407
  • 408
  • 409
  • 410
  • 411
  • 412
  • 413
  • 414
  • 415
  • 416
  • 417
  • 418
  • 419
  • 420
  • 421
  • 422
  • 423
  • 424
  • 425
  • 426
  • 427
  • 428
  • 429
  • 430
  • 431
  • 432
  • 433
  • 434
  • 435
  • 436
  • 437
  • 438
  • 439
  • 440
  • 441
  • 442
  • 443
  • 444
  • 445
  • 446
  • 447
  • 448
  • 449
  • 450
  • 451
  • 452
  • 453
  • 454
  • 455
  • 456
  • 457
  • 458
  • 459
  • 460
  • 461
  • 462
  • 463
  • 464
  • 465
  • 466
  • 467
  • 468
  • 469
  • 470
  • 471
  • 472
  • 473
  • 474
  • 475
  • 476
  • 477
  • 478
  • 479
  • 480
  • 481
  • 482
  • 483
  • 484
  • 485
  • 486
  • 487
  • 488
  • 489
  • 490
  • 491
  • 492
  • 493
  • 494
  • 495
  • 496
  • 497
  • 498
  • 499
  • 500
  • 501
  • 502
  • 503
  • 504
  • 505
  • 506
  • 507
  • 508
  • 509
  • 510
  • 511
  • 512
  • 513
  • 514
  • 515
  • 516
  • 517
  • 518
  • 519
  • 520
  • 521
  • 522
  • 523
  • 524
  • 525
  • 526
  • 527
  • 528
  • 529
  • 530
  • 531
  • 532
  • 533
  • 534
  • 535
  • 536
  • 537
  • 538
  • 539
  • 540
  • 541
  • 542
  • 543
  • 544
  • 545
  • 546
  • 547
  • 548
  • 549
  • 550
  • 551
  • 552
  • 553
  • 554
  • 555
  • 556
  • 557
  • 558
  • 559
  • 560
  • 561
  • 562
  • 563
  • 564
  • 565
  • 566
  • 567
  • 568
  • 569
  • 570
  • 571
  • 572
  • 573
  • 574
  • 575
  • 576
  • 577
  • 578
  • 579
  • 580
  • 581
  • 582
  • 583
  • 584
  • 585
  • 586
  • 587
  • 588
  • 589
  • 590
  • 591
  • 592
  • 593
  • 594
  • 595
  • 596
  • 597
  • 598
  • 599
  • 600
  • 601
  • 602
  • 603
  • 604
  • 605
  • 606
  • 607
  • 608
  • 609
  • 610
  • 611
  • 612
  • 613
  • 614
  • 615
  • 616
  • 617
  • 618
  • 619
  • 620
  • 621
  • 622
  • 623
  • 624
  • 625
  • 626
  • 627
  • 628
  • 629
  • 630
  • 631
  • 632
  • 633
  • 634
  • 635
  • 636
  • 637
  • 638
  • 639
  • 640
  • 641
  • 642
  • 643
  • 644
  • 645
  • 646
  • 647
  • 648
  • 649
  • 650
  • 651
  • 652
  • 653
  • 654
  • 655
  • 656
  • 657
  • 658
  • 659
  • 660
  • 661
  • 662
  • 663
  • 664
  • 665
  • 666
  • 667
  • 668
  • 669
  • 670
  • 671
  • 672
  • 673
  • 674
  • 675
  • 676
  • 677
  • 678
  • 679
  • 680
  • 681
  • 682
  • 683
  • 684
  • 685
  • 686
  • 687
  • 688
  • 689
  • 690
  • 691
  • 692
  • 693
  • 694
  • 695
  • 696
  • 697
  • 698
  • 699
  • 700
  • 701
  • 702
  • 703
  • 704
  • 705
  • 706
  • 707
  • 708
  • 709
  • 710
  • 711
  • 712
  • 713
  • 714
  • 715
  • 716
  • 717
  • 718
  • 719
  • 720
  • 721
  • 722
  • 723
  • 724
  • 725
  • 726
  • 727
  • 728
  • 729
  • 730
  • 731
  • 732
  • 733
  • 734
  • 735
  • 736
  • 737
  • 738
  • 739
  • 740
  • 741
  • 742
  • 743
  • 744
  • 745
  • 746
  • 747
  • 748
  • 749
  • 750
  • 751
  • 752
  • 753
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号