首先,什么是图

Graph)用于表示物件与物件之间的关系,是图论的基本研究对象。一张图由一些小圆点(称为顶点结点)和连结这些圆点的直线或曲线(称为)组成。

来源 维基百科

看到这里,你一定已经对图的定义有了一个基本的概念了

但是很明显,向上面这样的一张图肯定无法存入计算机系统并被计算机辨识,所以接下来的问题就是

有向图的表示

对于一个图G = (V,E),|V|代表图的结点数,|E|代表边的条数

我们对于这样的图有两种较为典型的表示方法

接下来我们逐一介绍

邻接链表

我们首先整理一下之前所出现的那张有向图

接下来我们可以得到下面这样的一张表

对于图 G = (V,E)  ,其邻接链表表示由一个包含|V|条链表的数组Edge所构成,每个结点有一条链表。对于每个结点u∈V,邻接链表Edge[u]包含所有与结点u之间有边相连的结点v。

代码实现

const int maxn = 100;
int cnt = 0,root[maxn];
struct Graph{
  int to,cost,next;
}edge[maxn];

// 初始化,-1代表无结点u后无相连结点 
void init(){
  memset(root,-1,sizeof(root));
  return;
} 
// 输入 
void add(int start,int to,int cost){
  // 将v指向v' 
  edge[cnt].next = root[start];
  // 路径权重 
  edge[cnt].cost = cost;
  // 目的地 
  edge[cnt].to = to;
  // 将u指向v 
  root[start] = cnt++;
  return;
}

邻接矩阵

同样的道理,我们可以得到一个邻接矩阵,使用一个二维数组来表示,表中数值代表了两点之间的距离

代码实现

const int maxn = 100;
// 设正无穷为int最大值 
const int inf = 2147483647;
int edge[maxn][maxn];

// 初始化,-1代表无结点u后无相连结点 
void init(){
  for(int i = 0;i<maxn;i++){
    for(int j = 0;j<maxn;j++){
      edge[i][j] = inf;
    }
  }
  return;
} 

// 输入 
void add(int start,int to,int cost){
  edge[start][to] = cost;
  return;
}



打赏 赞(2)
微信二维码图片

微信扫描二维码打赏

发表评论

电子邮件地址不会被公开。

Scroll Up