泉州暑假集训Day 8

PS: This is a note.

图论基础

图的概念

偷懒一波~ 😄

segmentfault上某大佬的讲解

知乎上某大佬的讲解

补充:

• 节点的度: 无向图中与节点相连的边的数目,称为节点的度
• 节点的入度: 在有向图中,以这个节点为终点的有向边的数目
• 节点的出度: 在有向图中,以这个节点为起点的有向边的数目

邻接表

邻接表编码

1. 利用结构体+指针来实现(原始,不推荐)
2. 利用STL库vector+结构体来实现

实现步骤

1. 结构体
2. 创建图
   1. 顶点和边数，顶点需要用一维数组保存
   2. 获取顶点的下标，因为链接结点中的index域是顶点的下标值。
   3. 创建结点，通过头插法(或尾插法)把结点链接到头结点的尾部
3. 打印

详细可见: TMusketeer的博客

邻接表代码示例

#include<bits/stdc++.h>
using namespace std;
int n,m,j,k,w;
struct node{
    int to;
    int w;
};
vector<node> v[100001];
int main(){
    node e;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&j,&k,&w);
        e.to=k;
        e.w=w;
        v[j].push_back(e);
        e.to=j;
        v[k].push_back(e);
    }
    for(int i=1;i<=n;i++)
    {
        for(vector<node>::iterator l=v[i].begin();k!=v[i].end();k++){
            node t=*k;
            printf("%d %d %d\n",i,t.to,t.w);
        }
    }
    return 0;
}

更详细可见OI-Wiki