i3geek.com
闫庚哲的个人博客

图论

一、介绍

图,从关系的有向性上,可以分为有向图和无向图。从边的性质上,可以分为有权图和无权图。

图论问题的常见出错问题:题目中的各种对图的约束条件,如图的连通性,图的边的唯一性,拓扑排序的无回路性,最短路的的无负权,无负环,0顶点图或单顶点图等等。

二、图的表示

图在程序中的表示方法主要有邻接矩阵和邻接表等几种,邻接矩阵和邻接表是比较常用且基础的两种。

  • 邻接矩阵适用于稠密图或需要很快判两个顶点间是否有边或边权值是多少的情况。
  • 邻接表在稀疏图的表示上更加节省内存而且在边的遍历上比邻接矩阵更方便。

邻接矩阵使用一个二维矩阵,矩阵的两个维度均为图的顶点数,下标表示顶点的编号。假设使用矩阵graph[N][N]来表示一个图,对于无权图:可以使用graph[i][j]表示i顶点和j顶点之间有边,反之使其为0表示两个顶点之间无边。对于有权图,则全graph[i][j]等于相应的边的权值。对于无向图graph[i][j]==graph[j][i]。

邻接表使用一个线性表,表中的每个元素对应图的一个顶点,并且保存一个链表,链表的每个节点表示与从该顶点出发的一条边,链表的节点中保存与边有关的所有信息如该边指向的顶点,边的权值等。

可以看出邻接矩阵需要的空间为O(n^2),而邻接表需要O(V+E),所以邻接表在稀疏图上的表示有着非常大的空间优势。

三、代码实现

struct Arc
{
int next_arc;
int point;
};
int node[V];
struct Arc arc[E];

使用node存储每个顶点, arc存储每条边,node[i]表示第i个顶点指向的第一条边在arc中的位置,next_arc表示和这条边同样出发点的下一条边在arc中的位置。

每个node[i]都表示一个用数组实现的表示边的链表的表头,插入一条新边的过程,就是在该链表上插入一个节点,这里的链表是用数组实现,当然也可以使用动态分配去实现。

加入新边:

void AddEdge(int u,int v)
{
arc[EdgeCount].next_arc=node[u];
arc[EdgeCount].point=v;
node[u]=EdgeCount;
EdgeCount++;
}

EdgeCount用来表示总共加入的边的数量,初始化为0.

赞(0)
未经允许不得转载:爱上极客 » 图论
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址