王道——数据结构——图（1）

系列文章目录其他章节相关文章

王道——数据结构——栈和队列（1）
王道——数据结构——树与二叉树（1）

本章节其他相关文章

文章目录

系列文章目录
- 其他章节相关文章
- 本章节其他相关文章
前言
一、邻接表矩阵法
- 一、图的建立
- - 1.1、不带权图的建立
  - 1.2、不带权图的其他相关函数
  - 1.1、带权图的建立
  - 1.2、带权图的其他相关函数
二、2.邻接表法(顺序+链式)
- - 1、图的建立（无向、有向）
  - 2、图的其他相关函数
三、十字链表法存储有向图
四、邻接多重表存储无向图

前言

本文为王道数据结构的第六章——图的编程题。
运行软件：vscode
使用c++文件编写

一、邻接表矩阵法一、图的建立

邻接矩阵法，使用数组实现的顺序存储
空间复杂度：O(|V|²)——只和顶点数有关，和实际边数无关，适合存放稠密图，可用对称矩阵的压缩办法压缩

1.1、不带权图的建立

该建立方法受限于本人技术能力，存在许多欠佳之处。
1、头文件并使用宏定义给出存储最大结点数

#include
#include
#include
#include
#define MaxVertexNum 100

2、图的结构体定义

// 不带权图
typedef struct{
    char Ver[MaxVertexNum];  // 存放顶点
    int Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
    int tag[MaxVertexNum];  // 标记该结点是否为空
}MGraph;

3、初始化

