数据结构C语言实现----图
2024-09-07 19:04:11
邻接表储存结构
/*邻接表的边*/
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
/*邻接表的结点*/
typedef struct VNode
{
char date;
ArcNode *firstarc;
}VNode;
创建一个邻接表储存结构的图
//创建一个邻接表类型的图
void CreatArcGraph(int count , VNode G[])
{
ArcNode *p , *q;
char c; //储存结点内数据
int number; //储存要连接的结点
printf("请输入各个结点的数据：\n");
for (size_t i = 0; i < count; i++) //初始化数组，输入各结点数据
{
fflush(stdin);
printf("请输入第%d个结点内存入的字符：" , i);
c = getchar();
G[i].date = c;
G[i].firstarc = NULL;
}
图的遍历（1）-----深度优先搜索
//深度优先搜索一个连通图
void DFS(VNode G[] , int v)
{
int w;
printf("%c" , G[v].date); //访问当前结点
printfed[v] = 1;
w = FirstAdj(G , v);
while (w!=-1)
{
if (printfed[w]==0)
DFS(G,w);
w = NextAdj(G , v);
}
}
//对图G = （V，E）进行深度优化搜索的主算法
void Travel_DFS(VNode G[] , int n)
{
for (size_t i = 0; i < n; i++)
{
printfed[i] = 0;
}
for (size_t i = 0; i < n; i++)
{
if (printfed[i]==0)
{
DFS(G,i);
}
}
}
深度优先搜索实例
#include<stdio.h>
#include<stdlib.h>
/*邻接表的边*/
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
/*邻接表的结点*/
typedef struct VNode
{
char date;
ArcNode *firstarc;
}VNode; //创建一个邻接表类型的图
void CreatArcGraph(int count , VNode G[])
{
ArcNode *p , *q;
char c; //储存结点内数据
int number; //储存要连接的结点
printf("请输入各个结点的数据：\n");
for (size_t i = 0; i < count; i++) //初始化数组，输入各结点数据
{
fflush(stdin);
printf("请输入第%d个结点内存入的字符：" , i);
c = getchar();
G[i].date = c;
G[i].firstarc = NULL;
//putchar('\n');
}
for (size_t i = 0; i < count; i++) //创建边
{
printf("请输入第%d个结点要连接的结点(各个结点以空格隔开）：",i);
scanf("%d" , &number);
while (number!=-1)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->next = NULL;
p->adjvex = number;
if (G[i].firstarc == NULL)
{
G[i].firstarc = p;
}else
{
q->next = p;
}
q = p;
scanf("%d" , &number);
}
}
}
int printfed[3];
//寻找第一个邻接点
int FirstAdj(VNode G[] , int v)
{
return G[v].firstarc->adjvex;
}
//寻找下一个邻接点
int NextAdj(VNode G[] , int v)
{
ArcNode *p;
p = G[v].firstarc->next;
while (p->next!=NULL )
{
p = p->next;
if (printfed[p->adjvex]==0)
{
return p->adjvex;
}
}
return -1;
}
//深度优先搜索一个连通图
void DFS(VNode G[] , int v)
{
int w;
printf("%c" , G[v].date); //访问当前结点
printfed[v] = 1;
w = FirstAdj(G , v);
while (w!=-1)
{
if (printfed[w]==0)
DFS(G,w);
w = NextAdj(G , v);
}
}
//对图G = （V，E）进行深度优化搜索的主算法
void Travel_DFS(VNode G[] , int n)
{
for (size_t i = 0; i < n; i++)
{
printfed[i] = 0;
}
for (size_t i = 0; i < n; i++)
{
if (printfed[i]==0)
{
DFS(G,i);
}
}
}
#define MAXG 100
int main()
{
int count;
VNode G[MAXG];
printf("请输入要创建的图的结点数:");
scanf("%d",&count);
CreatArcGraph(count , G);
Travel_DFS(G,count);
return 0;
}
运行结果
图的遍历（2）-------广度优先搜索
//广度优先搜索一个连通图
void BFS(VNode G[] , int v)
{
initQueue(&q);
//首先访问当前结点
printf("%c" , G[v].date);
visited[v] = 1; //访问标记
EnQueue(&q , v); //入队列
//
int w;
while (q.front==q.rear)
{
DeQueue(&q , &v);
w = Firstadj(G , v);
while (w!=-1)
{
if (visited[w]==0)
{
printf("%c",G[w].date);
EnQueue(&q , w);
visited[w] = 1;
}
w = Nextadj(G,v);
}
}
}
//广度优先搜索的主算法
void Travel_BFS(VNode G[] , int v)
{
for (size_t i = 0; i < v; i++)
{
visited[i] = 0;
}
for (size_t i = 0; i < v; i++)
{
BFS(G , i);
}
}
广度优先搜索实例
如图：
#include<stdio.h>
#include<stdlib.h>
//////////////////////////////////////////////////////////////////////////////
//储存类型定义
//图边
typedef struct ArcNode
{
int adjvex;
struct ArcNode *next;
}ArcNode;
//图结点
typedef struct VNode
{
char date;
ArcNode *firstarc;
}VNode;
//队列结点
typedef struct QNode
{
int date;
struct QNode *next;
}QNode , *QueuePtr;
//队列指针
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
////////////////////////////////////////////////////////////////////////////////
//队列操作
//创建队列
void initQueue(LinkQueue *q)
{
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
if(!q->front) exit(0);
q->front->next = NULL;
}
//入队列
void EnQueue(LinkQueue *q , int v )
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!q->front) exit(0);
p->date = v;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
//出队列
void DeQueue(LinkQueue *q , int *v)
{
if (q->front==q->rear)
{
exit(0);
}
QueuePtr p;
p = q->front->next;
*v = p->date;
q->front->next = p->next;
if (q->rear==p)
{
q->front = q->rear =NULL;
}
free(p);
}
/////////////////////////////////////////////////////////////////////////////////////
//图操作
//创建一个图（邻接表）
void CreatArcNode(VNode G[] , int count)
{
//为结点数组输入数据
char c;
printf("请输入要在各个结点存入的字符...");
for (size_t i = 0; i < count; i++)
{
fflush(stdin);
printf("请输入在第%d个结点存入的数据：",i);
c = getchar();
G[i].date = c;
G[i].firstarc = NULL;
}
//创建几条单链表连接在数组后面（创建边）
int number;
ArcNode *p , *q;
for (size_t i = 0; i < count; i++)
{
printf("请输入结点%d要指向的结点：",i);
scanf("%d",&number);
while (number!=-1)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = number;
p->next = NULL; if (G[i].firstarc==NULL)
{
G[i].firstarc = p;
}else
{
q->next = p;
}
q = p;
scanf("%d",&number);
}
}
}
/***********************************全局变量****************************************/
int visited[100];
LinkQueue q; /////////////////////////////////////////////////////////////////////////////////
//广度优先搜索操作
//寻找第一个邻接点
int Firstadj(VNode G[] , int v)
{
return G[v].firstarc->adjvex;
}
//寻找下一个邻接点
int Nextadj(VNode G[] , int v)
{
ArcNode *p;
p = G[v].firstarc->next;
while (!p->next)
{
p = p->next;
if (visited[p->adjvex]==0)
{
return p->adjvex;
}
}
return -1;
}
//广度优先搜索一个连通图
void BFS(VNode G[] , int v)
{
initQueue(&q);
//首先访问当前结点
printf("%c" , G[v].date);
visited[v] = 1; //访问标记
EnQueue(&q , v); //入队列
//
int w;
while (q.front==q.rear)
{
DeQueue(&q , &v);
w = Firstadj(G , v);
while (w!=-1)
{
if (visited[w]==0)
{
printf("%c",G[w].date);
EnQueue(&q , w);
visited[w] = 1;
}
w = Nextadj(G,v);
}
}
}
//广度优先搜索的主算法
void Travel_BFS(VNode G[] , int v)
{
for (size_t i = 0; i < v; i++)
{
visited[i] = 0;
}
for (size_t i = 0; i < v; i++)
{
BFS(G , i);
}
} int main()
{
//创建一个图
int count;
printf("请输入创建的图有几个结点：");
scanf("%d" , &count);
VNode G[count];
CreatArcNode(G,count);
//打印邻接表
for (size_t i = 0; i < count; i++)
{
ArcNode *p;
p = G[i].firstarc;
printf("第%d个结点：%c",i,G[i].date);
do
{
if(p!=NULL)
{
printf("----<%d,%c>",p->adjvex,G[p->adjvex].date);
p = p->next;
}
}while(p!=NULL);
putchar('\n');
}
//广度优先搜索
Travel_BFS(G , count);
getchar();
return 0;
}
运行结果：
最新文章
- 深入理解javascript原型和闭包（1）---一切都是对象
- SpringMVC与MyBatis整合（一）——查询人员列表
- 统计在从1到n的正整数中1出现的次数
- 20个最新的照片 PS 技巧，提升摄影水平
- Some useful links
- 利用gitbash上传项目到github
- 一个Delphi7的BUG
- Hive基础之HiveServer2 JDBC的使用
- 自适应游标共享技术02(一个简单的例子来走近ACS)
- sourcetree下回退
- Selenium稳定性 Test
- PHP学习之［第06讲］数组、多维数组和数组函数
- DBA 经典面试题(3)
- Oracle中碰到的函数和关键字收集
- ORALCE PL/SQL学习笔记
- javascript算法（一）
- tensorflow初探
- python for循环巧妙运用（迭代、列表生成式）
- 1.12 dict 字典表
- Android Gradle 自定义Task 详解