模板 图论

存图

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int Maxv=1000;
struct node{
    int v;
    node* next;
};
int n,e;
typedef node* link;
link g[Maxv];
bool visited[Maxv];
queue<int> q;
void Insert(int u,int v){//insert edge(u,v) to  Adjacency list
    link x;
    x=new node;
    x->v=v;x->next=g[u];g[u]=x;
}
void init(){
    int u,v;
    cin>>n>>e;
    memset(visited,0,sizeof(visited));
    memset(g,0,sizeof(g));
    for(int i=0;i<e;i++){
        cin>>u>>v;
        Insert(u,v);
        Insert(v,u);
    }
    return ;
}
void BFS(int v){
    cout<<v<<" ";
    visited[v]=1;
    q.push(v);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(link x=g[i];x!=NULL;x=x->next){
            int u=x->v;
            if(!visited[u]){
                cout<<u<<" ";
                visited[u]=1;
                q.push(u);
            }
        }
    }
}
int main(){
    init();
    memset(visited,0,sizeof(visited));
    for(int i=1;i<=n;i++) if(!visited[i]) {
        BFS(i);
        cout<<endl;
    }
    return 0;
}
/*******************************************************/
void DFS(int v){
    cout<<v<<" ";
    visited[v]=1;
    for(link x=g[v];x!=NULL;x=x->next){
        int u=x->v;
        if(!visited[u]) DFS(u);
    } 
}
int main(){
    init();
    for(int i=1;i<=n;i++) if(!visited[i]){
        DFS(i);
        cout<<endl;
    } 
    
}

#include<iostream>
#include<queue>
#include<stack>
#include<stdlib.h>
#define MAX 100
using namespace std;

typedef struct 
{
    int edges[MAX][MAX];    //邻接矩阵
    int n;                  //顶点数
    int e;                  //边数
}MGraph;

bool visited[MAX];          //标记顶点是否被访问过

void creatMGraph(MGraph &G)    //用引用作参数
{
    int i,j;
    int s,t;                 //存储顶点编号
    int v;                   //存储边的权值
    for(i=0;i<G.n;i++)       //初始化
    {
        for(j=0;j<G.n;j++)
        {
            G.edges[i][j]=0;
        }
        visited[i]=false;
    }
    for(i=0;i<G.e;i++)      //对矩阵相邻的边赋权值
    {
        scanf("%d %d %d",&s,&t,&v);   //输入边的顶点编号以及权值
        G.edges[s][t]=v;
    }
}

void DFS(MGraph G,int v)      //深度优先搜索
{
    int i;
    printf("%d ",v);          //访问结点v
    visited[v]=true;
    for(i=0;i<G.n;i++)       //访问与v相邻的未被访问过的结点
    {
        if(G.edges[v][i]!=0&&visited[i]==false)
        {
            DFS(G,i);
        }
    }
}

void DFS1(MGraph G,int v)   //非递归实现
{
    stack<int> s;
    printf("%d ",v);        //访问初始结点
    visited[v]=true;
    s.push(v);              //入栈
    while(!s.empty())
    {
        int i,j;
        i=s.top();          //取栈顶顶点
        for(j=0;j<G.n;j++)  //访问与顶点i相邻的顶点
        {
            if(G.edges[i][j]!=0&&visited[j]==false)
            {
                printf("%d ",j);     //访问
                visited[j]=true;
                s.push(j);           //访问完后入栈
                break;               //找到一个相邻未访问的顶点，访问之后则跳出循环
            }
        }
        if(j==G.n)                   //如果与i相邻的顶点都被访问过，则将顶点i出栈
            s.pop();
    }
}

void BFS(MGraph G,int v)      //广度优先搜索
{
    queue<int> Q;             //STL模板中的queue
    printf("%d ",v);
    visited[v]=true;
    Q.push(v);
    while(!Q.empty()) 
    {
        int i,j;
        i=Q.front();         //取队首顶点
        Q.pop();
        for(j=0;j<G.n;j++)   //广度遍历
        {
            if(G.edges[i][j]!=0&&visited[j]==false)
            {
                printf("%d ",j);
                visited[j]=true;
                Q.push(j);
            }
        }
    }
}

