图的基本知识

图的存储结构

邻接矩阵

对于一个有 $n$ 个点的图，需要 $n*n$ 的矩阵，这个矩阵中的第 $i$ 行第 $j$ 列的数值表示点 $v_i$ 到点 $v_j$ 的距离

数据结构

int maze[maxn][maxn]; //maze[i][j]表示点i到点j的权重, 不可达为inf或者-1

特点

时间复杂度: $O(n)$

空间复杂度: $O(m)$

优点:

1. 实现简单
2. 可以直接查询点i与j是否有边, 如果有, 边权是多少

缺点:

1. 遍历效率低
2. 不能存储重边
3. 初始化效率低
4. 大图的空间开销大, 当n比较大时, 建一个n*n的数组不现实
5. 稀疏图空间利用率不高

---

前向星

前向星是一种通过存储边信息的方式存储图的数据结构。读入每条边的信息存储在数组中，把数组中的边按照起点顺序排序。

数据结构

int head[maxn]; //存储起点为i的第一条边的位置
struct node
{
  int from      //起点
  int to;       //终点
  int w;        //权值
};
node edge[maxn];

//比较函数
bool cmp(node a, node b)
{
  if(a.from != b.from) return a.from < b.from;
  return a.to != b.to ? a.to < b.to : a.w < b.w;
}

//读入数据
void input()    //信息储存主要代码
{
    cin >> n >> m;
    for(int i = 0; i < m; i++)
      cin >> edge[i].from >> edge[i].to >> edge[i].w;
    sort(edge, edge + m, cmp);
    memset(head, -1, sizeof(head)); //#include <cstring>
    head[edge[0].from] = 0;
    for(int i = 1; i < m; i++)
        if(edge[i].from != edge[i-1].from)
            head[edge[i].from] = i; // 确定起点为vi的第一条边的位置
}

---

邻接表

邻接表是图的一种链式存储结构。对于图G中每个顶点$v_i$, 把所有邻接与$v_i$的顶点$v_j$链成一个单链表，此单链表称为顶点$v_j$的邻接表。

邻接表有三种实现方法:

1. 动态建表
2. 使用STL中的vector模拟链表
3. 静态建表(链式前向星)

数据结构

1. 动态建表

   struct edgeNode      //邻接表节点
   {
     int to;            //终点
     int w;             //权值
     edgeNode * next;   //指向下一条边的指针
   };
   struct vNode
   {
     int from;          //起点
     edgeNode * first;  //邻接表头指针
   };
   vNode adjlist[maxn]; //整个图的邻接表
   
   void input()    //信息储存主要代码
   {
     int i, j, w;
     cin >> i >> j >> w;
     edgeNode * p = new edgeNode();
     p->to = j;
     p->w = w;
     p->next = adjlist[i].first;
     adjlist[i].first = p;
   }
   
   void output()    //遍历代码
   {
     for(int i = 1; i <= n; i++)
       for(edgeNode * k = adjlist[i].first; k != NUll; k = k->next)
         cout << i << " " << k->to << " " << k -> w << endl;
   }

2. STL中的vector模拟链表实现

   struct edgeNode
   {
     int to;
     int w;
   };
   vector<edgeNode> map[maxn];
   
   void input()    //信息储存主要代码
   {
     edgeNode e;
     int i, j, w;
     cin >> i >> j >> w;
     e.to = j;
     e.w = w;
     map[i].push_back(e);
   }
   
   void output()    //遍历代码
   {
     for(int i = 1; i <= n; i++)
     {
       for(vector<edgeNode>::iterator k = map[i].begin(); k != map[i].end();k++)
       {
         edgeNode t = *k;
         cout << i << ' ' << t.to << ' ' << t.w << endl;
       }
     }
   }

---

链式前向星

邻接表的一种实现方法，又称为邻接表的静态建表。链式前向星方法最开始基于前向星，目的是提高其构造效率，而最终形成的数据却是一个变形的邻接表。

数据结构

int head[n];
struct edgeNode
{
  int to;
  int w;
  int next;
};
edgeNode edge[m];

void input(int k)    //信息存储主要代码, k表示当前输入第k条边
{
  int i, j, w;
  cin >> i >> j >> w;
  edge[k].to = j;
  edge[k].w = w;
  edge[k].next = head[i];
  head[i] = k;
}

void output()
{
  for(int i = 1; i <= n; i++)
  {
    for(int k = head[i]; k != -1; k = edge[k].next)
    {
      cout << i << ' ' << edge[k].to << ' ' << edge[k].w << endl;
    }
  }
}

---