AI 助理
备案控制台
开发者社区 人工智能 文章 正文

有向图，无向图的邻接矩阵和邻接表模板

2022-12-02 204
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 有向图，无向图的邻接矩阵和邻接表模板

图的定义

图 G GG 由顶点集 V VV 和边集 E EE 组成，记为 G = ( V , E ) G=(V,E)G=(V,E)，其中 V ( G ) V(G)V(G) 表示图 G GG 中顶点的有限非空集；E ( G ) E(G)E(G) 表示图 G GG 中顶点之间的关系（边）集合。


有向图

概念

若 E是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 < v , w > ，其中 v , w是顶点， v  称为弧尾，w 称为弧头，< v , w > 称为从 v 到 w 的弧，也称 v 邻接到 w。



模板

邻接矩阵

/* 
有向图邻接矩阵
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MaxVertexNum 100
typedef int weightType;  // 权重数据类型
typedef char vertexType; // 顶点数据类型
struct Graph
{
    int vertexnum;
    int edgenum;
    vertexType vertexList[MaxVertexNum];
    weightType edgeList[MaxVertexNum][MaxVertexNum];
};
void BuildGraph(Graph *G)
{
    int start, end;
    cout << "Please enter the number of vertices and edges" << endl;
    cin >> G->vertexnum >> G->edgenum;
    // 图的权重初始化
    for (int i = 0; i < G->vertexnum; i++)
    {
        for (int j = 0; j < G->vertexnum; j++)
        {
            G->edgeList[i][j] = 0;
        }
    }
    // 图的顶点数据
    for (int i = 0; i < G->vertexnum; i++)
    {
        cout << "Please enter the data of vertex" << i + 1 << endl;
        cin >> G->vertexList[i];
    }
    // 输入权重信息
    for (int i = 0; i < G->edgenum; i++)
    {
        cout << "Please enter the Start number, end number, weight" << endl;
        cin >> start >> end;
        cin >> G->edgeList[start - 1][end - 1];
    }
    cout << endl;
}
void Print_Adjacency_Matrix(Graph G)
{
    for (int i = 0; i < G.vertexnum; i++)
    {
        for (int j = 0; j < G.vertexnum; j++)
        {
            cout << G.edgeList[i][j] << '\t';
        }
        cout << endl;
    }
}
int main()
{
    Graph G;
    BuildGraph(&G);
    Print_Adjacency_Matrix(G);
    cout << endl;
    system("pause");
    return 0;
}


邻接表

/* 
有向图邻接表
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MaxVertexNum 100
typedef int weightType;  // 权重数据类型
typedef char vertexType; // 顶点数据类型
struct EdgeNode
{
    int adjvex;
    weightType weight;
    EdgeNode *next;
};
struct VertexNode
{
    vertexType data;
    EdgeNode *firstedge;
};
struct Graph
{
    int vertexnum;
    int edgenum;
    VertexNode vertexList[MaxVertexNum];
    VertexNode inverseVertexList[MaxVertexNum];
};
void BuildGraph(Graph *G)
{
    int start, end, weight;
    EdgeNode *newnode;
    cout << "Please enter the number of vertices and edges" << endl;
    cin >> G->vertexnum >> G->edgenum;
    // 图的顶点数据
    for (int i = 0; i < G->vertexnum; i++)
    {
        cout << "Please enter the data of vertex" << i << endl;
        cin >> G->vertexList[i].data;
        G->vertexList[i].firstedge = NULL;
        G->inverseVertexList[i].data = G->vertexList[i].data;
        G->inverseVertexList[i].firstedge = NULL;
    }
    // 输入权重信息
    for (int i = 0; i < G->edgenum; i++)
    {
        cout << "Please enter the Start number, end number, weight" << endl;
        cin >> start >> end >> weight;
        //start-->end
        newnode = new EdgeNode;
        newnode->adjvex = end;
        newnode->weight = weight;
        newnode->next = G->vertexList[start].firstedge;
        G->vertexList[start].firstedge = newnode;
        // 逆邻接表
        newnode = new EdgeNode;
        newnode->adjvex = start;
        newnode->weight = weight;
        newnode->next = G->inverseVertexList[end].firstedge;
        G->inverseVertexList[end].firstedge = newnode;
    }
}
void Print_Adjacency_Matrix(Graph G)
{
    for (int i = 0; i < G.vertexnum; i++)
    {
        cout << G.vertexList[i].data << '\t';
        EdgeNode *p = G.vertexList[i].firstedge;
        while (p)
        {
            printf("adjvex:%d weight:%d  ", p->adjvex, p->weight);
            p = p->next;
        }
        cout << endl;
    }
    cout << endl;
    cout << "inverse adjacency list" << endl;
    for (int i = 0; i < G.vertexnum; i++)
    {
        cout << G.inverseVertexList[i].data << '\t';
        EdgeNode *p = G.inverseVertexList[i].firstedge;
        while (p)
        {
            printf("adjvex:%d weight:%d  ", p->adjvex, p->weight);
            p = p->next;
        }
        cout << endl;
    }
}
int main()
{
    Graph G;
    BuildGraph(&G);
    Print_Adjacency_Matrix(G);
    cout << endl;
    system("pause");
    return 0;
}


无向图

概念

若 E是无向边的有限集合时，则图 G 为有向图。边是顶点的无序对，记为 ( v , w )或 ( w , v )。可以说 w 和 v  互 为邻接点。边 ( V , W )依附于 w 和 v ，或称边 ( v , w ) 和 v , w相关联。



模板

邻接矩阵

/* 
无向图邻接矩阵
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MaxVertexNum 100
typedef int weightType;  // 权重数据类型
typedef char vertexType; // 顶点数据类型
struct Graph
{
    int vertexnum;
    int edgenum;
    vertexType vertexList[MaxVertexNum];
    weightType edgeList[MaxVertexNum][MaxVertexNum];
};
void BuildGraph(Graph *G)
{
    int start, end;
    cout << "Please enter the number of vertices and edges" << endl;
    cin >> G->vertexnum >> G->edgenum;
    // 图的权重初始化
    for (int i = 0; i < G->vertexnum; i++)
    {
        for (int j = 0; j < G->vertexnum; j++)
        {
            G->edgeList[i][j] = 0;
        }
    }
    // 图的顶点数据
    for (int i = 0; i < G->vertexnum; i++)
    {
        cout << "Please enter the data of vertex" << i + 1 << endl;
        cin >> G->vertexList[i];
    }
    // 输入权重信息
    for (int i = 0; i < G->edgenum; i++)
    {
        cout << "Please enter the Start number, end number, weight" << endl;
        cin >> start >> end;
        cin >> G->edgeList[start - 1][end - 1];
        G->edgeList[end - 1][start - 1] = G->edgeList[start - 1][end - 1];
    }
    cout << endl;
}
void Print_Adjacency_Matrix(Graph G)
{
    cout << '\t';
    for (int i = 0; i < G.vertexnum; i++)
    {
        cout << G.vertexList[i] << '\t';
    }
    cout << endl;
    for (int i = 0; i < G.vertexnum; i++)
    {
        cout << G.vertexList[i] << '\t';
        for (int j = 0; j < G.vertexnum; j++)
        {
            cout << G.edgeList[i][j] << '\t';
        }
        cout << endl;
    }
}
int main()
{
    Graph G;
    BuildGraph(&G);
    Print_Adjacency_Matrix(G);
    cout << endl;
    system("pause");
    return 0;
}


邻接表


/* 
无向图邻接表
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MaxVertexNum 100
typedef int weightType;  // 权重数据类型
typedef char vertexType; // 顶点数据类型
struct EdgeNode
{
    int adjvex;
    weightType weight;
    EdgeNode *next;
};
struct VertexNode
{
    vertexType data;
    EdgeNode *firstedge;
};
struct Graph
{
    int vertexnum;
    int edgenum;
    VertexNode vertexList[MaxVertexNum];
};
void BuildGraph(Graph *G)
{
    int start, end, weight;
    EdgeNode *newnode;
    cout << "Please enter the number of vertices and edges" << endl;
    cin >> G->vertexnum >> G->edgenum;
    // 图的顶点数据
    for (int i = 0; i < G->vertexnum; i++)
    {
        cout << "Please enter the data of vertex" << i << endl;
        cin >> G->vertexList[i].data;
        G->vertexList[i].firstedge = NULL;
    }
    // 输入权重信息
    for (int i = 0; i < G->edgenum; i++)
    {
        cout << "Please enter the Start number, end number, weight" << endl;
        cin >> start >> end >> weight;
        //start-->end
        newnode = new EdgeNode;
        newnode->adjvex = end;
        newnode->weight = weight;
        newnode->next = G->vertexList[start].firstedge;
        G->vertexList[start].firstedge = newnode;
        // end-->start
        newnode = new EdgeNode;
        newnode->adjvex = start;
        newnode->weight = weight;
        newnode->next = G->vertexList[end].firstedge;
        G->vertexList[end].firstedge = newnode;
    }
}
void Print_Adjacency_Matrix(Graph G)
{
    for (int i = 0; i < G.vertexnum; i++)
    {
        cout << G.vertexList[i].data << '\t';
        EdgeNode *p = G.vertexList[i].firstedge;
        while (p)
        {
            printf("adjvex:%d weight:%d\n", p->adjvex, p->weight);
            p = p->next;
        }
        cout << endl;
    }
}
int main()
{
    Graph G;
    BuildGraph(&G);
    Print_Adjacency_Matrix(G);
    cout << endl;
    system("pause");
    return 0;
}


简单图

1.不存在重复边

2.不存在顶点到自身的边


完全图

对于无向图

∣E∣ 的取值范围 0到 n ( n − 1 ) / 2，有 n ( n − 1 ) / 2条边的无向图称为完全图


对于有向图

∣E∣ 的取值范围 0 到 n ( n − 1 ) ，有 n ( n − 1 )条弧的有向图称为有向完全图

文章标签：
机器学习/深度学习
CastenWang
目录
相关文章
stormsha
|
7月前
|
存储
邻接表详解
邻接表详解
stormsha
45 0
dulu~dulu
|
7月前
|
存储 算法
有向图和无向图的表示方式(邻接矩阵，邻接表)
有向图和无向图的表示方式(邻接矩阵，邻接表)
dulu~dulu
408 0
为梦而生~
|
存储 机器学习/深度学习 人工智能
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
为梦而生~
1457 1
ZhangBlossom
|
存储
图操作之邻接矩阵与邻接表的深度优先遍历
图操作之邻接矩阵与邻接表的深度优先遍历
ZhangBlossom
212 0
dm2e66eopcgq6
有向图、无向图找环
笔记
dm2e66eopcgq6
199 0
CastenWang
拓扑排序（邻接表实现）
拓扑排序（邻接表实现）
CastenWang
202 0
拓扑排序（邻接表实现）
Lucky小黄人^_^
用邻接表表示图
用邻接表表示图
Lucky小黄人^_^
54 0
游客ghkclzcxdckbo
|
存储
邻接矩阵
数据结构中无向图邻接矩阵的存储
游客ghkclzcxdckbo
100 0
邻接矩阵
kyxdt4sqtmta6
|
存储 JavaScript 算法
邻接表详解（C/C++）
目录 一、概念 二、分类 1）无向图的邻接表 2）有向图的邻接表（出弧） 3）有向图的逆邻接表（入弧） 三.步骤 四、代码
kyxdt4sqtmta6
715 0
邻接表详解（C/C++）
zzqwtc
邻接表
笔记
zzqwtc
78 0

热门文章

最新文章

  • 1
    基于区块链的机器学习模型创建方案
  • 2
    性能的极致,Rust的加持,Zed-Dev编辑器快速搭建Python3.10开发环境
  • 3
    首届Global VR Hackathon完结 全球前三甲诞生
  • 4
    我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
  • 5
    iptables
  • 6
    DevExpress 10.2.4系列-ASPxListBox根据列值不同设置不同图标
  • 7
    jquery的load加载js页面到指定div中
  • 8
    分享平时工作中那些给力的shell命令（更新版）
  • 9
    如何在ubuntu下用SVN commit
  • 10
    hdu 1800 Flying to the Mars
  • 1
    HelloMeme：开源的面部表情与姿态迁移框架，将视频中的人物表情迁移到静态图像中生成动态视频
    102
  • 2
    VSI-Bench：李飞飞谢赛宁团队推出视觉空间智能基准测试集，旨在评估多模态大语言模型在空间认知和理解方面的能力
    32
  • 3
    CLEAR：新加坡国立大学推出线性注意力机制，使8K图像的生成速度提升6.3倍，显著减少了计算量和时间延迟
    32
  • 4
    Kheish：开源的多智能体开发框架，通过 YAML 配置工作流和多个 Agent 共同协作解决复杂任务
    41
  • 5
    Bamba-9B：基于 Mamba2 架构的仅解码语言模型，旨在提高大型语言模型在推理时的效率
    37
  • 6
    DisPose：清华北大等多所高校联合推出基于人物图像增强视频生成技术，实现对人物动画的准确控制和一致性
    41
  • 7
    InvSR：开源图像超分辨率生成模型，提升分辨率，修复老旧照片为超清图像
    36
  • 8
    Univer：开源全栈 AI 办公工具，支持 Word、Excel、PPT 等文档处理和多人实时协作
    28
  • 9
    《人工智能：驱散新材料数据噪声与填补缺失值的曙光》
    25
  • 10
    《人工智能：解锁新材料最佳掺杂元素及比例的密码》
    21

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    DataWorks售前咨询