int main(void)
{
    int n,e;    //建立的图的顶点数和边数
    while(scanf("%d %d",&n,&e)==2&&n>0)
    {
        MGraph G;
        G.n=n;
        G.e=e;
        creatMGraph(G);
        DFS(G,0);
        printf("
");
    //    DFS1(G,0);
    //    printf("
");
    //    BFS(G,0);
    //    printf("
");
    }
    return 0;
}

#define MAX_VERTEX_NUM 20  
#include<iostream>  
#include<string>  
using namespace std;  
  
template<class T>  
int Locate_Vex(T G,string x) //定位顶点位置  
{  
    for(int k=0;G.vexs[k]!=x;k++);  
    return k;  
}  
  
//邻接矩阵存储图  
struct MGraph  
{  
    string vexs[MAX_VERTEX_NUM];//顶点数组  
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵  
    int vexnum;//顶点数目  
    int arcnum;//边数目  
};  
  
void CreateUDN_MG(MGraph &G)  
{  
    //采用邻接矩阵表示法，构造无向网  
    cin>>G.vexnum>>G.arcnum;  
    for(int i=0;i<G.vexnum;i++)  
        cin>>vaxs[i];  
      
    for(i=0;i<G.vexnum;i++)  
        for(int j=0;j<G.vexnum;j++)  
            G.arcs[i][j]=-1;  
    //上面是初始化邻接矩阵，-1表示两点间边的权值为无穷大  
      
    for(int k=0;k<G.arcnum;k++)  
    {  
        string v1,v2;  
        int w;  
        cin>>v1>>v2>>w;  
        i=Locate_Vex(G,v1);  
        j=Locate_Vex(G,v2);  
        while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)  
        {  
            cout<<"结点位置输入错误,重新输入: ";  
            cin>>v1>>v2>>w;  
            i=Locate_Vex(G,v1);  
            j=Locate_Vex(G,v2);   
        }  
        G.arcs[i][j]=w;  
        G.arcs[j][i]=G.arcs[i][j]; //置对称边  
    }  
}  
  
//邻接表存储图  
//表结点  
struct ArcNode  
{  
    int adjvex; //弧所指向顶点的位置  
    ArcNode *nextarc;// 指向下一条弧  
};  
  
//头结点  
typedef struct VNode  
{  
    string data;//顶点名  
    ArcNode *firstarc;//指向第一条关联顶点的弧  
}AdjList[MAX_VERTEX_NUM];  
  
struct ALGraph  
{  
    AdjList vertices;//头结点数组  
    int vexnum;  
    int arcnum;  
};  
  
void CreateDG_ALG(ALGraph &G)  
{  
    //采用邻接表存储表示，构造有向图G  
    string v1,v2;  
    int i,j,k;  
    cin>>G.arcnum>>G.vexnum;  
      
    //构造头结点数组  
    for(i=0;i<G.vexnum;i++)  
    {  
        cin>>G.vertices[i].data;  
        G.vertices[i].firstarc=NULL;  
    }  
  
    //输入各弧并构造邻接表  
    for(k=0;k<G.arcnum;k++)  
    {  
        cin>>v1>>v2;  
        i=Locate_Vex(G,v1);  
        j=Locate_Vex(G,v2);  
        while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)  
        {  
            cout<<"结点位置输入错误,重新输入: ";  
            cin>>v1>>v2;  
            i=Locate_Vex(G,v1);  
            j=Locate_Vex(G,v2);   
        }  
      
        ArcNode *p=new ArcNode;  
        p->adjvex=j;  
        p->nextarc=NULL;  
        p->nextarc=G.vertices[i].firstarc;  
        G.vertices[i].firstarc=p;  
    }  
}  
  
//十字链表方式存储有向图  
//弧结点  
struct ArcBox  
{  
    int tailvex,headvex;//弧结点头尾结点位置  
    ArcBox *hlink,*tlink;//弧头和弧尾相同的弧的链域  
};  
  
//顶点结点  
struct VexNode  
{  
    string data;  
    ArcBox *firstin,*firstout;//顶点第一条入弧和出弧  
};  
  
struct OLGraph  
{  
    VexNode xlist[MAX_VERTEX_NUM];  
    int vexnum;  
    int arcnum;  
};  
  
void CreateDG_OLG(OLGraph &G)  
{  
    //采用十字链表存储表示，构造有向图G  
    string v1,v2;  
    int i,j,k;  
    cin>>G.vexnum>>G.arcnum;  
    for(i=0;i<G.vexnum;i++)  
    {  
        cin>>G.xlist[i].data;  
        G.xlist[i].firstin=NULL;  
        G.xlist[i].firstout=NULL;  
    }  
    for(k=0;k<G.arcnum;k++)  
    {  
        cin>>v1>>v2;  
        i=Locate_Vex(G,v1);  
        j=Locate_Vex(G,v2);  
      
        while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)  
        {  
            cout<<"结点位置输入错误,重新输入: ";  
            cin>>v1>>v2;  
            i=Locate_Vex(G,v1);  
            j=Locate_Vex(G,v2);   
        }         
  
        ArcBox *p=new ArcBox;  
        p->tailvex=i;  
        p->headvex=j;  
        p->hlink=G.xlist[j].firstin;  
        p->tlink=G.xlist[i].firstout;  
        G.xlist[i].firstout=G.xlist[j].firstin=p;  
    }  
}  
          
