小弟求大神解答:图论中的多边图是如何存储的?

现在在做社交网络影响力传播这块,遇到一个算法需要用C++实现,但涉及到了多边图(多重图),
我知道简单图一般用邻接矩阵或邻接表来存储,但是多边图(多重图)用什么数据结构来储存呢,
最好用c++帮我实现以下或者把关键代码发一下,谢谢了!

0

4个回答

1.这个是可以正常用邻接表存的2.你也可以用边集数组直接存边

0

邻接表——动态建表

[cpp] view plain copy

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
const int MAXN = 100;  

struct EdgeNode<span style="white-space:pre">     </span>//邻接表节点  
{  
    int to;<span style="white-space:pre">     </span>//终点  
    int w;<span style="white-space:pre">      </span>//权值  
    EdgeNode *next;<span style="white-space:pre"> </span>//指向下一条边的指针  
};  

struct VNode<span style="white-space:pre">        </span>//起点表节点  
{  
    int from;<span style="white-space:pre">       </span>//起点  
    EdgeNode *first;<span style="white-space:pre">    </span>//邻接表头指针  
};  

VNode Adjlist[MAXN];<span style="white-space:pre">    </span>//整个图的邻接表  


int main()  
{  
    int n,m,x,y,w;  
    cin >> n >> m;  
    for(int i = 0; i < m; i++)//读入图  
    {  
        cin >> x >> y >> w;  
        EdgeNode *p = new EdgeNode();  
        p->to = y;  
        p->w = w;  
        p->next = Adjlist[x].first;  
        Adjlist[x].first = p;  
    }  
    cout << endl;  
    for(int i = 1; i <= n; i++)//遍历图  
    {  
        for(EdgeNode *k = Adjlist[i].first; k != NULL; k = k->next)  
            cout << i << ' ' << k->to << ' ' << k->w << endl;  
    }  
    return 0;  
}  
0

运用五种方式来实现图的存储,以适应不同的情况。

参考:ACM-ICPC程序设计系列——图论及应用

方式1:邻接矩阵

邻接矩阵是表示图的数据结构中最简单也是最常用的一种。

实现:二维数组Map[MAXN][MAXN],Map[i][j]表示点i到点j的距离。

初始化:Map[i][i] = 0,Map[i][j] = INF(i!=j),读入数据Map[i][j] = w。

时间复杂度:初始化O(n^2),建图需要O(m),总时间复杂度O(n^2)。

优缺点:简单直观,可直接查询点i和点j之间是否有边;遍历效率低,不

能存储重编;初始化效率低;大图开销大,适合存储点少的稠密图。

方式2:前向星

0

