#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 40
typedef int DataType;
int visited[MAXNUM]={0};//访问节点标识
int vexInNum[MAXNUM]={0};//统计节点的入度
//无向图 测试数据 8 0 1 0 2 0 3 1 2 1 4 2 5 3 1 3 6 4 0 4 1 4 6 6 4 6 7 7 6 -1 -1
//有向图 测试数据 需是无环图 做拓扑排序 5 2 0 2 1 0 1 0 4 1 3 4 3 -1 -1
/*图的邻接矩阵结构*/
typedef struct
{
int vexnum;//顶点个数
int arcs[MAXNUM][MAXNUM];//邻接矩阵
}MGraph,*PMGraph;
/*队列的定义用于广度优先遍历*/
typedef struct{
int front;//头指针
int rear;//尾指针
int count;//计数器
DataType data[MAXNUM];
}CirQueue,*PCirQueue;
//初始化
void initQueue(PCirQueue q)
{
q->front=q->rear=0;
q->count=0;
}
//判定队空
int emptyQueue(PCirQueue q)
{
return q->count==0;
}
//判定队满
int fullQueue(PCirQueue q)
{
return q->count==MAXNUM;
}
//入队
void entryQueue(PCirQueue q,DataType x)
{
if(fullQueue(q))
{
printf("队列已满\n");
exit(1);
}
q->count++;
q->data[q->rear]=x;
q->rear=(q->rear+1)%MAXNUM;
}
//出队 返回出来的元素
DataType deleteQueue(PCirQueue q)
{
DataType temp;
if(emptyQueue(q))
{
printf("队已经为空\n");
exit(1);
}
q->count--;
temp=q->data[q->front];
q->front=(q->front+1)%MAXNUM;
return temp;
}
/*图的初始化*/
void initGraph(PMGraph g)
{
int i,j,k;
printf("输入顶点个数:\n");//校验输入的顶点个数
scanf("%d",&k);
g->vexnum=k;
//初始化边信息
for(i=0;i<k;i++)
for(j=0;j<k;j++)g->arcs[i][j]=0;
printf("输入边信息:\n");
while(1)
{
scanf("%d%d",&i,&j);
if(i==-1&&j==-1)break;
g->arcs[i][j]=1;
}
}
/*图的邻接矩阵*/
void outPutGraph(PMGraph g)
{
int i,j,k;
k=g->vexnum;
for(i=0;i<k;i++)
{
for(j=0;j<k;j++)
{
printf("%-3d",g->arcs[i][j]);
}
printf("\n");
}
}
/*拓扑排序---参考深度优先遍历思路*/
void topSort(PMGraph g,int i)
{
int j;
printf("V%d ",i);
visited[i]=1;
//去掉i 到j的入度
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[i][j]==1)
{
vexInNum[j]-=1;
}
if(vexInNum[j]==0&&visited[j]==0)topSort(g,j);
}
}
void topTraver(PMGraph g)
{
int i,j;
//初始化入度点数
for(i=0;i<g->vexnum;i++)
{
vexInNum[i]=0; visited[i]=0;
}
//统计图g的各个节点的入度 数组下标标示节点 数组值表示入度数
for(i=0;i<g->vexnum;i++)
{
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[j][i]==1)vexInNum[i]+=1;
}
}
for(i=0;i<g->vexnum;i++){
if(vexInNum[i]==0&&visited[i]==0)
{
topSort(g,i);
}
}
}
/*深度优先搜索DFS*/
void DFS(PMGraph g,int i)
{
int j;
//打印表示已访问
printf("V%d ",i);
visited[i]=1;
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[i][j]==1&&!visited[j])DFS(g,j);
}
}
void DFSTraver(PMGraph g)
{
int i;
//初始化访问节点
for(i=0;i<g->vexnum;i++)visited[i]=0;
for(i=0;i<g->vexnum;i++)
{
if(!visited[i])
{
DFS(g,i);
}
}
}
/*广度优先搜索BFS 使用队列遍历*/
void BFS(PMGraph g,int i)
{
CirQueue q;
int j;
printf("V%d ",i);
visited[i]=1;
initQueue(&q);//初始化队列
entryQueue(&q,i);
while(!emptyQueue(&q))
{
int v=deleteQueue(&q);
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[v][j]==1&&visited[j]==0)
{
printf("V%d ",j);
visited[j]=1;
entryQueue(&q,j);
}
}
}
}
void BFSTraver(PMGraph g)
{
int i;
//初始化访问节点
for(i=0;i<g->vexnum;i++)visited[i]=0;
for(i=0;i<g->vexnum;i++)
{
if(!visited[i])
{
BFS(g,i);
}
}
}
/*最小生成树*/
void main()
{
MGraph *g = (PMGraph)malloc(sizeof(MGraph));
initGraph(g);
printf("图的邻接矩阵:\n");
outPutGraph(g);
printf("图的深度优先遍历:\n");
DFSTraver(g);
printf("\n图的拓扑排序:\n");
topTraver(g);
printf("\n图的广度优先遍历:\n");
BFSTraver(g);
}
分享到:
相关推荐
数据结构中有向图和无向图的c语言实现.pdf
无向图 有向图 有向网 无向网 深度优先遍历 C语言 用户操纵界面
无向图的课设,有程序和报告,内容有邻接矩阵建立无向图、邻接矩阵遍历、广度优先搜索遍历、深度优先搜索遍历、(最小生成树普里姆(Prim)算法)、单源最短路径(地杰斯特拉(Dijkstra)算法),程序打开即可运行。
图的创建,以及利用图的几种不同的存储方法而实现的不同的创建方法,对无向图,有向图,无向网,以及有向网都与很好的说明,是你学习数据结构时必不可少的好东西.,,,,
无向图是图结构的一种。本次程序利用邻接表实现无向图,并且通过广度优先遍历找到两点之间的最短路径。 2.广度优先遍历 广度优先遍历(BFS)和深度优先遍历(DFS)是图结构中最常用的遍历方式。其中广度优先遍历配合上...
无向图的邻接矩阵存储及输出无向图的邻接矩阵存储及输出
数据结构作业,建立一个有向图或者无向图,然后判断其是否是连通的
C语言版Dijkstra算法,有注释。 只是简单的Dijkstra算法的实现。
关于c 的数据结构 图方面得东西 可以对图有好的了解
随机生成有向无环图 DAG源代码示例(C语言)
里面有数据结构的一些详细信息,有关邻接表的广度和深度的测试以及怎么用C语言编写邻接表
图算法,图的性质及类型,图搜索,深度优先搜索,有向图和有向无环图,最小生成树,最短路径,网络流
要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建立好的图进行深度和广度优先遍历。具体实现要求: 1. 通过键盘输入图的顶点和边信息,分别构造一个无向图的...
求出有向无环图的所有拓扑排序序列的C语言程序实现
实现了图的基本操作,判断有向图及无向图。细分到无向图的联通不连通,和有向图的有环无环。
2. C语言的函数兼有其它语言中的函数和过程两种功能,从这个角度看,又可把函数分为有返回值函数和无返回值函数两种。 (1)有返回值函数 此类函数被调用执行完后将向调用者返回一个执行结果, 称为函数返回值。如...
最短哈密顿回路,在无向图中由一个顶点出发,不重复的遍历所有顶点,最后回到出发点,找到最短的回路,用C语言实现,
7.4.1 无向图的连通分量和生成树 7.4.2 有向图的强连通分量 7.4.3 最小生成树 7.4.4 关节点和重连通分量 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短...
数据结构题集答案(C语言版)(严蔚敏-吴伟民著)!