图基础模版

_pzy · 2025-10-18 08:57:23 · 算法·理论

图存储

链式前向星

核心思想

通过链表存储边

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,k;

struct abc
{
    long long to,size,next;
}a[100005];
long long head[100005],cnt; 
void add(long long x,long long y,long long z)
{
    cnt++;
    a[cnt].to=y;
    a[cnt].next=head[x];
    a[cnt].size=z;
    head[x]=cnt;
    return ;
}
//链式前向星核心 

int main()
{
    cin>>n>>m>>k;
    //k为1则是有向图
    //k为0则是无向图 
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        if(k!=1)
        {
            add(y,x,z);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=0;j=a[j].next)
        {
            cout<<i<<" "<<a[j].to<<" "<<a[j].size<<endl; 
        }
        //链式前向星遍历
        /*
        作用：
        找出以i为头的边(有向图)
        /
        找出连接i的所有边(无向图) 
        */ 
    }
    return 0;
} 

图直径

核心思想

• 直径两端点必为叶子节点
• 任意点的最远点必为直径端点
• 直径中点即为树的中心

  代码

  
  #include<iostream>
  using namespace std;
  long long n;

struct abc { long long to,size,next; }a[100005]; long long head[100005],cnt; void add(long long x,long long y,long long z) { cnt++; a[cnt].to=y; a[cnt].next=head[x]; a[cnt].size=z; head[x]=cnt; return ; }//链式前向星，见上文

long long fa /farthest/,lo /longest/; void find(long long now,long long father,long long dep) { if(dep>lo) { lo=dep; fa=now; } for(int i=head[now];i!=0;i=a[i].next) { if(a[i].to!=father) { find(a[i].to,now,dep+a[i].size); } } } long long get() { find(1,-1,0); long long t=fa; lo=0; find(t,-1,0); return lo; } //树直径核心

int main() { cin>>n; for(int i=1;i<=n-1;i++) { long long x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } cout<<get(); return 0; }

::::warning[警告]{open}
本段代码用万能头会ce。
::::

[![pAwNWCV.png](https://s21.ax1x.com/2024/10/25/pAwNWCV.png)](https://www.luogu.com.cn/article/amp4dxk1)