图论建图

图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

1.邻接表建图:

直接开一个N*N的矩阵如果i,j相连则将二维矩阵赋值,否则则为INF。

虽然简单直观但是遍历效率过低, “并且不能存储重边”, 准确的说是不能覆盖重边,应该说这是邻接表建图和链式前向星的弊病所在。

遇到点较稀疏的图时空间利用率过低,时间复杂度为O(N*N)

#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 0x3f3f3f3f
using namespace std;
int N,M;
struct node{
  int y,w=maxn;//初始化,没有连接的边默认为maxn
  node(int y1,int w1){y=y1;w=w1;}//构造函数
};
vector<node>G[105];
int main(){
        int i,j,x,y,z;
        cin>>N>>M;   //构图
    while(scanf("%d%d%d",&x,&y,&z)!=EOF){
             G[x].push_back((node){y,z});
         }
        for(int i=1;i<=N;i++)
       for(int j=0;j<G[i].size();j++)
        printf("%d %d %d\n",i,G[i][j].y,G[i][j].w);
      return 0;
}

vector + pair ,如果会用pair的话就不用建结构体了,美滋滋..

typedef pair<int,int> pii;
vector<pii>G[maxn];
  //vector<pair<int,int> > G[maxn];
  //加边:
G[u].push_back(make_pair(v,w));
  //遍历从p点出发的边
for(int i=0;i<G[p].size();i++){
    int v=G[p][i].first;
    int w=G[p][i].second;
}

2.链式前向星

1.结构

edge存边,edge[i]表示第i条边

head[i]存以i为起点的第一条边(在edge中的下标)

struct EDGE{
       int next=0;   //下一条边的存储下标(默认0)
       int to;     //这条边的终点
       int w;      //权值
};
EDGE edge[500010];

3.增边

若以点i为起点的边新增了一条,在edge中的下标为j.

那么edge[j].next=head[i];然后head[i]=j.

即每次新加的边作为第一条边,最后倒序遍历

void Add(int u, int v, int w) {  //起点u, 终点v, 权值w
      //cnt为边的计数,从1开始计
      edge[++cnt].next = head[u];
      edge[cnt].w = w;
      edge[cnt].to = v;
      head[u] = cnt;    //第一条边为当前边
}

4. 遍历

遍历以st为起点的边

for(int i=head[st]; i!=0; i=edge[i].next)

i开始为第一条边,每次指向下一条(以0为结束标志) (若下标从0开始,next应初始化-1)

#include <iostream>
using namespace std;

#define MAXM 500010
#define MAXN 10010

struct EDGE{
      int next;   //下一条边的存储下标
  nt to;     //这条边的终点
      int w;      //权值
};
EDGE edge[MAXM];

int n, m, cnt;
int head[MAXN];  //head[i]表示以i为起点的第一条边

void Add(int u, int v, int w) {  //起点u, 终点v, 权值w
      edge[++cnt].next = head[u];
      edge[cnt].w = w;
      edge[cnt].to = v;
      head[u] = cnt;    //第一条边为当前边
}

void Print() {
      int st;
      cout << "Begin with[Please Input]: \n";
      cin >> st;
      for(int i=head[st]; i!=0; i=edge[i].next) {//i开始为第一条边,每次指向下一条(以0为结束标志)若下标从0开始,next应初始化-1
          cout << "Start: " << st << endl;
          cout << "End: " << edge[i].to << endl;
          cout << "W: " << edge[i].w << endl << endl;
      }
}

int main() {
      int s, t, w;
      cin >> n >> m;
      for(int i=1; i<=m; i++) {
          cin >> s >> t >> w;
          Add(s, t, w);
      }
      Print();
      return 0;
}

我知道在座的有很多图论大佬,但我想说,不喜勿喷,谢谢大家的关爱

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

    Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

    ACM算法日常
  • 不同路径(动态规划)- leetcode 62

    最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感...

    ACM算法日常
  • 集合中随机取不重复的索引

    有时候希望从一个集合中随机取n个元素不重复 那么就取到这n个数字的索引 public static int[] GetRandomArray(int Numb...

    用户1055830
  • 洛谷P4054 [JSOI2009]计数问题(二维树状数组)

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-4 使用函数求素数和

    其中函数prime当用户传入参数p为素数时返回1,否则返回0;函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题4-6 水仙花数

    水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

    C you again 的博客
  • 排序算法——一篇文章搞懂常用的排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记...

    海盗船长
  • OpenCV中积分图介绍与应用

    OpenCV中积分图函数与应用 一:图像积分图概念 积分图像是Crow在1984年首次提出,是为了在多尺度透视投影中提高渲染速度。随后这种技术被应用到基于NC...

    OpenCV学堂

扫码关注云+社区

领取腾讯云代金券