图论算法 有图有代码 万字总结 向前辈致敬（2） C语言, 空间

yuyang911220

邻接表
如果用邻接矩阵表示稀疏图就会浪费大量内存空间，而用链接表，则是通过把顶点所能到的顶点的边保存在链表中来表示图，这样就只需要O(|V|+|E|)的内存空间。

而所谓的邻接表，就是用n个链表代替邻接矩阵中的n行。链表中的结点结构至少要包含一个顶点域和一个链域。对于任意给定的链表i，链表中的结点就是与顶点i相邻的所有顶点。邻接表存储声明的C语言声明如下：
#define MAX_VERTICES 50  typedef struct node *node-pointer; typedef struct node {     int vertex;     struct node *link; }; node_pointer graph[MAX_VERTICES]; int n=0;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

邻接多重表
在无向图的邻接表存储表示中，每一条边(vi，vj)都表示为两项：一项在顶点vi的邻接表中，而另一项在顶点vj的邻接表中。在多重表中，各链表中的结点可以被几个链表共享，此时图中的每一条边只对应于一个结点，而这个结点出现在该边所关联的两个顶点的每个邻接链表中。如下图所示：
                    marked            vertex1            vertex2            path1            path2        邻接多重表结点结构的C语言声明为：
typedef struct edge *edge-pointer typedef struct edge {     short int marked;     int vertex1;     int vertex2;     edge_pointer path1;     edge_pointer path2; };

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

图的基本操作和算法广度优先搜索请先忽视下图中所有的下标，让我们从头开始。随意选择一个点，此处选择v3，作为切入点。因此到v3的距离为0。从v3出发，距离为1的结点是v1和v6；继续下一步，v6已经无路可走，而与v1距离为1的是v2和v4，因此对它们标记上2；继续下去，v2和v4走一步都可以到v5，v4走一步可以到v7，因此v5和v7被标记为3。至此搜索便结束了。
这就是广度优先搜索（breadth-first search），该方法按层处理顶点。距起始点最近的那些顶点首先被求值，最远点则最后被求值，这很像对树的层序遍历（level-order traversal）。

为了实现广度优先搜索，可以使用动态链接队列。在队列中的每个顶点都包含两个域：顶点的序号和链接指针。
函数bfs所使用的队列的定义和函数原型声明为：
typedef struct queue *queue_pointer; typedef struct queue {     int vertex;     queue_pointer link; }; void addq(queue_pointer *, queue_pointer *,int); int deleteq(queue_pointer *);

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

图的广度优先搜索算法：
void bfs(int v) {     node_pointer w;     queue_pointer front,rear;     front=rear=NULL;     printf("%5d",v);     visited[v]=TRUE;     addq(&front,&rear,v);     while(front)     {         v=deleteq(&front);         for(w=graph[v];w;w=w->link)         {             if(!visited[w->vertex])             {                 printf("%5d",w->vertex);                 addq(&front,&rear,w->vertex);                 visited[w->vertex]=TRUE;             }         }     } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

图中每个顶点都被存入队列一次，所以该算法中的while循环至多重复n次。如果采用邻接表存储表示，那么该算法所需要的时间为：
d0+d1+…+dn−1=O(e)
其中di为顶点vi的度。
而如果采用邻接矩阵来实现，那么对于每个顶点的访问，while循环的时间为O(n)，所以算法的总耗时为O(n2)。和接下来的深度优先搜索一样，一次广度优先搜索访问到的顶点以及与这些顶点相关联的边形成的图G的一个连通分支。
深度优先搜索深度优先搜索内容较多，已经在下文中单独列出。
连通图使用以上的两种搜索算法也可以用来判断一个无向图是否是连通的。具体步骤如下：
1.调用bfs(0)或dfs(0)
2.检查是否存在未被访问过的顶点
具体代码如下：
void connected(void) {     int i;     for(i=0;i<n;i++)     {         if(!visited)         {             dfs(i);             printf("n");         }     } }           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

算法分析：如果采用邻接表存储，那么函数dfs时间开销为O(e)。这里for循环的时间开销为O(n)，所以整个算法的时间复杂性为O(n+e)。