考研数据结构关于图的操作

邻接表建图输出每个节点的度

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000;

//定义边表节点结构
typedef struct ArcNode{
  int adjv; //与顶点相连的邻接点下标
  struct ArcNode * next;  //指向顶点的下一个邻接点
}ArcNode;

//定义顶点表节点结构
typedef struct VNode{
  int data;
  ArcNode *first; //边表头节点,指向顶点的第一个邻接点
}VNode;

typedef struct AGraph{
  VNode VList[maxn];
  int n;
  int e;
}AGraph;


int findnode(AGraph *g, int c){
  for(int i = 0; i < g->n; i ++){
    if(g->VList[i].data == c)  {  return i;}
  }
  return -1;
}

void createAgraph(int n, int m){
  int l = 0, k = 0, x = 0, y = 0;
  AGraph *g = (AGraph *)malloc(sizeof(AGraph));
  g -> n = n;
  g -> e = m;
  for(int i = 0; i < n; i ++){
    scanf("%d", &(g -> VList[i].data));
    g -> VList[i].first = NULL;
  }

  for(int j = 0; j < m; j ++){
    scanf("%d%d", &x, &y);
    l = findnode(g, x);
    k = findnode(g, y);
    ArcNode *arcl = (ArcNode *)malloc(sizeof(ArcNode));
    arcl -> adjv = k;
    arcl -> next = g -> VList[l].first;
    g -> VList[l].first = arcl;

    ArcNode *arck = (ArcNode *)malloc(sizeof(ArcNode));
    arck -> adjv = l;
    arck -> next = g -> VList[k].first;
    g -> VList[k].first = arck;
  }

  //输出每个节点的度
  for(int i = 0; i < g->n; i ++){
    int s = 0;
    for(ArcNode *p = g->VList[i].first;  p != NULL; p = p->next) s ++;
    if(i == 0)  cout << s;
    else  cout << " " << s;
  }

}


int main(){
  int n, m;
  scanf("%d%d", &n, &m);
  createAgraph(n, m);
  return 0;
}

邻接矩阵转邻接表

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100;

//定义边表节点结构
typedef struct ArcNode{
  int adjv; //与顶点相连的邻接点下标
  struct ArcNode * next;  //指向顶点的下一个邻接点
}ArcNode;

//定义顶点表节点结构
typedef struct VNode{
  int data;
  ArcNode *first; //边表头节点,指向顶点的第一个邻接点
}VNode;

typedef struct AGraph{
  VNode VList[maxn];
  int n;
  int e;
}AGraph;

typedef struct MGraph{
  int edges[maxn][maxn];
  int n;
  int e;
}MGraph;


void MGraphToAGraph(MGraph M){
  ArcNode *arc;
  AGraph *g = (AGraph *)malloc(sizeof(AGraph));
  g->n = M.n;
  g->e = M.e;
  for(int i = 0; i < g->n ; i ++){
    g->VList[i].first = NULL;
  }

  for(int i = 0; i < g->n; i ++){
    for(int j = 0; j < g->e; j ++){
      if(M.edges[i][j]){
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc -> adjv = j;
        arc -> next = g->VList[i].first;
        g->VList[i].first = arc;
      }
    }
  }
}

int main(){
  int n, m;
  MGraph M;
  scanf("%d%d", &n, &m);
  M.n = n;
  M.e = m;
  for(int i = 0; i < n; i ++){
    for(int j = 0; j < m; j ++){
      scanf("%d", &M.edges[i][j]);
    }
  }
  MGraphToAGraph(M);
  return 0;
}

有向图的入度

void indgeree(AGraph g){
  ArcNode *p;
  int cnt;
  for(int k = 0; k < g->n; k ++){
    cnt = 0;
    for(int j = 0; j < g-> n; j ++){
      p = g -> VList[j].first;
      while(p != NULL){
        if(p -> adjv == k){
          cnt ++;
          break;
        }
        p = p -> next;
      }
    }
    cout << "顶点" << k << "的入度为:" << cnt << endl;
  }
}

有向图的出度

void outdegree(AGraph g){
  ArcNode *p;
  int cnt;
  for(int i = 0; i < g.n; i ++){
    cnt = 0;
    p = g.VList[i].first;
    while(p != NULL){
      cnt ++;
      p = p -> next;
    }
    cout << "顶点" << i << "的出度为:" << cnt << endl;
  }
}

节点总数恰好为k的连桶分量的个数

