数据结构㉓图的邻接矩阵结构及遍历
图的邻接矩阵结构及遍历...
定义
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边。
设图A=（V，E）是一个有n个顶点的图，图的邻接矩阵为Egde[n][n],则
注：W为权值，当不需要权值时，取w为1表示结点间的连接。
- 无向图的邻接矩阵是对称的
- 有向图的邻接矩阵是不对称的
邻接矩阵的结构
头结点
typedef struct _tag_MGraph {
int count;
//存储图的结点
MVertex** v;
//邻接矩阵存储边
int** matrix;
} TMGraph;
- count记录顶点个数
- v记录顶点信息
- matrix邻接矩阵存储图中顶点间的边
动态申请二位数组
- 通过二级指针动态申请一维指针数组
- 通过一级指针申请数据空间
- 将一维指针数组中的指针连接到数据空间
int** malloc2d(int row, int col) {
int** ret = (int**)malloc(sizeof(int*) * row);
int* p = (int*)malloc(sizeof(int) * row * col);
int i = 0;
if (p && ret) {
for(i = 0; i < row; i++) {
ret = p + i * col;
}
} else {
free(ret);
free(p);
ret = NULL;
}
return ret;
}
图的遍历
从图中的某一顶点出发访遍图中的所有顶点，使得每个顶点仅被访问一次
深度优先遍历（DFS）
也称深度优先搜索，Depth First Search
整个过程需要一个标记顶点是否被访问过的数组visited[]
算法描述
- 访问起始顶点v
- 当v还有邻接顶点未访问时，深度遍历未访问过的邻接顶点w
- 当v的所有邻接顶点都被访问时，若图中所有顶点都被访问则算法结束；若图中还有未被访问的结点，则递归进行1，2步骤。
广度优先遍历(BFS)
也称广度优先搜索，Breadth First Search
整个过程需要一个标记顶点是否被访问过的数组visited[]
算法描述
- 访问起始顶点V0
- 依次访问V0的各个邻接顶点V01，V02...
- 依次访问V01，V02...的各个邻接顶点
- 若图中的所有结点均已访问则算法结束，否则访问下一顶点V2，重复上面的步骤。
代码实现
代码中使用的队列请参考数据结构⑬链式队列的优化中的队列
头文件
//
// Created by 刘涤生 on 2017/2/28 21:00.
//
#ifndef CPLUSPLUS_MGraph_H
#define CPLUSPLUS_MGraph_H
typedef void MGraph;
typedef void MVertex;
typedef void (MGraph_Printf)(MVertex*);
/**
* 创建并返回有n个顶点的图
* @param n
* @return
*/
MGraph* MGraph_create(MVertex** v,int n);
/**
* 销毁图
* @param MGraph
*/
void MGraph_destroy(MGraph* MGraph);
/**
* 清空图
* @param MGraph
*/
void MGraph_clear(MGraph* MGraph);
/**
* 在顶点v1和v2之间加上边
* @param MGraph
* @param v1
* @param v2
* @param w 边的权值
* @return
*/
int MGraph_add_edge(MGraph* MGraph,int v1,int v2,int w);
/**
* 将顶点v1和v2之间的边删除
* @param MGraph
* @param v1
* @param v2
* @return 权值
*/
int MGraph_remove_edge(MGraph* MGraph,int v1,int v2);
/**
* 获取顶点v1和v2之间的边的权值
* @param MGraph
* @param v1
* @param v2
* @return
*/
int MGraph_get_edge(MGraph* MGraph,int v1,int v2);
/**
* 获取图中V顶点的度
* @param MGraph
* @param v
* @return
*/
int MGraph_degree(MGraph* MGraph,int v);
/**
* 获取图中的结点数
* @param MGraph
* @return
*/
int MGraph_vertex_count(MGraph* MGraph);
/**
* 获取图中的边数
* @param MGraph
* @return
*/
int MGraph_edge_count(MGraph* MGraph);
/**
* 深度优先遍历
* @param graph
* @param v 顶点的位置
* @param pFunc
*/
void MGraph_DFS(MGraph* graph,int v,MGraph_Printf* pFunc);
/**
* 广度优先遍历
* @param graph
* @param v
* @param pFunc
*/
void MGraph_BFS(MGraph* graph,int v,MGraph_Printf* pFunc);
/**
* 打印图
* @param graph
* @param pFunc 指针打印函数
* @return
*/
void MGraph_Display(MGraph* graph,MGraph_Printf* pFunc);
#endif
实现文件
//
// 邻接矩阵法实现图
// Created by 刘涤生 on 2017/2/28 21:00.
//
#include "MGraph.h"
#include "LinkQueue.h"
#include
#include
typedef struct _tag_MGraph {
int count;
//存储图的结点
MVertex** v;
//邻接矩阵存储边
int** matrix;
} TMGraph;
static void recursive_dfs(TMGraph* graph,int v,int visited[],MGraph_Printf* pFunc) {
//访问顶点
int i = 0;
pFunc(graph->v[v]);
//遍历后置为1
visited[v] = 1;
printf(", ");
//遍历顶点v相关联的顶点
for(i = 0; i < graph->count; i++) {
//顶点间需要有边
if ((graph->matrix[v] != 0) && !visited) {
recursive_dfs(graph,i,visited,pFunc);
}
}
}
static void bfs(TMGraph* graph,int v,int visited[],MGraph_Printf* pFunc) {
LinkQueue* queue = LinkQueue_Create();
if (queue != NULL) {
//将该顶点及其相关的顶点依次存入队列中
LinkQueue_Offer(queue,graph->v + v);
visited[v] = 1;
while (LinkQueue_Size(queue) > 0) {
int i = 0;
//取出序号
v = (MVertex**)LinkQueue_Poll(queue) - graph->v;
pFunc(graph->v[v]);
printf(", ");
//遍历该顶点中邻接链表中的结点
for(i = 0; i < graph->count; i++) {
if ((graph->matrix[v]) && !visited) {
LinkQueue_Offer(queue,graph->v + i);
visited = 1;
}
}
}
}
LinkQueue_Destroy(queue);
}
//o(n)
MGraph* MGraph_create(MVertex** v,int n) {
TMGraph* ret = NULL;
if ((v != NULL) && (n > 0)) {
ret = (TMGraph*)malloc(sizeof(TMGraph));
if (ret != NULL) {
int * p = NULL;
ret->count = n;
ret->v = (MVertex**)malloc(sizeof(MVertex*) * n);
ret->matrix = (int**)malloc(sizeof(int*) * n);
//动态申请数据空间
p = (int*)calloc(n * n,sizeof(int));
if ((ret->v != NULL) && (ret->matrix != NULL) && (p != NULL)) {
int i = 0;
for (i = 0; i < n; i++) {
//连接到数据空间
ret->v = v;
ret->matrix = p + i * n;
}
} else {
free(p);
free(ret->matrix);
free(ret->v);
free(ret);
}
}
}
return ret;
}
//o(n)
void MGraph_destroy(MGraph* graph) {
TMGraph* tGraph = (TMGraph*)graph;
if (tGraph != NULL) {
//顺序不能乱
free(tGraph->v);
//释放数据空间
free(tGraph->matrix[0]);
free(tGraph->matrix);
free(tGraph);
}
}
//o(n^2)
void MGraph_clear(MGraph* graph) {
TMGraph* tGraph = (TMGraph*)graph;
if (tGraph != NULL) {
int i = 0;
int j = 0;
for (i = 0; i < tGraph->count; i++) {
for (j = 0; j < tGraph->count; j++) {
tGraph->matrix[j] = 0;
}
}
}
}
//O(1)
int MGraph_add_edge(MGraph* graph,int v1,int v2,int w) {
TMGraph* tGraph = (TMGraph*)graph;
int ret = (tGraph != NULL);
ret = ret && (0 count);
ret = ret && (0 count);
ret = ret && (0 matrix[v1][v2] = w;
}
return ret;
}
//O(1)
int MGraph_remove_edge(MGraph* graph, int v1, int v2) {
int ret = MGraph_get_edge(graph,v1,v2);
if (ret != 0) {
((TMGraph*)graph)->matrix[v1][v2] = 0;
}
return ret;
}
//O(1)
int MGraph_get_edge(MGraph* graph,int v1,int v2) {
TMGraph* tGraph = (TMGraph*)graph;
int condition = (tGraph != NULL);
condition = condition && (0 count);
condition = condition && (0 count);
int ret = 0;
if (condition) {
ret = tGraph->matrix[v1][v2];
}
return ret;
}
//O(n)
int MGraph_degree(MGraph* graph,int v) {
TMGraph* tGraph = (TMGraph*)graph;
int condition = (tGraph != NULL);
condition = condition && (0 count);
int ret = 0;
if (condition) {
int i = 0;
for (i = 0; i < tGraph->count; i++) {
if (tGraph->matrix[v] != 0) {
ret++;
}
if (tGraph->matrix[v] != 0) {
ret++;
}
}
}
return ret;
}
//O(1)
int MGraph_vertex_count(MGraph* graph) {
TMGraph* tGraph = (TMGraph*)graph;
int ret = 0;
if (tGraph != NULL) {
ret = tGraph->count;
}
return ret;
}
//O(n^2)
int MGraph_edge_count(MGraph* graph) {
TMGraph* tGraph = (TMGraph*)graph;
int ret = 0;
if (tGraph != NULL) {
int i = 0;
int j = 0;
for (i = 0; i < tGraph->count; i++) {
for (j = 0; j < tGraph->count; j++) {
if(tGraph->matrix[j] != 0) {
//如果是无向图 ret除以2
ret++;
}
}
}
}
return ret;
}
void MGraph_DFS(MGraph* graph,int v,MGraph_Printf* pFunc) {
TMGraph *tGraph = (TMGraph *) graph;
int* visited = (int*)calloc(tGraph->count,sizeof(int));
int condition = (tGraph != NULL);
condition = condition && (0 count);
condition = condition && (pFunc != NULL);
condition = condition && (visited != NULL);
if (condition) {
recursive_dfs(tGraph,v,visited,pFunc);
//遍历其他顶点
int i = 0;
for (i = 0; i < tGraph->count; i++) {
if (!visited) {
recursive_dfs(graph,i,visited,pFunc);
}
}
}
free(visited);
}
void MGraph_BFS(MGraph* graph,int v,MGraph_Printf* pFunc) {
TMGraph *tGraph = (TMGraph *) graph;
int* visited = (int*)calloc(tGraph->count,sizeof(int));
int condition = (tGraph != NULL);
condition = condition && (0 count);
condition = condition && (pFunc != NULL);
condition = condition && (visited != NULL);
if (condition) {
bfs(graph,v,visited,pFunc);
//遍历其他顶点
int i = 0;
for (i = 0; i < tGraph->count; i++) {
if (!visited) {
bfs(graph,i,visited,pFunc);
}
}
}
free(visited);
}
//O(n^2)
void MGraph_Display(MGraph* graph,MGraph_Printf* pFunc) {
TMGraph* tGraph = (TMGraph*)graph;
if ((tGraph != NULL) && ( pFunc != NULL)) {
int i = 0;
int j = 0;
for (int i = 0; i < tGraph->count; i++) {
printf("%d:",i);
pFunc(tGraph->v);
printf(" ");
}
printf("");
printf("边及权值");
for (int i = 0; i < tGraph->count; i++) {
for (int j = 0; j < tGraph->count; j++) {
if (tGraph ->matrix[j] != 0) {
printf("");
printf(" ");
}
}
}
printf("");
}
}测试文件
//
// Created by 刘涤生 on 2017/1/11 21:47.
//
#include
#include "graph/MGraph.h"
void print_data(MVertex* mVertex) {
printf("%s",(char*)mVertex);
}
int main() {
MVertex* v[] = {"A","B","C","D","E"};
MGraph* graph = MGraph_create(v,5);
MGraph_add_edge(graph,0,1,1);
MGraph_add_edge(graph,1,2,1);
MGraph_add_edge(graph,2,3,1);
MGraph_add_edge(graph,2,4,1);
MGraph_add_edge(graph,3,4,9);
printf("顶点间的权值 = %d
",MGraph_get_edge(graph,2,3));
printf("图中边的数量 = %d
",MGraph_edge_count(graph));
printf("结点数 = %d
",MGraph_vertex_count(graph));
printf("顶点的度 = %d
",MGraph_degree(graph,1));
printf("打印图");
MGraph_Display(graph,print_data);
printf("从C开始图的深度优先遍历");
MGraph_DFS(graph,2,print_data);
printf("");
printf("从B开始图的广度优先遍历");
MGraph_BFS(graph,1,print_data);
printf("");
printf("删除边");
MGraph_remove_edge(graph,2,3);
MGraph_Display(graph,print_data);
MGraph_clear(graph);
printf("结点数 = %d
",MGraph_vertex_count(graph));
printf("图中边的数量 = %d
",MGraph_edge_count(graph));
printf("顶点的度 = %d
",MGraph_degree(graph,1));
MGraph_destroy(graph);
}
顶点间的权值 = 1
图中边的数量 = 5
结点数 = 5
顶点的度 = 2
打印图
0:A 1:B 2:C 3:D 4:E
边及权值
从C开始图的深度优先遍历
C, D, E, A, B,
从B开始图的广度优先遍历
B, C, D, E, A,
删除边
0:A 1:B 2:C 3:D 4:E
边及权值
结点数 = 5
图中边的数量 = 0
顶点的度 = 0小结
- 邻接矩阵法优点：直观容易实现
- 缺点：当顶点较多而边数较少时浪费时间和空间
关注 刘涤生
微信扫一扫关注公众号