//邻接多重表存储  
//边结点  
struct EBox  
{  
    int mark;//标志域，指示该边是否被访问过(0:没有 1:有)  
    int ivex,jvex;//该边关联的两个顶点的位置  
    EBox *ilink,*jlink;//分别指向关联这两个顶点的下一条边  
};  
  
//顶点结点  
struct VexBox  
{  
    string data;  
    EBox *firstedge;//指向第一条关联该结点的边  
};  
  
struct AMLGraph  
{  
    VexBox adjmulist[MAX_VERTEX_NUM];  
    int vexnum;  
    int arcnum;  
};  
  
void CreateUDG_AML(AMLGraph &G)  
{  
    //用邻接多重表存储，构造无向图G  
    string v1,v2;  
    int i,j,k;  
    cin>>G.vexnum>>G.arcnum;  
    for(i=0;i<G.vexnum;i++)  
    {  
        cin>>G.adjmulist[i].data;  
        G.adjmulist[i].firstedge=NULL;  
    }  
  
    for(k=0;k<G.arcnum;k++)  
    {  
        cin>>v1>>v2;  
        i=Locate_Vex(G,v1);  
        j=Locate_Vex(G,v2);  
          
        while(i<0|| i>G.vexnum-1 || j<0 || j>G.vexnum-1)  
        {  
            cout<<"结点位置输入错误,重新输入: ";  
            cin>>v1>>v2;  
            i=Locate_Vex(G,v1);  
            j=Locate_Vex(G,v2);   
        }  
  
        EBox *p=new EBox;  
        p->ivex=i;  
        p->jvex=j;  
        p->ilink=G.adjmulist[i].firstedge;  
        p->jlink=G.adjmulist[j].firstedge;  
        p->mark=0;  
        G.adjmulist[i].firstedge=G.adjmulist[j].firstedge=p;  
    }  
}  

最短路

#include<cstdio>
#include<cstring>
#define MAXN 1005
using namespace std;
int n,m,s;
int d[MAXN][MAXN];
inline int Min(int a,int b){return a<b?a:b;}
inline void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                d[i][j]=Min(d[i][j],d[i][k]+d[k][j]);
            }
}
int main(){
    //freopen("floyd.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=0x3fffffff;
    for(int i=1;i<=m;i++) {
        int x,y,z;scanf("%d%d%d",&x,&y,&z); d[x][y]=Min(d[x][y],z);
    }
    for(int i=1;i<=n;i++) d[i][i]=0; 
    floyd();
    for(int i=1;i<=n;i++) printf("%d ",d[s][i]==0x3fffffff?2147483647:d[s][i]);
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
const int maxN=10005,maxM=500005;
struct edge{int u,v,w;}e[maxM];
int top=0,head[maxN],to[maxM],nxt[maxM],val[maxM];
void add(int u,int v,int w){top++;to[top]=v,nxt[top]=head[u],val[top]=w;head[u]=top;}
struct queue{
    int head,tail,data[maxM];
    queue(){head=1,tail=0;}
    void push(int x){data[tail=(tail+1)%maxM]=x;}
    void pop(){head=(head+1)%maxM;}
    int front(){return data[head];}
    bool empty(){return tail<head;}
}q;
int d[maxN];
void defense(edge *buf,int len){
    srand(233333);
    for(int i=0;i<len;i++)
        std::swap(buf[rand()%len],buf[rand()%len]);
}
void spfa(int u){
    memset(d,0x3f,sizeof(d));
    d[u]=0; q.push(u);
    while(!q.empty()){
        int tmp=q.front(),now=head[tmp]; q.pop();
        while(now!=0){
            if(d[to[now]]>d[tmp]+val[now]){
                d[to[now]]=d[tmp]+val[now];
                q.push(to[now]);
            }
            now=nxt[now];
        }
    }
}
int main(){
//    freopen("1.in","r",stdin);
    int n,s,t; scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=s;i++){int x,y,z;scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);}
    for(int i=1;i<=s;i++)add(e[i].u,e[i].v,e[i].w);
    defense(e+1,s);
    spfa(t);
    for(int i=1;i<=n;i++) printf("%d ",d[i]==0x3f3f3f3f?2147483647:d[i]);
}

