【数据结构】图
发布时间：2020-12-15 05:54:03 所属栏目：安全 来源：网络整理
导读：图是一种更为复杂的数据结构，在数据结构中，数据元素之间的关系存在着3种关系： 线性结构 树结构 图结构 前面学习了线性结构（链表、栈、队列）和树结构（二叉树等）。以下对图结构进行学习。 一、图的概念 图（Graph）是由顶点的非空有限集合V（N大于0个顶
|
图是一种更为复杂的数据结构，在数据结构中，数据元素之间的关系存在着3种关系：
前面学习了线性结构（链表、栈、队列）和树结构（二叉树等）。以下对图结构进行学习。
一、图的概念
图（Graph）是由顶点的非空有限集合V（N大于0个顶点组成）与边的集合E（顶点之间的关系）所构成的。
若图G中每一条边都没有方向，称图G为无向图。
若图G中每一条边都有方向，称图G为有向图。
二、图的存储方式
一般数据结构书中介绍的会有4种存储方式，其中最为常见的图的存储方式为如下两种：
邻接矩阵存储方法也称为数组存储方法，核心思想是：利用两个数组来存储一个图。这两个数组一个是一维数组，用来存储图中的顶点，一个是二维数组，用来表示图中顶点之间的相互关系。该方法不适合存储稀疏图（边数目很少的图）。那么可以用邻接表存储这类图
三、图的创建 四、图的遍历 图的遍历分为两种：
对于如下的无向图：
1. 深度优先遍历代码实现如下： #include <stdio.h>
#include <stdlib.h>
typedef struct node // 图顶点结构声明
{
int vertex; // 顶点数据
struct node *nextnode; // 指向下一个顶点的指针
}*graph;
struct node head[9]; // 存储定点的结构数组，长度是6，而不是顶点数5.
int visited[9]; // 遍历记录数组
//创建图
void create_graph(int *array,int num)
{
graph newnode; // 新顶点指针
graph ptr;
int from; // 边的起点
int to; // 边的终点
int i;
for(i = 0; i < num; i++) // 读取边的循环
{
from = array[i * 2]; // 边的起点
to = array[i * 2 + 1]; // 边的终点
newnode = (graph)malloc(sizeof(struct node));
newnode->vertex = to;
newnode->nextnode = NULL;
ptr = &(head[from]);
while(ptr->nextnode != NULL)
{
ptr = ptr->nextnode;
}
ptr->nextnode = newnode;
}
}
/*--------------------------------------*/
/* 图的深度优先搜索法*/
/*--------------------------------------*/
void dfs(int current)
{
graph ptr;
visited[current] = 1; //记录已遍历过
printf("顶点[%d] ",current); //输出遍历顶点值
ptr = head[current].nextnode;
while(ptr != NULL)
{
if(visited[ptr->vertex] == 0) //若没有遍历过
{
dfs(ptr->vertex);
}
ptr = ptr->nextnode;
}
}
int main()
{
graph ptr;
int array[20][2] = {{1,2},{2,1},{1,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,7}};
int i;
for(i = 1; i <= 5; i++)
{
head[i].vertex = i; //设置定点值
head[i].nextnode = NULL; //清除图指针
visited[i] = 0; //设置遍历初值
}
create_graph(array,20); //创建图
printf("图的邻接表内容:n");
for(i = 1; i <= 8; i++)
{
printf("顶点%d => ",head[i].vertex);
ptr = head[i].nextnode;
while(ptr != NULL)
{
printf(" %d",ptr->vertex);
ptr = ptr->nextnode;
}
printf("n");
}
printf("图的深度优先遍历内容：n");
dfs(1);
printf("n");
return 0;
}
结果如下：
2. 广度优先遍历代码实现如下： #include <stdio.h>
#include <stdlib.h>
#define MAXQUEUE 10
typedef struct node // 图顶点结构声明
{
int vertex; // 顶点数据
struct node *nextnode; // 指向下一个顶点的指针
}*graph;
struct node head[9]; // 存储定点的结构数组，长度是6，而不是顶点数5.
int visited[9]; // 遍历记录数组
int queue[MAXQUEUE]; //队列的数组声明
int front = -1; //队列的队头
int rear = -1; //队列的队尾
//创建图
void create_graph(int *array,int num)
{
graph newnode; // 新顶点指针
graph ptr;
int from; // 边的起点
int to; // 边的终点
int i;
for(i = 0; i < num; i++) // 读取边的循环
{
from = array[i * 2]; // 边的起点
to = array[i * 2 + 1]; // 边的终点
newnode = (graph)malloc(sizeof(struct node));
newnode->vertex = to;
newnode->nextnode = NULL;
ptr = &(head[from]);
while(ptr->nextnode != NULL)
{
ptr = ptr->nextnode;
}
ptr->nextnode = newnode;
}
}
/*------------------------------------------*/
/* 队列数据的存入 */
/*------------------------------------------*/
int enqueue(int value)
{
if(rear >= MAXQUEUE)
{
return -1;
}
rear++;
queue[rear] = value; //存入队列
return 0;
}
/*------------------------------------------*/
/* 队列数据的取出 */
/*------------------------------------------*/
int dequeue()
{
if(front == rear)
{
return -1;
}
front++;
return queue[front]; //队列取出
}
/*--------------------------------------*/
/* 图的广度优先搜索法*/
/*--------------------------------------*/
void bfs(int current)
{
graph ptr;
enqueue(current);
visited[current] = 1;
printf("顶点[%d] ",current);
while(front != rear)
{
current = dequeue();
ptr = head[current].nextnode;
while(ptr != NULL)
{
if(visited[ptr->vertex] == 0)
{
enqueue(ptr->vertex);
visited[ptr->vertex] = 1;
printf("顶点[%d] ",ptr->vertex);
}
ptr = ptr->nextnode;
}
}
}
int main()
{
graph ptr;
int array[20][2] = {{1,ptr->vertex);
ptr = ptr->nextnode;
}
printf("n");
}
printf("图的深度优先遍历内容：n");
bfs(1);
printf("n");
return 0;
}
运行结果如下：
来自于《数据结构C语言版》 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
