专栏首页glm的全栈学习之路数据结构题集(严书)图 常见习题代码

数据结构题集(严书)图 常见习题代码

7.15

//邻接矩阵实现图的增删点、边

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

7.16 //邻接链表实现图的增删点、边

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

7.25 /*假设对有向图中n个顶点进行自然编号并以三个数组s[1..max],fst[1..n],lst[1..n]表示之其中数组s存放每个顶点的 后继顶点的信息第i个顶点的后继顶点存放在s中下表从fst[i]起到lst[i]的分量中(i=1,2,...n)若fst[i]>lst[i]则第i个顶 点无后继顶点,试编写判别该有向图中是否存在回路的算法*/

#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;
}

7.27 //采用邻接链表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法

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; 
} 

7.33 //已知无向图的边集存放在某个类型为EdgeSetType的数据结构EdgeSet 中(没有端点相重的环边),并在此结构上已定义两种基本运算: (1)函数GetMinEdge(EdgeSet, u, v):若EdgeSet非空,则必存在最小边,变参u和v分别含最小边上两顶点,并返回true;否则返回false; (2)过程DelMinEdge(EdgeSet, u, v):从EdgeSet中删除依附于顶点u和v的最小边。 试在上述结构上实现求最小生成树(以孩子-兄弟链表表示)的克鲁斯卡尔算法。

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

7.36 //在图的邻接表存储结构中,为每个顶点增加一个MPL域。试写一算法,求有向无环图G的每个顶点出发的最长路径的长度,并存入其MPL域。请给出算法的时间复杂度。

时间复杂度:o(n+e)

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 

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT (Basic Level) Practice (中文)1023 组个最小数 (20 分)

    给定数字 0-9 各若干个。你可以以任意顺序排列这些数字,但必须全部使用。目标是使得最后得到的数尽可能小(注意 0 不能做首位)。例如:给定两个 0,两个 1,...

    glm233
  • PAT (Basic Level) Practice (中文)1016 部分A+B (15 分)

    正整数 A 的“D​A​​(为 1 位整数)部分”定义为由 A 中所有 D​A​​ 组成的新整数 P​A​​。例如:给定 A=3862767,D​A​​=6,则...

    glm233
  • PAT (Basic Level) Practice (中文)1046 划拳 (15 分)

    划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为:每人口中喊出一个数字,同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和,谁...

    glm233
  • Rotate Image

    问题:矩阵顺时针旋转90度 class Solution { public: bool dfs(vector<vector<int> > &matrix...

    用户1624346
  • Leetcode 74. Search a 2D Matrix

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Search a 2D Matrix

    问题:二维数组中是否存在一个数 class Solution { public: bool dfs(vector<vector<int> > &matr...

    用户1624346
  • PHP10段常用功能代码

    用户7657330
  • C 语言作业 - 1- 指针使用与冒泡排序

    大致意思就是对一个字符数组进行排序;比较的方法有两种,一种是基于 ASCII 码的大小,一个是基于整数值的大小;最后用冒泡排序来测试这两种比较方法。

    caoqi95
  • 51Nod-1621-花钱买车牌

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> using namespace std; const int ...

    f_zyj
  • Data Structures and Algorithms Basics(017):String

    用户5473628

扫码关注云+社区

领取腾讯云代金券