邻接表可以存带重边的图的

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
图论算法——环和有向无环图
环和有向无环图rn在有向图相关的实际应用中,有向环特别重要。一幅图可能含有大量的环,通常,我们一般只关注它们是否存在。rn调度问题rn给定一组任务并安排它们的执行顺序,限制条件为这些任务的执行方法、起始时间以及任务的消耗等。最重要的一种限制条件叫做优先级限制,它指定了哪些任务必须在哪些任务之前完成。不同类型的限制条件会产生不同难度的调度问题。rn以一个正在安排课程的大学生为例,有些课程是其他课程的先导课程...
图论3——图的存储与基本性质
在数学上,图是表示物件与物件之间联系的数学对象;而在计算机中,每个物件可以抽象成一个节点,而关系就是一条边。rnrn这里主要介绍图的一些较关键的性质以及邻接矩阵、邻接表的应用。rnrn1、有向图和无向图rnrn图分为有向图和无向图。顾名思义,有向图就是每条边都具有方向,一条从A->B的有向边它可以让一个东西从A走到B,却不能沿同一条边从B走回A;反之,无向图就是不具有方向的,既可以从A到B,也可以
《图论与代数结构》(戴一奇,清华大学出版社)习题解答
《图论与代数结构》(戴一奇,清华大学出版社)习题解答 图论课程必备!
图论基础之 图中找环
对于有向图而言 可以使用拓扑排序的方式找出图中的环#include&amp;lt;bits/stdc++.h&amp;gt;nusing namespace std;nconst int maxn = 1e5+7;nint n;nint du[maxn];//入度nvector&amp;lt;int&amp;gt; gra[10];nvector&amp;lt;int&amp;gt; res;nvoid addedge(int a,int b)...
图论入门及基础概念(图篇)
图篇nn这是第一次写博客,为了下载积分而来。 n随便写些,各位大佬们多多指教。nn本次内容是关于图论的引入的,内容如下: n- 矩阵引入 n- 什么是图?其如何表示? n- 图论起源之七桥问题 n- 图论引入 n- 图论相关的基本概念 n- 图的表示nnnnn矩阵引入 nnnn 线性代数学的好的可以直接跳过, n &amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;nbsp;当然,看不懂的也可以直接跳过,这部分引入只是...
图论算法(五)--求解割点、割边(JAVA)
割点:对于一个连通图来说,如果删除某个点之后图不再连通,这个点就称为割点 n割点算法 n时间复杂度:O(N+M) n但是下面给出的算法时间复杂度为O(N^2),这是因为下面的存储结构都是邻接矩阵,这样的话用该算法就完全失去了意义,毕竟如果使用邻接矩阵完全可以通过删除一个点,然后进行DFS/BFS遍历即可了。所以在实际应用中还是要使用邻接表来保存数据,这样时间复杂度可以达到O(N+M) nInput
图论算法-求(有向)图中任意两点间所有路径
图论算法-求(有向)图中任意两点间所有路径
图论关于图的连通度
图论关于图的连通度
图论1.2子图与图的运算
子图n设G 和H为两个图,若V(H) V(G) , E(H) E(G) ,且H中边的重数不超过G中对应边的重数,则称H 是G 的子图. 记为H G 。有时又称G是H的母图。n当H G ,但H ≠ G时,则记为H G ,且称H为G的真子图。G的生成子图是指满足V(H) = V(G)的子图H。n边导出子图 假设E’是E的非空子集。以E’为边集,以E’中边的端点全体为顶点集所组成的子图称为G的由E...
图论 最大团,最大独立集
经典的NP完全问题,只有暴力解,时间复杂度O(n2^n)rn对于无向图来说rn所谓最大团, 其实就是找一个最大完全子图,最大就是包含的点最多.rn而最大独立集 == 补图的最大团rn这里使用深度优先搜索实现,对于每一个结点,考虑要与不要两种状态,则问题构成一个子集树,本质上与01背包一样,只不过多了联通性的判断rnrnrn#include nconst int SIZE = 55;nint Gra
图的色数
图论有个经典问题是这样的:给定一个无向图,把图中的结点染成尽量少的颜色,使得相邻结点颜色不同. n用d(s)表示把结点集s染色,所需的颜色数的最小值,则 nd(s) = d(s-s’) +1;其中s’是s的一个子集,并且内部没有边,即s’中任意两点不想邻.#include<cstdio>n#include<cstdlib>n#include<cstring>n#include<algorithm>
图论总结(一)二分图最大匹配
nn一、二分图最大匹配n(一)、二分图的定义性质及判定n1、定义n2、性质n3、判定nnn(二)、二分图的匹配与最大匹配nnnnnnnnnn一、二分图最大匹配nnnn(一)、二分图的定义性质及判定nnnn1、定义nn二分图又称作二部图,是图论中的一种特殊模型。 n设G=(V, E)是一个无向图。如果顶点集 V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在 X中,另一个在 Y中...
图论的存储
写在前面n邻接矩阵n概念n特点n代码n邻接表n概念n特点n代码写在前面图论的存储有好几种 n 1.邻接表(较普遍) n 2.邻接矩阵(最好写) n 3.编集数组 n 4.前向星 n 但蒟蒻萝卜水平有限,只会前面两种,而且不会STL库,所以。。。邻接矩阵概念用来存储图的二维数组(下标为点编号,数值是权值或边的有无) n特点1.在无向图中往往是沿直线i=j对称。 n2.缺点:占用空间
理论: 图论(7): 无圈图的最短路径和关键路径
总括在我们不知道图的类型(有圈无圈、有负圈无负圈)的时候, Ford算法和上文中Dijkstra算法的优化版会给予我们一种通用的解法, 但是我们要注意到他们的时间复杂度为0(E * V); 这个时间的耗费是巨大的, 所以在我们知道足够的限制条件时我们就可以细化情况, 单独提出无环图这样的一个特例, 优化出时间复杂度为O(N)的线性算法。除此之外, 无向图的应用中还有关键的一点就是关键路径的求解, 他
图论网络流入门增广路算法详解与实现
讲解nn对于求一个图起点到终点的最大网络流。nn我们可以利用增广路来求。nn将图的容量初始化,注意:读入边的信息时,必须只能单向读入,这是为了更好的增加残余网络的反向弧。nn对图所有的流量均初始化为0。nn首先我们应该寻找增广路,对于寻找一条增广路,我们可以这样做:nn第一步:我们首先通过广度搜索或者深度搜索来求出这个图的其中一条路径。并用Pre数组记录前驱。n 第二步:我们可以通过求出此路径的残...
图论(二):图的四种最短路径算法
本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法rnrnrn1),深度或广度优先搜索算法(解决单源最短路径)rn从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。rnrn下面是核心代码:rnvoid dfs(int cur, int dst){ n /
图论(五)图着色
文章目录点着色边着色应用rn把结点集或边集划分为一些不相交的子集rn点着色rnrn色数:在这里插入代码片:图G需要着色的最小颜色数量rnk着色:使用k种颜色的结点rn独立:如果S是G的结点子集,S中的任何一对结点都不相邻。独立数:最大独立集的元素数量rn可唯一k着色:图G的色数为k,且只存在一种将G的结点划分为k个子集的方式rnrn边着色rnrn正常边着色:相邻两条边着色不同rn单色三角形:只有一个颜色rn双色三角形rn矛盾...
图论(五)——以图的眼光看树&&编程求解图半径直径中心点
一、树的概念和性质rn首先借助图来阐述几个概念:rnrn树:不含圈的连通图。rn森林:不含圈的图。rn树叶:度为1的顶点。rnrn\quad由定义可知,树和森林都是简单图,且都是偶图。树有许多特有的性质,接下来我们一一揭晓。rn1、每棵非平凡树至少有两片树叶rn\quad首先我们要知道什么是平凡树呢?平凡树即平凡图,即只有一个顶点的图。且看证明:rn\quad设P=v1v2…vkP=v_1v_2…v_kP=v1​v2...
图论 —— 图的连通性
【基本概念】nn1.连通图与连通分量nn1)连通图:无向图 G 中,若对任意两点,从顶点 Vi 到顶点 Vj 有路径,则称 Vi 和 Vj 是连通的,图 G 是一连通图nn2)连通分量:无向图 G 的连通子图称为 G 的连通分量nn 任何连通图的连通分量只有一个,即其自身,而非连通的无向图有多个连通分量nn nn 以上图为例,总共有四个连通分量,分别是:ABCD、E、FG、HI。...
图论(九)——图连通度
1、点连通度和边连通度rn\quad一张连通图G最少删除多少个顶点后使得G不连通,设删除顶点数为m,则称图G的点连通度为K(G)=mK(G)=mK(G)=m。删除顶点集V′V&amp;#x27;V′后G−V′G-V&amp;#x27;G−V′不连通,则V′V&amp;#x27;V′为G的顶点割集,点数最少的顶点割集为最小顶点割,其顶点个数即为刚刚所说的点连通度。rn\quad在G中,若存在顶点割,称G...
图论经典算法(通俗易懂):最短路径和最小生成树
一、最短路问题nn求图的最短路问题,几乎是图论的必学内容,而且在算法分析与设计中也会涉及。很多书上内容, n实在没法看,我们的图论教材,更是编的非常糟糕,吐槽,为啥要用自己学校编的破教材,不过据说 n下一届终于要换书了。nn言归正传,开始说明最短路问题。nnnn1.问题描述:nn对一幅图G,我们对每一条边赋权w(e),成为一个赋权图。H是G的一个子图,则W(H) = sigma(w(e)), n也...
图论知识(一) 图,关联矩阵,邻接矩阵,拉普拉斯矩阵
版权声明:本文为博主原创文章,转载请在您的文章开始注明原址:https://blog.csdn.net/Broccoli_Lian/article/details/79755225学习CV第六天
图论02—任意两点间最短距离及路径(经典)
========================================================n求任意两点间最短距离及其路径。(万能最短路)n输入:权值矩阵,起点,终点n输出:最短距离矩阵,指定起讫点路径(经过的顶点编号)n为任意一点到其他点最短路奠定基础n========================================================
有环图求环的个数和具体节点数
这个问题一直没仔细写过,cf上做到了就写一下,就是用栈存储+回溯,很简单。n#includen#includen#includen#includen#includenusing namespace std;nconst int N = 20;nvector edge[N];nint s[N],top=0;//stl里的stack没办法遍历,所以用数组模拟nbool instack[N];nint
【matlab】《图论》-完全图仿真
% % 完全图nclose all;nnN=30;nt=0: 2*pi/N: 2*pi;nx = sin(t); y = cos(t);nfigure('Name','Point-Line');nhold on;n% plotx-y linesnfor n = 1: N-1n for m = (n+1): Nn plot(x([n,m]), y([n,m]), 'b-');
图论——寻找无向连通图割点算法
查看原文:http://www.wyblog.cn/2016/12/20/%e5%9b%be%e8%ae%ba-%e5%af%bb%e6%89%be%e6%97%a0%e7%9b%b8%e8%bf%9e%e9%80%9a%e5%9b%be%e5%89%b2%e7%82%b9%e7%ae%97%e6%b3%95/割点定义nn首先,如果一个连通的无向图中的任意顶点删除之后,剩下的图如果仍然连通,那么这
图论中最短路径问题C++实现
City.h文件 #ifndef _CITY_H_ n #define _CITY_H_ n n using namespace std; n n class City { n n public: n n // 城镇的名称 n string name; n n /
图论重造-图的存储(邻接表模版)
图论-生成树-最小生成树计数
我的天,改一个晚上才改出来,一个及其细微难以发现的逻辑错误:在做最小生成树顺便保留并查集状态的时候,不论每次是否处理的是新的种类的边(离散化后的),都应当先将fa拷贝到nowfa当中去,否则将会出现一种边没有被使用过(因为加入后会形成环),从而其相对应的nowfa均为0,导致在dfs判断所选则的边会不会形成环时得出有环的结论(因为fa[a]、fa[b]都是0),进而引起方案数出现0的情况。n#in...
图论----无向图割点-桥
无向图中割点:去掉这个点连通分量增加。rn求法:当一个点为树根时,如果他的儿子数量大于一则这个点为割点,(一棵树的根节点有数量大于一的儿子那么去掉树根,这棵树不连通)rn当这个点u的dfn[u]rn        很明显可以看出图二去掉u点连通分量没有增加,为图一去掉u点连通分量增加rnrn无向图的桥:当去掉某条边图的连通分量增加则称为此边为桥。rn求法:当碰到一个点u时dfn[u]
求连通分量-方法1(图论算法)
Descriptionnn求一个图的连通分量nnInputnnnn顶点数(n边nnOutputnn连通分量nnSample Inputnn nn5 nnn1 2 nnn3 4 nnn2 3 nnn0 0nnnn nnSample Outputnn nn4nnnnnnnnn解题思路:用深度优先搜索建立图的邻接矩阵。nnnnnnnnn程序:nnnconstnnn  maxn=100;nnnvarnnn
复杂网络(2)--图论的基本理论-最小生成树问题
连通且不含圈的无向图称为树(tree)。树中度为1的节点称为树叶,度大于1的节点称为分支点。 n若图G=(V,E)的生成子图是一棵树,则称该树为图G的生成树(spanning tree),也称支撑树,简称为图G的树。图G中属于生成树的边称为树枝(branch)。 n连通图G=(V,E),每条边上有非负权L(e)。一棵树上所有树枝上权的总和,称为这个生成树的权。具有最小权的生成树称为最小生成树(min
图论——最大团问题和最大独立集、二分图相关
主要研究二分图性质,附带最大团问题
图论第二次作业
图论第二次作业                                                                         rnrn一)五的阶乘:rn#include rnint LD (int a)rn{  rnint i,c=1;rnfor (i=1;irnc=c*i;rnprintf("%d这个数的阶乘结果为%d",a,c);rn//printf("%d"
数据结构实验之图论:AOE网上的关键路径
数据结构实验之图论十一:AOE网上的关键路径nnTime Limit: 1000MS Memory Limit: 65536KBnnSubmitStatisticnnProblem Descriptionnn    一个无环的有向图称为无环图(Directed Acyclic Graph),简称DAG图。n    AOE(Activity On Edge)网:顾名思义,用边表示活动的网,当然它也是...
图论(八)最小生成树
一个正在进行信息化建设的国家级贫困县,需要在下属9个乡镇之间架设光纤网络。为减少建设难度,光纤网主要沿着这9个乡镇之间互连的公路进行铺设。这9个乡镇之间的公路网以及相互之间的距离(单位:km)如下图所示: n n如果你是工程师,该怎样设计线路铺设方案?当然,你可以直接把所有的公路网都铺设上光缆,这样的线路总长度是247公里。但如果你是这样想的,那么我一定会怀疑你到底是不是一名工程师!你可以再设计一种
图论算法之最短路径(具有负边值的图)
1 算法介绍rnrn如果图具有负边值,那么Dijkstra算法行不通。但是把赋权的和无权的算法结合起来将会解决这个问题。开始,我们把s放到队列中。然后,在每个阶段我们让一个顶点出队。找出所有与v邻接的顶点w,使得dw > dv + cvw。然后更新dw和pw,并在w不在队列中的时候把它放到队列中。rn2 算法实现rnrn//n// main.cn// WeightedNegativen//n/
图论(十二)——偶图的匹配问题
一、图的匹配与贝尔热问题rn\quad图匹配概念:如果M是图G的边子集(不含环),且M中的任意两条边没有共同顶点,则称M是G的一个匹配或对集或边独立集。如下图所示:rnrn\quad若顶点是M中某条边的顶点,则称它为M饱和点,否则为M非饱和点。rn\quad最大匹配 M— 如果M是图G的包含边数最多的匹配,称M是G的一个最大匹配。特别是,若最大匹配饱和了G的所有顶点,称它为G的一个完美匹配。一个图一定存在...
图论-生成树-构造完全图
记得要将初始边的边权加入答案中。rn在这里插入代码片#include&amp;amp;lt;bits/stdc++.h&amp;amp;gt;rn#define rep(i,l,r) for(int i=(l);i&amp;amp;lt;=(r);i++)rn#define per(i,r,l) for(int i=(r);i&amp;amp;gt;=(l);i--)rn#define random(l,r) ((l)+rand()%((r)-(l)+1))rnusin...
图论(三)图的遍历
图建构好后,针对具体的问题,我们常常需要通盘的读取图中的信息,包括顶点(vertex)和边(edge),以及它们之间的关系。这种读取图中所有信息的方法就是图的遍历(traversal),也称为搜索(search),就是从图中某个顶点出发,沿着一些边访问图中所有的顶点,且使每个顶点仅被访问一次。遍历是很多图论算法的基础。 n n遍历需要决定从哪里开始读,依照什么顺序读,要读到哪里为止。如果遍历方法与需
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 java大神班 大数据大神班