C算法精解---图（Graph）
在计算机科学领域，图是最为灵活的数据结构之一。事实上，大多数的数据结构都能用图的形式表示，尽管按照这种方法表示它们通常会变得更加复杂。图是一种灵活的数据结构，描述一种模型用来定义对象之间的关联和联系。对象有顶点表示，对象之间的关系或关联则通过顶点的边来表示。 图的遍历方法： 深度优先搜索：（DFS：Depth First Search) 深度优先搜索在搜索过程中每当访问到某个顶点后
·
在计算机科学领域，图是最为灵活的数据结构之一。事实上，大多数的数据结构都能用图的形式表示，尽管按照这种方法表示它们通常会变得更加复杂。图是一种灵活的数据结构，描述一种模型用来定义对象之间的关联和联系。对象有顶点表示，对象之间的关系或关联则通过顶点的边来表示。
图的遍历方法：
深度优先搜索：（DFS：Depth First Search)
深度优先搜索在搜索过程中每当访问到某个顶点后，需要递归地访问此顶点的所有未访问过得相邻的顶点。
算法描述过程看下图
广度优先搜索：（BFS：Breadth first Search)
广度优先搜索采用队列的方式。
图的存储结构
由于图的顶点间的关系无规律，因此图的存储比链表及树的存储相对复杂些，需要根据图的具体应用来选择合适的存储结构，下面来介绍2中常用的存储结构：邻接矩阵和临界表。
图的数组表示法，又称临界矩阵。
邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。
假设图中顶点数为n，则邻接矩阵An×n：
1 若Vi和Vj之间有弧或边
A[i][j]=
0 反之
注意：
1) 图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。
2) 无向图的邻接矩阵必然是对称矩阵。
3) 无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。
下面是邻接矩阵代码：
#include <stdio.h>
#include "sequeue.h"
#ifndef N
#define N 5
#endif
void DFS(int matrix[N][N],int s[],int v);
void BFS(int matrix[N][N],int s[],int v);
int firstadj(int matrix[N][N],int v)
{
int i;
for(i=0;i<N;i++)
if(matrix[v][i]==1)
return i;
return -1;
}
int nextadj(int matrix[N][N],int v,int u)
{
int i;
for(i=u+1;i<N;i++)
if(matrix[v][i]==1)
return i;
return -1;
}
//1、访问v，s【v】置位；2、取v的第一临界点u
//3、若u>=0,转4，否则退出；4、若u未访问则DFS（matrix，s，u）
//再访问下一个节点，u = vnextadj(matrix,s,u);再转3.
void DFS(int matrix[N][N],int s[],int v)//深度优化搜索。
{
int u;
printf("V%d ",v);
s[v]=1;
u = firstadj(matrix,v);
while(u>=0)
{
if(s[u]!=1)
{
DFS(matrix,s,u);
}
u=nextadj(matrix,v,u);
}
}
void BFS(int matrix[N][N],int s[],int v)//对图G从序号V的顶点开始遍历，按BFS遍历；
{
int u;
sequeue *sq;
sq = Createsequeue();//创建队列并置空；
printf("V%d ",v);//访问V定点，输出；
s[v]=1;//对v定点置1；
Ensequeue(sq,v);//v进队列；
while(!Emptysequeue(sq))//当队列未空时，依次出队，
{
v = Desequeue(sq);
u=firstadj(matrix,v);//先找到他的第一临接点；
while(u>=0)//u》=0；表示访问v定点的所有临接点；
{
if(!s[u])//判断临节点标志是否为1，如果是找下个临界点；依次遍历
{
printf("v%d ",u);
s[u]=1;
Ensequeue(sq,u);//有临界点时，访问 置标识1，并进队列～
}
u = nextadj(matrix,v,u);//找v定点的下一临界点，
}
}
}
int main()
{
int matrix[N][N]={0};
int i,j,s[N]={0};
while(1)
{
scanf("%d%d",&i,&j);
if ( i == j)
break;
matrix[i][j]=1;
matrix[j][i]=1;
}
// DFS(matrix,s,0);
//********************************************
BFS(matrix,s,0);
#if 0
for(i=0;i<N;i++)
{
printf("V%d: ",i);
for(j=0;j<N;j++)
{
if(matrix[i][j] == 1)
printf("V%d ",j);
}
puts("");
}
#endif
return 0;
}
2.图的邻接表存储表示：
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef struct _node_
{
int vertex;
struct _node_ *next;
} linknode, *linklist;
void AddEdge(linknode s[], int i, int j)
{
linklist p, q;
p = s + i;
while (p->next != NULL && p->next->vertex < j) p = p->next;
q = (linklist)malloc(sizeof(linknode));
q->vertex = j;
q->next = p->next;
p->next = q;
return;
}
int FirstAdj(linknode s[], int v)
{
return s[v].next->vertex;
}
int NextAdj(linknode s[], int v, int u)
{
linklist p;
p = s[v].next;
while (p->vertex != u) p = p->next;
return (p->next == NULL ? -1 : p->next->vertex);
}
int main()
{
linknode s[N] = {{0, NULL}};
int i, j;
linklist p;
while (scanf("%d,%d", &i, &j) == 2 && i != j)
{
AddEdge(s, i, j);
AddEdge(s, j, i);
}
for (i=0; i<N; i++)
{
printf("V%d : ", i);
p = s[i].next;
while (p != NULL)
{
printf("V%d ", p->vertex);
p = p->next;
}
printf("\n");
}
return 0;
}
上面是比较简单的介绍了邻接表的实现过程。下面介绍是算法精解上面的函数接口。先来了解下：
这个图好像在下面程序中理解起不到具体的作用，只能是个参照。下面代码的理解需要对前面链表的函数接口和集合的函数接口，有一定的理解才能很清晰的知道函数的具体实现过程。
/*graph.h*/
#ifndef GRAPH_H
#define GRAPH_H
#include <stdlib.h>
#include <stdio.h>
#include "./list.h"
#include "./set.h"
/*定义邻接表结构体*/
typedef struct Adjlist_{
void *vertex;//保存当前顶点的值
Set adjcent;//保存邻接顶点的值
}Adjlist;
/*定义图的结构体*/
typedef struct Graphs_ {
int vcont;// 顶点的个数
int ecount;//边的个数
int (*match)(const void *key1;const void *key2);
void (*destroy)(void *data);
List adjlists;//邻接表链表
}Graphs;
/*函数接口*/
void graph_init(Graphs *graph,int (*match)(const void *key1,const void *key2),
void (*destroy)(void *data));
void graph_destroy(Graphs *graph);
int graph_ins_vertex(Graphs *graph,const void *data);
int graph_ins_edge(Graphs *graph,const void *data1,const void *data2);
int graph_rem_vertex(Graphs *graph,const void *data);
int graph_rem_edge(Graphs *graph,const void *data1,const void *data2);
int graph_adjlist(const Graphs *graph, const void *data, Adjlist **adjlist);
int graph_is_adjacent(const Graphs *graph,const void *data1,const void *data2);
#define graph_adjlists(graph) ((graph)->adjlists)
#define graph_vcount(graph) ((graph)->vcont)
#define graph_ecount(graph) ((graph)->ecount)
#endif
/*graph.c*/
#include <stdio.h>
#include <string.h>
#include "../include/graph.h"
#include "../include/list.h"
#include "../include/set.h"
/*图的初始化*/
void graph_init(Graphs *graph,int (*match)(const void *key1,const void *key2),
void (*destroy)(void *data))
{
/*初始化图结构体成员*/
graph->vcont = 0;
graph->ecount = 0;
graph->match = match;
graph->destroy = destroy;
/*初始化邻接表头的链表*/
list_init(&graph->adjlists,NULL);
return;
}
/*销毁图*/
void graph_destroy(Graphs *graph)
{
Adjlist *adjlist;
/*销毁图*/
while(list_size(&graph->adjlists) > 0){
if (list_rem_next(&graph->adjlists,NULL,(void **)&adjlists) == 0){
set_destroy(&adjlist->adjcent);
if (graph->destroy != NULL)
graph->destroy(adjlist->vertex);
free(adjlist);
}
}
/*删除邻接表链表*/
list_destory(&greap->adjlists);
memset(graph,0,sizeof(Graphs));
return;
}
/*插入顶点
*返回值：成功0；已经存在1；失败：-1.
* */
int graph_ins_vertex(Graphs *graph,const void *data)
{
ListElmt *element;
Adjlist *adjlist;
int retval;
/*不允许插入的顶点已经存在，如果存在返回1*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data,((Adjlist*)list_data(element))->vertex))
return 1;
}
/*插入顶点，插入失败，返回-1*/
if((adjlist = (Adjlist *)malloc(sizeof(Adjlist))) == NULL)
return -1;
adjlist->vertex = (void *)data;
set_init(&Adjlist->adjcent,graph->match,NULL);
if((retval = list_ins_next(&graph->adjlists,list_tail(&graph->adjlists),adjlist)) != 0)
return retval;
graph->vcont ++;
return 0;
}
/*插入边
*返回值：成功0；已经存在1；失败：-1.
* */
int graph_ins_edge(Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element;
int retval;
/*不允许插入的边，在途中没有这个顶点*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data2,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
/*将第二个顶点，插入到第一个顶点中的邻接表中*/
if((retval = set_insert(&((Adjlist *)list_data(element))->adjcent,data2)) != 0)
return retval;
graph->ecount ++;
return 0;
}
/*删除顶点
*return:成功：0；失败：-1
*从图中移除所有与data相匹配的顶点，在调用函数之前，所有与该顶点相关的边都必须移除。
*函数返回后，data指向已移除顶点中保存的数据，有调用着管理data的存储空间。
* */
int graph_rem_vertex(Graphs *graph,const void *data)
{
ListElmt *element,
*temp,
*prev = NULL;
Adjlist *adjlist;
int found = 0;
/*在图中的邻接表查找顶点*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
/*不允许和顶点相关的边还存在*/
if (set_is_member(&((Adjlist *)list_data(element))->adjcent,data))
return -1;
/*如果找到顶点，temp指向找到的顶点*/
if(graph->match(data,((Adjlist*)list_data(element))->vertex)){
temp = element;
found = 1;
}
/*保存找到顶点的上一个节点的指针prev*/
if (!found)
prev = element;
}
/*没有找到返回-1*/
if (!found)
return -1;
/*不允许删除顶点的邻接表中为不为空*/
if (set_size(&((Adjlist *)list_data(temp)) ->adjcent) > 0)
return -1;
/*删除顶点*/
if (list_rem_next(&graph->adjlists,prev,(void **adjlist)) != 0)
return -1;
/*data,保存顶点的数值，释放顶点*/
*data = adjlist -> vertex;
free(adjlist);
graph->vcont --;
return 0;
}
/*删除边
*return:成功：0；失败：-1
*从图中移除所有从data1到data2的边，函数返回后，vdata2指向有由data1所致顶的顶点的链接表中的数据。
*有调用着管理data2的存储空间。
* */
int graph_rem_edge(Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
/*将data2从data1的邻接表中删除*/
if (set_remove(&((Adjlist *)list_data(element))->adjcent,data2) != 0)
return -1;
graph->ecount--;
return 0;
}
/*取得邻接表
* return：成功：0；失败：-1.
*取的graph中由data所指定的顶点的邻接表。返回的邻接表以结构体Adjlist 的形式保存
*该结构体保存与data相匹配的顶点。
* */
int graph_adjlist(const Graphs *graph, const void *data, Adjlist **adjlist)
{
ListElmt *element,
*prev = NULL;
/*搜索顶点的结构体*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data,((Adjlist*)list_data(element))->vertex))
break;
prev = element;
}
if (element == NULL)
return -1;
*adjlist = list_data(element);
return 0;
}
/*判断data2是否与data1邻接
*return 成功：0；失败：-1.
* */
int graph_is_adjacent(const Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element,
*prev = NULL;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
prev = element;
}
if (element == NULL)
return -1;
return set_is_member(&((Adjlist *)list_data(element))->adjcent,data2);
}
假设图中顶点数为n，则邻接矩阵An×n：
1 若Vi和Vj之间有弧或边
A[i][j]=
0 反之
注意：
1) 图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。
2) 无向图的邻接矩阵必然是对称矩阵。
3) 无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。
下面是邻接矩阵代码：
#include <stdio.h>
#include "sequeue.h"
#ifndef N
#define N 5
#endif
void DFS(int matrix[N][N],int s[],int v);
void BFS(int matrix[N][N],int s[],int v);
int firstadj(int matrix[N][N],int v)
{
int i;
for(i=0;i<N;i++)
if(matrix[v][i]==1)
return i;
return -1;
}
int nextadj(int matrix[N][N],int v,int u)
{
int i;
for(i=u+1;i<N;i++)
if(matrix[v][i]==1)
return i;
return -1;
}
//1、访问v，s【v】置位；2、取v的第一临界点u
//3、若u>=0,转4，否则退出；4、若u未访问则DFS（matrix，s，u）
//再访问下一个节点，u = vnextadj(matrix,s,u);再转3.
void DFS(int matrix[N][N],int s[],int v)//深度优化搜索。
{
int u;
printf("V%d ",v);
s[v]=1;
u = firstadj(matrix,v);
while(u>=0)
{
if(s[u]!=1)
{
DFS(matrix,s,u);
}
u=nextadj(matrix,v,u);
}
}
void BFS(int matrix[N][N],int s[],int v)//对图G从序号V的顶点开始遍历，按BFS遍历；
{
int u;
sequeue *sq;
sq = Createsequeue();//创建队列并置空；
printf("V%d ",v);//访问V定点，输出；
s[v]=1;//对v定点置1；
Ensequeue(sq,v);//v进队列；
while(!Emptysequeue(sq))//当队列未空时，依次出队，
{
v = Desequeue(sq);
u=firstadj(matrix,v);//先找到他的第一临接点；
while(u>=0)//u》=0；表示访问v定点的所有临接点；
{
if(!s[u])//判断临节点标志是否为1，如果是找下个临界点；依次遍历
{
printf("v%d ",u);
s[u]=1;
Ensequeue(sq,u);//有临界点时，访问 置标识1，并进队列～
}
u = nextadj(matrix,v,u);//找v定点的下一临界点，
}
}
}
int main()
{
int matrix[N][N]={0};
int i,j,s[N]={0};
while(1)
{
scanf("%d%d",&i,&j);
if ( i == j)
break;
matrix[i][j]=1;
matrix[j][i]=1;
}
// DFS(matrix,s,0);
//********************************************
BFS(matrix,s,0);
#if 0
for(i=0;i<N;i++)
{
printf("V%d: ",i);
for(j=0;j<N;j++)
{
if(matrix[i][j] == 1)
printf("V%d ",j);
}
puts("");
}
#endif
return 0;
}
2.图的邻接表存储表示：
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef struct _node_
{
int vertex;
struct _node_ *next;
} linknode, *linklist;
void AddEdge(linknode s[], int i, int j)
{
linklist p, q;
p = s + i;
while (p->next != NULL && p->next->vertex < j) p = p->next;
q = (linklist)malloc(sizeof(linknode));
q->vertex = j;
q->next = p->next;
p->next = q;
return;
}
int FirstAdj(linknode s[], int v)
{
return s[v].next->vertex;
}
int NextAdj(linknode s[], int v, int u)
{
linklist p;
p = s[v].next;
while (p->vertex != u) p = p->next;
return (p->next == NULL ? -1 : p->next->vertex);
}
int main()
{
linknode s[N] = {{0, NULL}};
int i, j;
linklist p;
while (scanf("%d,%d", &i, &j) == 2 && i != j)
{
AddEdge(s, i, j);
AddEdge(s, j, i);
}
for (i=0; i<N; i++)
{
printf("V%d : ", i);
p = s[i].next;
while (p != NULL)
{
printf("V%d ", p->vertex);
p = p->next;
}
printf("\n");
}
return 0;
}
上面是比较简单的介绍了邻接表的实现过程。下面介绍是算法精解上面的函数接口。先来了解下：
这个图好像在下面程序中理解起不到具体的作用，只能是个参照。下面代码的理解需要对前面链表的函数接口和集合的函数接口，有一定的理解才能很清晰的知道函数的具体实现过程。
/*graph.h*/
#ifndef GRAPH_H
#define GRAPH_H
#include <stdlib.h>
#include <stdio.h>
#include "./list.h"
#include "./set.h"
/*定义邻接表结构体*/
typedef struct Adjlist_{
void *vertex;//保存当前顶点的值
Set adjcent;//保存邻接顶点的值
}Adjlist;
/*定义图的结构体*/
typedef struct Graphs_ {
int vcont;// 顶点的个数
int ecount;//边的个数
int (*match)(const void *key1;const void *key2);
void (*destroy)(void *data);
List adjlists;//邻接表链表
}Graphs;
/*函数接口*/
void graph_init(Graphs *graph,int (*match)(const void *key1,const void *key2),
void (*destroy)(void *data));
void graph_destroy(Graphs *graph);
int graph_ins_vertex(Graphs *graph,const void *data);
int graph_ins_edge(Graphs *graph,const void *data1,const void *data2);
int graph_rem_vertex(Graphs *graph,const void *data);
int graph_rem_edge(Graphs *graph,const void *data1,const void *data2);
int graph_adjlist(const Graphs *graph, const void *data, Adjlist **adjlist);
int graph_is_adjacent(const Graphs *graph,const void *data1,const void *data2);
#define graph_adjlists(graph) ((graph)->adjlists)
#define graph_vcount(graph) ((graph)->vcont)
#define graph_ecount(graph) ((graph)->ecount)
#endif
/*graph.c*/
#include <stdio.h>
#include <string.h>
#include "../include/graph.h"
#include "../include/list.h"
#include "../include/set.h"
/*图的初始化*/
void graph_init(Graphs *graph,int (*match)(const void *key1,const void *key2),
void (*destroy)(void *data))
{
/*初始化图结构体成员*/
graph->vcont = 0;
graph->ecount = 0;
graph->match = match;
graph->destroy = destroy;
/*初始化邻接表头的链表*/
list_init(&graph->adjlists,NULL);
return;
}
/*销毁图*/
void graph_destroy(Graphs *graph)
{
Adjlist *adjlist;
/*销毁图*/
while(list_size(&graph->adjlists) > 0){
if (list_rem_next(&graph->adjlists,NULL,(void **)&adjlists) == 0){
set_destroy(&adjlist->adjcent);
if (graph->destroy != NULL)
graph->destroy(adjlist->vertex);
free(adjlist);
}
}
/*删除邻接表链表*/
list_destory(&greap->adjlists);
memset(graph,0,sizeof(Graphs));
return;
}
/*插入顶点
*返回值：成功0；已经存在1；失败：-1.
* */
int graph_ins_vertex(Graphs *graph,const void *data)
{
ListElmt *element;
Adjlist *adjlist;
int retval;
/*不允许插入的顶点已经存在，如果存在返回1*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data,((Adjlist*)list_data(element))->vertex))
return 1;
}
/*插入顶点，插入失败，返回-1*/
if((adjlist = (Adjlist *)malloc(sizeof(Adjlist))) == NULL)
return -1;
adjlist->vertex = (void *)data;
set_init(&Adjlist->adjcent,graph->match,NULL);
if((retval = list_ins_next(&graph->adjlists,list_tail(&graph->adjlists),adjlist)) != 0)
return retval;
graph->vcont ++;
return 0;
}
/*插入边
*返回值：成功0；已经存在1；失败：-1.
* */
int graph_ins_edge(Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element;
int retval;
/*不允许插入的边，在途中没有这个顶点*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data2,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
/*将第二个顶点，插入到第一个顶点中的邻接表中*/
if((retval = set_insert(&((Adjlist *)list_data(element))->adjcent,data2)) != 0)
return retval;
graph->ecount ++;
return 0;
}
/*删除顶点
*return:成功：0；失败：-1
*从图中移除所有与data相匹配的顶点，在调用函数之前，所有与该顶点相关的边都必须移除。
*函数返回后，data指向已移除顶点中保存的数据，有调用着管理data的存储空间。
* */
int graph_rem_vertex(Graphs *graph,const void *data)
{
ListElmt *element,
*temp,
*prev = NULL;
Adjlist *adjlist;
int found = 0;
/*在图中的邻接表查找顶点*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
/*不允许和顶点相关的边还存在*/
if (set_is_member(&((Adjlist *)list_data(element))->adjcent,data))
return -1;
/*如果找到顶点，temp指向找到的顶点*/
if(graph->match(data,((Adjlist*)list_data(element))->vertex)){
temp = element;
found = 1;
}
/*保存找到顶点的上一个节点的指针prev*/
if (!found)
prev = element;
}
/*没有找到返回-1*/
if (!found)
return -1;
/*不允许删除顶点的邻接表中为不为空*/
if (set_size(&((Adjlist *)list_data(temp)) ->adjcent) > 0)
return -1;
/*删除顶点*/
if (list_rem_next(&graph->adjlists,prev,(void **adjlist)) != 0)
return -1;
/*data,保存顶点的数值，释放顶点*/
*data = adjlist -> vertex;
free(adjlist);
graph->vcont --;
return 0;
}
/*删除边
*return:成功：0；失败：-1
*从图中移除所有从data1到data2的边，函数返回后，vdata2指向有由data1所致顶的顶点的链接表中的数据。
*有调用着管理data2的存储空间。
* */
int graph_rem_edge(Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
}
if (element == NULL)
return -1;
/*将data2从data1的邻接表中删除*/
if (set_remove(&((Adjlist *)list_data(element))->adjcent,data2) != 0)
return -1;
graph->ecount--;
return 0;
}
/*取得邻接表
* return：成功：0；失败：-1.
*取的graph中由data所指定的顶点的邻接表。返回的邻接表以结构体Adjlist 的形式保存
*该结构体保存与data相匹配的顶点。
* */
int graph_adjlist(const Graphs *graph, const void *data, Adjlist **adjlist)
{
ListElmt *element,
*prev = NULL;
/*搜索顶点的结构体*/
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data,((Adjlist*)list_data(element))->vertex))
break;
prev = element;
}
if (element == NULL)
return -1;
*adjlist = list_data(element);
return 0;
}
/*判断data2是否与data1邻接
*return 成功：0；失败：-1.
* */
int graph_is_adjacent(const Graphs *graph,const void *data1,const void *data2)
{
ListElmt *element,
*prev = NULL;
for(element = list_head(&graph->adjlists);element != NULL;element = list_next(element)){
if(graph->match(data1,((Adjlist*)list_data(element))->vertex))
break;
prev = element;
}
if (element == NULL)
return -1;
return set_is_member(&((Adjlist *)list_data(element))->adjcent,data2);
}
欢迎加入 MCP 技术社区！与志同道合者携手前行，一同解锁 MCP 技术的无限可能！
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)