#include<stdio.h>
#include<string.h>
const int maxN=10005,maxM=500005;
int top=0,head[maxN],to[maxM],nxt[maxM],val[maxM];
void add(int u,int v,int w){top++;to[top]=v,nxt[top]=head[u],val[top]=w;head[u]=top;}
struct queue{
    int head,tail,data[maxM];
    queue(){head=1,tail=0;}
    void push(int x){data[tail=(tail+1)%maxM]=x;}
    void pop(){head=(head+1)%maxM;}
    int front(){return data[head];}
    bool empty(){return tail<head;}
}q;
int d[maxN];
void spfa(int u){
    memset(d,0x3f,sizeof(d));
    d[u]=0; q.push(u);
    while(!q.empty()){
        int tmp=q.front(),now=head[tmp]; q.pop();
        while(now!=0){
            if(d[to[now]]>d[tmp]+val[now]){
                d[to[now]]=d[tmp]+val[now];
                q.push(to[now]);
            }
            now=nxt[now];
        }
    }
}
int main(){
//    freopen("1.in","r",stdin);
    int n,s,t; scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=s;i++){
       int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);    
    }
    spfa(t);
    for(int i=1;i<=n;i++) printf("%d ",d[i]==0x3f3f3f3f?2147483647:d[i]);
}

#include<cstdio>
#include<queue>
#define MAXN 1000005
#define inf 0x7fffffff
#define debug 0
using namespace std;
#if debug
    int cnt_dij=0;
#endif
typedef pair<int,int> pa;
int n,m,s;
struct edge{
    int to,nxt,val;
}e[MAXN];
int head[MAXN],cnt=0;
inline void add(int u,int v,int w){
    cnt++,e[cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;e[cnt].val=w;
}
int d[MAXN];
inline void dij(){
    priority_queue<pa,vector<pa>,greater<pa> >q;
    fill(d,d+n+1,inf);d[s]=0;q.push(pa(s,0));  
    while(!q.empty()){
        pa p=q.top();q.pop();
        int val=p.second;
        //if(d[val]<p.first) continue;
        for(int i=head[p.first];i;i=e[i].nxt){
            int to=e[i].to;
            if(d[to]>val+e[i].val) d[to]=val+e[i].val,q.push(pa(to,d[to]));
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++) {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);
    }
    dij();
    for(int i=1;i<=n;i++) printf("%d ",d[i]);
    return 0;
}

//bellman_ford 
for(int i=0;i<n;i++) d[i]=INF;
d[0]=0;
for(int k=0;k<n-1;k++){//迭代n-1次 
    for(int i=0;i<m;i++)//检查每条边 
    {
      int x=u[i],y=v[i];
      if(d[x]<INF) d[y]=min(d[y],d[x]+w[i]);//松驰 
    } 
} 
//SPFA 
Bool bellman_ford(int s){
    queue<int> Q; 
    memset(inq,0,sizeof(inq));//inq[i]用于标记i点是否在队列中 
    memset(cnt,0,sizeof(cnt));//cnt[i]用于记录i点进队次数 
    for(int i=0;i<n;i++)d[i]=INF;//初始化d数组 
    d[s]=0;inq[s]=true;//源点到自己最短路长为0，s点进队 
    Q.push(s)；
    
    while(!Q.empty()){            //当队列非空时 
        int u=Q.front();Q.pop();//取队头元素给u 
        inq[u]=false;            //u点不在队 
        for(int i=0;i<G[u].size();i++){//扫描u点出发所有边 
            Edge &e=edges[G[u][i]];
            if(d[u]<INF && d[e.to]>d[u]+e.dist){//如果可以通过u松驰 
                d[e.to]=d[u]+e.dist;//松驰 
                if(!inq[e.to]){        //如果e.to不在队中，将它入队 
                    Q.push(e.to);inq[e.to]=true;
                    //如果e.to入队次数>n,则存在负环，返回false 
                    if(++cnt[e.to])>n) return false; 
                }
            }
        }
    }
    return true; 
} 

//floyd 
int d[Max_v][Max_v];
//d[u][v]表示边e=(u,v)的权值(不存在时设为INF，不过d[i][i]=0 
int V;    //顶点数 

void warshall_floyd(){
    for (int k=0;k<V;k++){
        for(int i=0;i<V;i++)
          for(int j=0;j<V;j++)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    } 
}

最小生成树