bool vis[maxn];
int num = 0;

void dfs(AGraph g, int i){
  ArcNOde *p;
  vis[i] = true;
  num ++;
  p = g -> VList[i].first;
  while(p != NULL){
    if(!vis[p -> adjv]){
      dfs(g, p -> next);
    }
    p = p -> next;
  }
}

int getnum(Agraph g, int k){
  int i, cnt = 0;
  for(int i = 0; i < g -> n; i ++){
    vis[i] = 0;
  }
  for(int i = 0; i < g -> n; i ++){
    if(!vis[i]){
      dfs(g, i);
      if(num == k){
        cnt ++;
      }
    }
  }
  return cnt;
}

删除边ij

void d_edge(AGraph *g, int i, int j){
  ArcNOde p = g -> VList[i].first;
  ArcNode pre = NULL;
  while(p != NULL){
    if(p -> adjv == j){
      if(pre == NULL){
        g -> VList[i].first = p -> next;
      }
      else{
        pre -> next = p -> next;
      }
      free(p);
    }
    else{
      pre = p;
      p = p -> next;
    }
  }

  p = g -> vlist[j].first;
  pre = NULL;
  while(p != NULL){
    if(p -> adjv == i){
      if(pre == NULL){
        g[j] -> vlist[i].first = p -> next;
      }
      else{
        pre -> next = p -> next;
        free(p);
      }
    }
    else{
      pre = p;
      p = p -> next;
    }
  }
}

出度邻接表变成入度邻接表

void invert(AGraph *gin, AGraph *gout){
  gin -> n = gout -> n;
  gin -> e = gout -> e;

  for(int i = 0; i < gout -> n; i ++){
    gin -> VList[i].data = gout -> VList[i].data;
    gin -> VList[i].first = null;
  }

  for(int i = 0; i < gout -> n; i ++){
    ArcNode *p, *s;
    p = gout -> VList[i].first;//取出邻接表中第i个顶点的指向邻接表的指针

    while(p != NULL){//遍历邻接表中第i个顶点所有邻接边
      int j = p -> adjv;
      s = new ArcNode;
      s -> adjv = i;//将 i 挂到 g->VList[j]上
      s -> next = gin -> VList[j].first;//将 i 挂到 j上
      gin -> vlist[j].first = s;
      p = p -> next;
    }
  }

找到vi-vj路径长度为k的路径

int vis[maxn], path[maxn];
void dfs(AGraph *g, int vi, int vj, int d){
  vis[vi] = 1;
  path[d ++] = vi;
  if(vi == vj && d == k){
    for(int i = 0; i < d; i ++){
      cout << path[i] << " " ;
    }
    cout << endl;
  }
  ArcNode *p = g -> vlist[vi].first;
  int v;
  while(p != NULL){
    v = p -> adjv;
    if(vis[v] == 0){
      dfs(g, v, vj, d);
    }
    p = p -> next;
  }
  vis[vi] = 0;
  d --;
}

判断无向图是否是树

bool istree(AGraph *g){
  int vis[maxn];
  for(int i = 0; i < g -> n; i ++){
    vis[i] = 0;
  }
  int Vnum = 0, Enum = 0;
  dfs(g, 1, Vnum, Enum, vis);
  if(Vnum == g -> n && Enum == 2 * (g -> n - 1))//边数为2∗(n−1)
    return true;
  else
    return false;
}

void dfs(Agraph *g, int v, int *Vnum, int *Enum, int vis[]){
  vis[v] = 1;
  Vnum ++;
  ArcNOde *p = g -> vlist[v].firs;
  while(p != NULL){
    Enum ++;
    if(!vis[p -> adjv]) dfs(g, p -> adjv, vum, enum, vis);
    p = p -> next;
  }
}

求图的连通分量个数和各连通分量的顶点集

void bfs_trace(Graph *g){
  int i, cnt = 0;
  int vis[maxn];
  for(int i = 0; i < g -> n; i ++){
    vis[i] = 0;
  }
  for(int i = 0; i < g -> n; i ++){
    if(!vis[i]){
      cnt ++;
      dfs(g, i);
    }
  }
}

void dfs(Graph *g, int i){
  ArcNode *p;
  vis[i] = 1;
  p = vlis[i].first;
  while(p != NULL){
    if(!vis[p -> adjv]){
      dfs(g, p -> adjv);
    }
    p = p -> next;
  }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注