图的基本知识

图的存储结构

邻接矩阵

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

数据结构

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

特点

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

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

优点:

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

缺点:

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

前向星

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

数据结构

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$ 的邻接表。

邻接表有三种实现方法:

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

数据结构

动态建表

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;

}

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;

    }

  }

}