#include<stdio.h>
#include<algorithm> 
using namespace std;
const int Max_E=10000;
struct edge{int u;int v;int cost;};        //边结构 
bool comp(const edge& e1,const edge& e2){
    return e1.cost<e2.cost;
}
edge es[Max_E];    //边集 
int fa[Max_E];     //并查集 
int V,E;        //顶点数与边数 
void init_union_find(int n){//初始化并查庥 
    for(int i=0;i<n;i++) fa[i]=i;
}
int find(int x){//并查集中查找操作 
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);    
} 
void unite(int x,int y){//并操作 
    int fx=find(x),fy=find(y);
    if(fx==fy) return ;
    fa[fx]=fy;
}
int kruskal(){
    sort(es,es+E,comp);    //按edge.cost的顺序从小到大排序 
    init_union_find(V);    //初始化并查集，每个点就是一个并查集 
    int res=0;
    for(int i=0;i<E;i++){//扫描每一条边 
      edge e=es[i];    
      if(find(e.u)!=find(e.v)){//如果e边的起点与终点不在同一个集合 
            unite(e.u,e.v);        //将这条边加入生成树，将它们所在集合合并 
            res+=e.cost;
      }
    }
    return res; 
}
int main(){
    int u,v,cost;
    scanf("%d%d",&V,&E);
    for(int i=0;i<E;i++){
        scanf("%d%d%d",&u,&v,&cost);
        es[i]=edge{u,v,cost};
    }
    printf("%d
",kruskal());
    return 0;
}

#include<iostream>
using namespace std;
const int Max_v=1000;        //最大顶点数 
const int INF=0x7fffffff;     
int cost[Max_v][Max_v];        //邻接矩阵 
int mincost[Max_v];            //从集合X出发的边到每个顶点的最小权值。 
bool used[Max_v];            //顶点i是否包含在集合Xk  
int V;                        //顶点数 
int prim(){
    fill(mincost,mincost+V,INF);         
    fill(used,used+V,false);
    mincost[0]=0;
    int res=0;
    while(true){
        int v=-1;
        //从不属于X的顶点中选取从X到其权值最小的顶点
        for(int u=0;u<V;u++){
            if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
        }
        if(v==-1) break;
        used[v]=true;
        res+=mincost[v];
        for(int u=0;u<V;u++) 
        if (cost[v][u])mincost[u]=min(mincost[u],cost[v][u]); 
    }
    return res;
}
int main(){
    cin>>V;
    for(int i=0;i<V;i++)
      for(int j=0;j<V;j++)
      cin>>cost[i][j];
    cout<<prim();
    return 0;
}

//最小生成树Prim算法 用上了堆（优先队列）优化  vijos 1190
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max_v=1001;
struct node{        //优先队列（最小堆）结构 
    int no,cost;    //顶点编号、顶点到生成树的权 
    bool operator <(const node &a)const{
      return cost > a.cost;
    }
};
struct data{int to,w;};        //邻接表结点结构 
vector<data> G[Max_v];        //邻接表头结点 
int n,m,ans,mincost[Max_v];    //n,m分别表示顶点数与边数，mincost[i]为目前生成树到i的权 
bool mark[Max_v];            //标志数组，mark[i]标志i是否已经加入生成树 
priority_queue<node> q;        //优先队列q是一个最小堆，存储每个点编号及最小权 
void Ins(int u,int v,int w){//往图中插入一条边(u,v,w) 
    data e;    e.to=v;e.w=w;G[u].push_back(e);
}
void init(){                //输入n与m及m条边，初始化建图 
    int i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        Ins(a,b,c);Ins(b,a,c);
    }
}
void prim_queue(){
    int num=0,now;
    memset(mincost,127,sizeof(mincost));
    mincost[1]=0;//从1号点开始，将1号点加入生成树T，1号点到t的最小权为0 
    node P={1,0};q.push(P);//将（1，0）加入优先队列 
    while(!q.empty()){        //当队列非空 
        P=q.top();q.pop();    //取优先队列中cost值最小的点now
        now=P.no;            
        if(mark[now]) continue;//如果now已经在生成树中，继续循环 
        mark[now]=1;            //将now点加入生成树T 
        ans+=mincost[now];        //答案加now到树的权 
        for(int i=0;i<G[now].size();i++){//更新与now相邻那些点的mincost 
            data e=G[now][i];
            if(e.w<mincost[e.to]){        //如果(now,e.to)的权w小球mincost[e.to] 
                mincost[e.to]=e.w;        //修改mincost[e.to],并将（e.to,e.w)入优先队列 
                P.no=e.to;P.cost=e.w;
                q.push(P);
            }
        }
    }
    printf("%d
",ans);
}
int main(){
    init();
    prim_queue();
    return 0;
}