数据结构题集（严书）图 常见习题代码

Status Insert_Vex(MGraph &G, char v)
{
  if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
  G.vexs[++G.vexnum]=v;
  return OK;
}//Insert_Vex 
Status Insert_Arc(MGraph &G,char v,char w)(v,w)
{
  if((i=LocateVex(G,v))<0) return ERROR;
  if((j=LocateVex(G,w))<0) return ERROR;
  if(i==j) return ERROR;
  if(!G.arcs[i][j].adj)
  {
    G.arcs[i][j].adj=1;
    G.arcnum++;
  }
  return OK;
}//Insert_Arc 
Status Delete_Vex(MGraph &G,char v)//懒删除，将要删除的点的行和连边全部打上标记,假设之前已经定义好一个标记数组
{
  n=G.vexnum;
  if((m=LocateVex(G,v))<0) return ERROR;
  G.vexnum--;
  for(i=0;i<n;i++)
  {for(j=0;j<m;j++)
  {if((i==m||j==m)
    flag[i][j]=1;
  }
  return OK;
}//Delete_Vex

Status Insert_Arc(ALGraph &G,char v,char w)
{
  if((i=LocateVex(G,v))<0) return ERROR;
  if((j=LocateVex(G,w))<0) return ERROR;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=j;p->nextarc=NULL;
  if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
  else
  {
    for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
      if(q->adjvex==j) return ERROR; //边已经存在
    q->nextarc=p;
  }
  G.arcnum++;
  return OK;
}//Insert_Arc 
Status Insert_Vex(ALGraph &G,char v)
{
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=j;p->nextarc=NULL,*(p->InfoType)=v;
  if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
  G.vexnum++;
  return OK;
}//Insert_Vex 
Status Delete_Arc(ALGraph &G,char v,char w)
{
  if((i=LocateVex(G,v))<0) return ERROR;
  if((j=LocateVex(G,w))<0) return ERROR;
  if(G.vertices[i].firstarc->adjvex==j)
{
  G.vertices[i].firstarc=NULL;
  return OK;
}
 for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
  if(p->nextarc->adjvex==j) 
{
  p->nextarc=p->nextarc->nextarc;
  return OK;
}
  }
  G.arcnum--;
  return OK;
}//Delete_Arc
Status Delete_Vex(ALGraph &G,char v)//在原有基础上应该加入一个删除标记flag,删除该点的出边和所有有关入边
{
  int k=0;
  if((k=LocateVex(G,v))<0) return ERROR;
  G.vertices[k].flag=1;
 for(int i=0;i<n;i++)
 if(i!=k)
 for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
  if(p->adjvex==k) 
{
  p->flag=1;
  G.arcnum--;
}
  }
  G.vexnum--;
  return OK;
}//Delete_Vex

#include <iostream>
#include <vector>
#include <string.h>
#define maxsize 1005
using namespace std;
vector<int>vec[maxsize];
int color[maxsize];
bool flag;
 
void dfs(int x){
    if(flag)return;
    color[x] = 0;
    for(int i = 0 ; i < vec[x].size() ; i++){
        if(color[vec[x][i]] == -1){
            dfs(vec[x][i]);
        } else if(color[vec[x][i]] == 0){
            flag = true;
            return;
        }
    }
    color[x] = 1;
}
int main(){
    memset(color, -1, sizeof(color));
    int max,n;
    cin >> max >> n;
    int s[max],fst[n],lst[n];
    memset(s,0,sizeof(s)),memset(fst,0,sizeof(fst)),memset(lst,0,sizeof(lst));
    for(int i=1;i<=max;i++)cin>>s[i];
    for(int i=1;i<=n;i++)cin>>fst[i],cin>>lst[i];
    for(int i = 1 ; i <=n ; i++){//建立邻接表
        if(fst[i] <= lst[i])
        for(int j = fst[i] ; j<= lst[i] ;j++)
        vec[i].push_back(s[j]);
    }
    flag = false;
    dfs(1);
    flag?cout<<"cyclic"<<endl:cout << "acyclic" <<endl;
    return 0;
}

bool visited[MAXSIZE]; 
int exist_path_len(ALGraph G,int i,int j,int k)
{
  if(i==j&&!k) return 1; //找到了一条路径,且长度符合要求
  else if(k>0)
  {
    visited[i]=1;
    for(p=G.vertices[i].firstarc;p;p=p->nextarc)
    {
      l=p->adjvex;
      if(!visited[l])
        if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
    }//for
    visited[i]=0; //递归擦除痕迹
  }//else
  return 0; 
} 

typedef struct {
                     int vex; //结点序号
                     int ecno; //结点所属的连通分量号
                   } VexInfo;
VexInfo vexs[MAXSIZE]; //记录结点所属连通分量号的数组 
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
  for(i=0;i<vexnum;i++)
    vexs[i]={i,i}; //初始状态:每一个结点都属于不同的连通分量
}//Init_VexInfo 
int is_ec(VexInfo vexs[ ],int i,int j)//判断顶点i和顶点j是否属于同一个连通分量
{
  if(vexs[i].ecno==vexs[j].ecno) return 1;
  else return 0;
}//is_ec 
void merge_ec(VexInfo &vexs[ ],int ec1,int ec2)//合并连通分量ec1和ec2
{
  for(i=0;vexs[i].vex;i++)
    if(vexs[i].ecno==ec2) vexs[i].ecno==ec1;
}//merge_ec 
void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T)
{
  Init_VexInfo(vexs,G.vexnum);
  ecnum=G.vexnum; //连通分量个数
  while(ecnum>1)
  {
    GetMinEdge(EdgeSet,u,v); //选出最短边
    if(!is_ec(vexs,u,v)) //u和v属于不同连通分量
    {
      Addto_CSTree(T,u,v); //加入到生成树中
      merge_ec(vexs,vexs[u].ecno,vexs[v].ecno); //合并连通分量
      ecnum--;
    }
    DelMinEdge(EdgeSet,u,v); //从边集中删除
  }//while
}//MinSpanTree_Kruscal 
void Addto_CSTree(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
   p=Locate(T,i)；//定位到树中i顶点的指针     	q=(CSTNode*)malloc(sizeof(CSTNode));
   q->data=j;
  if(!p->firstchild) 
    p->firstchild=q; 
  else
  {
    for(r=p->firstchild;r->nextsib;r=r->nextsib);
    r->nextsib=q; 
  }
}//Addto_CSTree

void Fill_MPL(ALGraph &G)
{
  FindIndegree(G,indegree);
  for(i=0;i<G.vexnum;i++)
    if(!indegree[i]) Get_MPL(G,i);//从每一个零入度顶点出发构建MPL域
}//Fill_MPL 
int Get_MPL(ALGraph &G,int i)//DFS函数
{
  if(!G.vertices[i].firstarc)//特判零出度
  {
    G.vertices[i].MPL=0;
    return 0; //零出度顶点
  }
  else
  {
    max=0;
    for(p=G.vertices[i].firstarc;p;p=p->nextarc)
    {
      j=p->adjvex;
      if(G.vertices[j].MPL==0) k=Get_MPL(G,j);
      if(k>max) max=k; //求其直接后继顶点MPL的最大者
    }
    return G.vertices[i]=max+1;
  }//else
}//Get_MPL