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

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

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

图的定义

图 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
|
6月前
|
存储
邻接表详解
邻接表详解
stormsha
37 0
dulu~dulu
|
6月前
|
存储 算法
有向图和无向图的表示方式(邻接矩阵，邻接表)
有向图和无向图的表示方式(邻接矩阵，邻接表)
dulu~dulu
208 0
为梦而生~
|
存储 机器学习/深度学习 人工智能
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
为梦而生~
1298 1
ZhangBlossom
|
存储
图操作之邻接矩阵与邻接表的深度优先遍历
图操作之邻接矩阵与邻接表的深度优先遍历
ZhangBlossom
175 0
dm2e66eopcgq6
有向图、无向图找环
笔记
dm2e66eopcgq6
176 0
CastenWang
拓扑排序（邻接表实现）
拓扑排序（邻接表实现）
CastenWang
182 0
拓扑排序（邻接表实现）
Lucky小黄人^_^
用邻接表表示图
用邻接表表示图
Lucky小黄人^_^
48 0
游客ghkclzcxdckbo
|
存储
邻接矩阵
数据结构中无向图邻接矩阵的存储
游客ghkclzcxdckbo
97 0
邻接矩阵
kyxdt4sqtmta6
|
存储 JavaScript 算法
邻接表详解（C/C++）
目录 一、概念 二、分类 1）无向图的邻接表 2）有向图的邻接表（出弧） 3）有向图的逆邻接表（入弧） 三.步骤 四、代码
kyxdt4sqtmta6
658 0
邻接表详解（C/C++）
zzqwtc
邻接表
笔记
zzqwtc
75 0