// 基本操作（不带权）
// 初始化
void InitMGraph(MGraph &G){
    for(int i = 0; i 
4、在不带权图G中插入一个节点 
// 在不带权图G中插入一个节点
bool InsertVerMG(MGraph &G, char x){  // 注意参数
    if(G.vexnum == MaxVertexNum)  // 空间已满
        return false;
    int i = 0;
    for (i; i 
5、在图G中删除顶点 时间复杂度 O(|V|)
 需要删除顶点及其所连接的边。 
// 在图G中删除顶点 时间复杂度 O(|V|)
bool DeleteVertexMG(MGraph &G, char x){
    if(G.vexnum == 0)  // 图为空
        return false;
    int i = 0;
    for(i;i  // 找到x的位置
        if(G.Ver[i] == x)
            break;
    }
    if(i == G.vexnum)  // 没有找到顶点
        return false;
    for(int j=0; i
    	// 无向图，由于对称性，更改比较方便
        if(G.Edge[i][j] != 0){  
            G.Edge[i][j] == 0;  // 将边置为0
            G.Edge[j][i] == 0;
            G.arcnum -= 2;  // 边数减2
        }
        // 有向图，需要分别对和进行判断
        // if(G.Edge[i][j] != 0){  判断
        //     G.Edge[i][j] == 0;
        //     G.arcnum--;
        // }
        // if(G.Edge[j][i] != 0){  // 判断
        //     G.Edge[j][i] == 0;
        //     G.arcnum--;
        // }
    }
    G.tag[i] = 0;  // 顶点标志位置0，标志该结点为空
    G.vexnum--;  // 顶点数减1
    return true;
}
 
6、在图G中增加边（x,y）或弧 
// 在图G中增加边（x,y）或弧  时间复杂度O(1)
bool AddEdgeMG(MGraph &G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k  // 分别找的x,y的位置
        if(i != -1 && j!=-1)
            break;
        if(G.Ver[k] == x)
            i = k;
        if(G.Ver[k] == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    // 无向图
    G.Edge[i][j] = 1; 
    G.Edge[j][i] = 1;
    G.arcnum+=2;
    // 有向图
    // G.Edge[i][j] = 1;  
    // G.arcnum++;
    return true;
}

 
7、在图G中删除边（x,y）或弧 
// 在图G中删除边（x,y）或弧  时间复杂度O(1)
bool DeleteEdgeMG(MGraph &G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k  // 找到x,y的位置
        if(i != -1 && j!=-1)
            break;
        if(G.Ver[k] == x)
            i = k;
        if(G.Ver[k] == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    // 无向图
    G.Edge[i][j] = 0;
    G.Edge[j][i] = 0;   
    G.arcnum-=2;
    // 有向图
    // G.Edge[i][j] = 0;
    // G.arcnum--;
    return true;
}
 
8、建立无向图(有向图类似，只需要修改AddEdgeMG函数) 
// 建立无向图(有向图类似，只需要修改AddEdgeMG函数)
void build_WX_MGraph(MGraph &G){
    char x,y;
    // 建立顶点列表
    printf("请输入你想插入的结点（Q为退出）：");
    scanf(" %c", &x);
    while(x != 'Q'){
        if(InsertVerMG(G, x)){
            printf("插入成功n");
        }
        else    
            printf("插入失败n");
        printf("请继续输入你想插入的结点（Q为退出）：");
        scanf(" %c", &x);
    }
    // 建立邻接矩阵
    printf("你要添加边吗（y or n）：");
    scanf(" %c", &y);
    while(y == 'y'){
        printf("请输入这条边的两个端点：");
        scanf(" %c", &x);
        scanf(" %c", &y);
        if(AddEdgeMG(G, x, y))
            printf("添加成功n");
        else
            printf("添加失败n");
        printf("你要继续添加边吗（y or n）：");
        scanf(" %c", &y);
    }
}
 
9、主程序 
int main(){
	MGraph G;  // 定义邻接矩阵存储的无向图
	InitMGraph(G);  // 初始化
	build_WX_MGraph(G);  // 建立图G
	Print_WX_MGraph(G);  // 打印输出图G
}
 
1.2、不带权图的其他相关函数 
1、打印输出图G 
void Print_WX_MGraph(MGraph G){
    for(int i=0; i
        printf("以%c为起点的边:", G.Ver[i]);
        Neighbors(G, G.Ver[i]);
        printf("n");
    }
}
 
2、判断图G是否存在弧或边（x, y） 
// 时间复杂度 O(1)  时间复杂度是在知道x，y下标情况下操作的时间复杂度
bool Adjacent(MGraph G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k  // 找到x,y的位置
        if(i != -1 && j!=-1)
            break;
        if(G.Ver[k] == x)
            i = k;
        if(G.Ver[k] == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1 || G.Edge[i][j] == 0)  // 判断边是否存在
        return false;
    return true;
}
 
3、求图G中顶点x的第一个邻接点 
// 求图G中顶点x的第一个邻接点，若有，返回顶点下标，没有，返回-1
int FirstNeighborMG(MGraph G, char x){
    int i = -1, k = 0, m=0;
    while(k  // 遍历所有的结点找到x
        if(G.Ver[k] == x){
            while(m 
4、输出x的相连边中(x,y)下一个边 
// 假设y是x的一个邻接点，返回除y之外的x的下一个邻接点下标，如果y是x的最后一个邻接点，返回-1
// 时间复杂度O(1)~O(|V|)
int NextNeighborMG(MGraph G, char x, char y){
    int i = -1, k = 0, m=0;
    while(k  // 遍历寻找顶点为x的值
        if(G.Ver[k] == x){  // 找到x
            while(m  // 在x所在行遍历寻找边（x,y）
                if(G.Ver[m] == y)  // 找到y
                    break;
                m++;
            }
            m++; // 寻找(x,y)的下一条边，所以要m+1
            while(m 
1.1、带权图的建立 
该建立方法受限于本人技术能力，存在许多欠佳之处。
 1、头文件并使用宏定义给出存储最大结点数
 由于两个不相连的边的距离为无穷大，所以要设置无穷大变量 
#include
#include
#include
#include

#define MaxVertexNum 100
#define INF INT_MAX
 
2、带权图的结构体定义 
// 不带权图
typedef struct{
    char Ver[MaxVertexNum];  // 结点列表
    int Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵
    int vexnum, arcnum; // 顶点总数和边总数
    int tag[MaxVertexNum];  // 该空间是否为空标记
}DQMGraph;
 
3、初始化 
// 基本操作（带权图）
// 初始化
void InitDQMGraph(DQMGraph &G){
    for(int i = 0; i
        for(int j = 0; j 
4、在带权图G中插入一个节点 
// 在带权图G中插入一个节点
bool InsertVerDQMG(DQMGraph &G, char x){
    if(G.vexnum == MaxVertexNum)
        return false;
    int i = 0;
    for (i; i 
5、在图G中删除顶点 时间复杂度 O(|V|)
 需要删除顶点及其所连接的边。 
// 在图G中删除顶点 时间复杂度 O(|V|)
bool DeleteVertexDQMG(DQMGraph &G, char x){
    if(G.vexnum == 0)
        return false;
    int i = 0;
    for(i;i
        if(G.Ver[i] == x)
            break;
    }
    if(i == G.vexnum)  // 没有找到顶点
        return false;
    for(int j=0; i
    	// 无向图
        if(G.Edge[i][j] != INF){  
            G.Edge[i][j] == INF;
            G.Edge[j][i] == INF;
            G.arcnum -= 2;
        }
        // // 有向图
        // if(G.Edge[i][j] != INF){
        //     G.Edge[i][j] == INF;
        //     G.arcnum--;
        // }
        // if(G.Edge[j][i] != INF){
        //     G.Edge[j][i] == INF;
        //     G.arcnum--;
        // }
    }
    G.tag[i] = 0;
    G.vexnum--;
    return true;
}
 
6、在图G中增加边（x,y）或弧 
// 在图G中增加边（x,y）或弧  时间复杂度O(1)
bool AddEdgeDQMG(DQMGraph &G, char x, char y, int info){
    int i = -1, j = -1, k = 0;
    while(k
        if(i != -1 && j!=-1)
            break;
        if(G.Ver[k] == x)
            i = k;
        if(G.Ver[k] == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    // 无向图
    G.Edge[i][j] = info; 
    G.Edge[j][i] = info;
    G.arcnum+=2;
    // 有向图
    // G.Edge[i][j] = info;  
    // G.arcnum++;
    return true;
}
 
7、在图G中删除边（x,y）或弧 
// 在图G中删除边（x,y）或弧  时间复杂度O(1)
bool DeleteEdgeDQMG(DQMGraph &G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k
        if(i != -1 && j!=-1)
            break;
        if(G.Ver[k] == x)
            i = k;
        if(G.Ver[k] == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    // 无向图
    G.Edge[i][j] = INF;
    G.Edge[j][i] = INF;   
    G.arcnum-=2;
    // 有向图
    // G.Edge[i][j] = INF;
    // G.arcnum--;
    return true;
}
 
8、建立无向图(有向图类似，只需要修改AddEdgeMG函数) 
// 建立带权无向图  (有向图类似，只需要修改AddEdgeMG函数)
void build_WX_DQMGraph(DQMGraph &G){
    char x,y;
    int z;
    printf("请输入你想插入的结点（Q为退出）：");
    scanf(" %c", &x);
    while(x != 'Q'){
        if(InsertVerDQMG(G, x)){
            printf("插入成功n");
        }
        else    
            printf("插入失败n");
        printf("请继续输入你想插入的结点（Q为退出）：");
        scanf(" %c", &x);
    }
    printf("你要添加边吗（y or n）：");
    scanf(" %c", &y);
    while(y == 'y'){
        printf("请输入这条边的两个端点和权重：");
        scanf(" %c", &x);
        scanf(" %c", &y);
        scanf(" %d", &z);
        if(AddEdgeDQMG(G, x, y, z))
            printf("添加成功n");
        else
            printf("添加失败n");
        printf("你要继续添加边吗（y or n）：");
        scanf(" %c", &y);
    }
}
 
9、主程序 
int main(){
	DQMGraph G;  // 定义邻接矩阵存储的带权无向图
	InitDQMGraph(G);  // 初始化
	build_WX_DQMGraph(G);  // 建立图G
	Print_WX_DQMGraph(G);  // 打印输出图G
}
 
1.2、带权图的其他相关函数 
1、打印输出图G 
void Print_WX_DQMGraph(DQMGraph G){
    for(int i=0; i
        printf("以%c为起点的边:", G.Ver[i]);
        NeighborsDQMG(G, G.Ver[i]);
        printf("n");
    }
}
 
2、列出图G中与结点x邻接的边 
// 列出图G中与结点x邻接的边
void NeighborsDQMG(DQMGraph G, char x){
    int i = -1, k = 0;
    while(k  // 找到顶点x
        if(G.Ver[k] == x){
            i = k;
            break;
        }
        k++;
    }
    if(i == -1)
        printf("你想查找的结点不存在n");
    int tag = 0;  // 标志位 0代表没有边
    for(k = 0; k  // 找出与x相连的所有边
        if(G.Edge[i][k] != INF && G.Edge[i][k] != 0){
            printf("%c-%c权重为%d ", x, G.Ver[k], G.Edge[i][k]);
            tag = 1;
        }
    }
    if(tag == 0)
        printf("没有边n");
}
 
3、求图G中顶点x的第一个邻接点 
// 求图G中顶点x的第一个邻接点，若有，返回顶点下标，没有，返回-1
int FirstNeighborDQMG(DQMGraph G, char x){
    int i = -1, k = 0, m=0;
    while(k  // 寻找x的下标
        if(G.Ver[k] == x){  // 找到第k个元素
            while(m 
4、输出x的相连边中(x,y)下一个边 
// 假设y是x的一个邻接点，返回除y之外的x的下一个邻接点下标，如果y是x的最后一个邻接点，返回-1
// 时间复杂度O(1)~O(|V|)
int NextNeighborDQMG(DQMGraph G, char x, char y){
    int i = -1, k = 0, m=0;
    while(k
        if(G.Ver[k] == x){  // 找到结点x
            while(m
                if(G.Ver[m] == y)  // 找到结点y
                    break;
                m++; 
            }
            m++;  // 从结点y继续向后找
            while(m 
二、2.邻接表法(顺序+链式) 
无向图的空间复杂度O(|V| + 2|E|), 有向图的空间复杂度O(|V| + |E|)
 特点：存储无向图的存在冗余数据，删除结点时很麻烦 
1、图的建立（无向、有向） 
该建立方法受限于本人技术能力，存在许多欠佳之处。
 1、头文件 
#include
#include
#include
#include

 
2、图的结构体定义 
// 边/弧
typedef struct ArcNode{
    int adivex;  // 边/弧指向的结点下标
    struct ArcNode *next;  // 指向下一条弧的指针
    // int info  // 边权值
}ArcNode;

// 顶点
typedef struct VNode{
    char data;  // 存放顶点信息
    ArcNode *first;   //顶点的第一条边/弧
    int tag;  // 标志该空间是否空闲
}VNode, AdjList[MaxVertexNum];

// 用邻接表存储图
typedef struct{
    AdjList vertices;  // 顶点列表
    int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
}ALGraph;
 
3、初始化 
// 基本操作
// 初始化
void InitALGraph(ALGraph &G){
    G.arcnum = 0;
    G.vexnum = 0;
    for(int i=0; i
        G.vertices[i].tag = 0;
        G.vertices[i].first = NULL;
    }
}
 
4、在图G中插入一个节点 
// 在图G中插入一个节点
bool InsertVerALG(ALGraph &G, char x){
    if(G.vexnum == MaxVertexNum)
        return false;
    int i = 0;
    for(i;i 
5、在图G中删除顶点 时间复杂度 O(|V|)
 需要删除顶点及其所连接的边。 
// 在图G中删除结点 时间复杂度O(1)~O(|V|)
bool DeleteVertexALG(ALGraph &G, char x){
    if(G.vexnum == 0)
        return false;
    for(int i = 0; i  // 遍历所有的顶点，如果是顶点x,删除顶点及其所有连接的边，如果不是顶点x，删除该顶点与x相连的边
        ArcNode *p = G.vertices[i].first;
        if(G.vertices[i].data == x){  // 该顶点是x
            G.vertices[i].tag = 0;  // 将该空间标为空闲
            G.vexnum--;  // 顶点数减一
            while(p){  // 遍历与x相连的所有边，全部删除
                ArcNode *q = p; 
                p = p->next;
                G.arcnum--;
                free(q);
            }
        }
        else{  // 不是顶点x，遍历该顶点所有的边，如果与x相连，则删去
            while(p->next != NULL && G.vertices[p->next->adivex].data != x)  // 寻找与x相连的边
                p = p->next;
            if(p->next != NULL){  // 删除与x相连的边
                ArcNode *q = p->next;
                p->next = q->next;
                free(q);
                G.arcnum--;
            }
        }
    }
    return true;
}
 
6、在无向图G中增加边（x,y）或弧 
// 在图G中增加边（x,y）或弧 时间复杂度O(1)~O(|V|)
bool AddEdgeALG(ALGraph &G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k  // 寻找x和y的下标
        if(i != -1 && j!=-1)
            break;
        if(G.vertices[k].data == x)
            i = k;
        if(G.vertices[k].data == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    // 在无向图中增加边，需要添加(x,y)和(y,x)
    ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
    q->adivex = j;  
    q->next = G.vertices[i].first;  // 头插法
    G.vertices[i].first = q;  
    G.arcnum++;
    // 添加(y,x)
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adivex = i;
    p->next = G.vertices[j].first;
    G.vertices[j].first = p;
    G.arcnum++;
    return true;
}
}
 
7、在有向图G中增加边（x,y）或弧 
// 在图G中增加边（x,y）或弧 时间复杂度O(1)~O(|V|)
bool AddEdgeALG_YX(ALGraph &G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k
        if(i != -1 && j!=-1)
            break;
        if(G.vertices[k].data == x)
            i = k;
        if(G.vertices[k].data == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
    q->adivex = j;  
    q->next = G.vertices[i].first;  // 头插法
    G.vertices[i].first = q;  
    G.arcnum++;
    return true;
}
 
8、建立邻接表存储的无向图 
// 建立邻接表存储的无向图
void build_WX_ALGraph(ALGraph &G){
    char x, y;
    // 建立顶点列表
    printf("请输入你想插入的结点（Q为退出）：");
    scanf(" %c", &x);
    while(x != 'Q'){
        if(InsertVerALG(G, x))
            printf("插入成功n");
        else
            printf("插入失败n");
        printf("请继续输入你想插入的结点（Q为退出）：");
        scanf(" %c", &x);
    }
    // 建立边列表
    printf("你要添加边吗（y or n）：");
    scanf(" %c", &y);
    while(y == 'y'){
        printf("请输入这条边的两个端点：");
        scanf(" %c", &x);
        scanf(" %c", &y);
        if(AddEdgeALG(G, x, y))
            printf("添加成功n");
        else
            printf("添加失败n");
        printf("你要继续添加边吗（y or n）：");
        scanf(" %c", &y);
    }
}
 
9、建立邻接表存储的有向图 
// 建立邻接表存储的有向图
void build_YX_ALGraph(ALGraph &G){
    char x, y;
    // 建立顶点列表
    printf("请输入你想插入的结点（Q为退出）：");
    scanf(" %c", &x);
    while(x != 'Q'){
        if(InsertVerALG(G, x))
            printf("插入成功n");
        else
            printf("插入失败n");
        printf("请继续输入你想插入的结点（Q为退出）：");
        scanf(" %c", &x);
    }
    // 建立边列表
    printf("你要添加边吗（y or n）：");
    scanf(" %c", &y);
    while(y == 'y'){
        printf("请输入这条边的两个端点：");
        scanf(" %c", &x);
        scanf(" %c", &y);
        if(AddEdgeALG_YX(G, x, y))
            printf("添加成功n");
        else
            printf("添加失败n");
        printf("你要继续添加边吗（y or n）：");
        scanf(" %c", &y);
    }
}

 
9、主程序 
int main(){
	ALGraph G;  // 定义邻接矩阵存储的无向图
	InitALGraph(G);  // 初始化
	build_WX_ALGraph(G);  // 建立图G
	Print_WX_ALGraph(G);  // 打印输出图G
}
 
2、图的其他相关函数 
1、打印输出图G 
void Print_WX_ALGraph(ALGraph &G){
    for(int i=0; i
        printf("以%c为起点的出边:", G.vertices[i].data);
        AdjListNeighbors(G, G.vertices[i].data);
        printf("以%c为起点的入边:", G.vertices[i].data);
        AdjListHHNeighbors(G, G.vertices[i].data);
        printf("n");
    }
}

 
2、判断图G是否存在弧或边（x, y） 
// 判断图G是否存在弧或边（x, y）
// 时间复杂度 O(1)~O(|V|)
bool AdjListacent(ALGraph G, char x, char y){
    int i = -1, j = -1, k = 0;
    while(k
        if(i != -1 && j!=-1)
            break;
        if(G.vertices[k].data == x)
            i = k;
        if(G.vertices[k].data == y)
            j = k;
        k++;
    }
    if(i == -1 || j == -1)
        return false;
    ArcNode *p = G.vertices[i].first;
    while(p && p->adivex != j)
        p = p->next;
    if(p)
        return true;
    return false;
}
 
3、求图G中顶点x的第一个邻接点 
// 求图G中顶点x的第一个邻接点，若有，返回顶点下标，没有，返回-1
// 时间复杂度O(1)
int FirstNeighborALG(ALGraph G, char x){
    int i = -1, k = 0;
    while(k
        if(G.vertices[k].data == x){
            if(G.vertices[k].first != NULL)
                return G.vertices[k].first->adivex;
            return -1;
        }
        k++;
    }
    return -1;
}
 
4、输出x的相连边中(x,y)下一个边 
// 假设y是x的一个邻接点，返回除y之外的x的下一个邻接点下标，如果y是x的最后一个邻接点，返回-1
// 时间复杂度O(1)
int NextNeighborALG(ALGraph G, char x, char y){
    int i = -1, k = 0;
    while(k
        if(G.vertices[k].data == x){
            ArcNode *p = G.vertices[k].first;
            while(G.vertices[p->adivex].data != y)
                p = p->next;
            if(p->next == NULL)
                return -1;
            return p->next->adivex;
        }
        k++;
    }
    return -1;
}

 
5、列出图G中与结点x邻接的边和出边 
// 列出图G中与结点x邻接的边和出边
void AdjListNeighbors(ALGraph G, char x){
    int i = -1, k = 0;
    while(k  // 找到x的位置
        if(G.vertices[k].data == x){
            i = k;
            break;
        }
        k++;
    }
    if(i == -1)
        printf("你想查找的结点不存在n");
    int tag = 0;  // 标志位 0代表没有边
    ArcNode *p = G.vertices[i].first;
    while(p){ // 打印输出x所有连接的边
        tag = 1;
        printf("%c->%c ", x, G.vertices[p->adivex].data);
        p = p->next;
    }
    if(tag == 0)
        printf("没有边n");
}

 
6、列出图G中与结点x邻接的入边 
// 列出图G中与结点x邻接的入边
void AdjListHHNeighbors(ALGraph G, char x){
    int i = -1, k = 0;
    while(k
        if(G.vertices[k].data == x){
            i = k;
            break;
        }
        k++;
    }
    if(i == -1)
        printf("你想查找的结点不存在n");
    int tag = 0;  // 标志位 0代表没有边
    for (k = 0; k  // 找到除x之外所有的顶点
        ArcNode *p = G.vertices[k].first;
        while(p){  // 遍历该结点所有的边
            if(p->adivex == i){  // 如果与x相连，打印输出
                tag = 1;
                printf("%c->%c ", G.vertices[k].data, x);
            }
            p = p->next;
        }
    }
    if(tag == 0)
        printf("没有入边");
}
 
三、十字链表法存储有向图 
空间复杂度O(|V| + |E|)，和邻接表法一样，但是解决了邻接表法找入度出度不变的问题 
结构体定义 
// 弧结点
typedef struct TArcNode{
    int tailvex, headvex; // 弧尾和弧头编号
    int info;  // 权重
    struct TArcNode *hlink, *tlink;  // 弧头相同的下一条弧，弧尾相同的下一条弧
}TArcNode;

// 顶点结点
typedef struct TVNode{
    char data; // 数据域
    TArcNode *firstin, *firstout; // 入度，和出度的第一条弧
}TVNode, TList[MaxVertexNum];

// 十字链表法存储图
typedef struct{
    TList vertices;
    int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
}TLGraph;
 
四、邻接多重表存储无向图 
空间复杂度O(|V| + |E|)，比邻接表更好
 删除边，删除结点更加方便
 只适用于存储无向图 
结构体定义 
// 边结点
typedef struct DArcNode{
    int i ,j ,info;  // i,j为边的两个顶点编号，info为权重
    struct DArcNode *iLink, *jLink;  // 依附于顶点i的下一条边和依附于顶点j的下一条边
}DArcNode;

// 顶点结点
typedef struct DVNode{
    char data;  // 数据域
    DArcNode *firstedge;  // 与该结点相连的第一条边
}DVNode, DList[MaxVertexNum];

// 邻接多重表法存储图
typedef struct{
    DList vertices;
    int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
}DLGraph;

王道——数据结构——图（1）

C/C++/C#相关栏目本月热门文章