...图的邻接表和邻接矩阵数据结构的定义、创建;图的深度优先遍历...
发布网友
发布时间：2024-09-29 16:40
我来回答
共1个回答
热心网友
时间：2024-10-11 02:09
/*
程序1：邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include <stdio.h>
#include <string.h>
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
void input_data()
{
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf("%d",x);
}else
printf(" %d",x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y]) dfs(y);
p=next[p];
}
}
void bfs(int k)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while (head<tail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
int main()
{
input_data();//读入图信息。
pre();//初始化
printf("图的深度优先遍历结果:");
int i;
for (i=1;i<=n;i++)//对整张图进行dfs; 加这个for主要是为了防止不多个子图的情况
if (!flag[i])
dfs(i);
printf("\n-------------------------------------------------------------\n");
pre();//初始化
printf("图的广度优先遍历结果为:");
for (i=1;i<=n;i++)
if (!flag[i])
bfs(i);
printf("\n----------------------end------------------------------------\n");
return 0;
}/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1000
int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
void input_data()
{
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int i;
for (i=1;i<=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y]) dfs(y);
}
}
void bfs(int t)
{
int head=0,tail=1;
dl[1]=t;flag[t]=1;
while (head<tail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int i;
for (i=1;i<=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
int main()
{
input_data();
printf("图的深度优先遍历结果:");
pre();
int i;
for (i=1;i<=n;i++)
if (!flag[i])
dfs(i);
printf("\n---------------------------------------------------------------\n");
printf("图的广度优先遍历结果:");
pre();
for (i=1;i<=n;i++)
if (!flag[i])
bfs(i);
printf("\n-----------------------------end--------------------------------\n");
return 0;
}
用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建;图的深度优先...
/* 程序1：邻接表的dfs,bfs 其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。*/#include <stdio.h>#include <string.h>#define MAXM 100000#define MAXN 10000int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],hea...
非结构化数据如何可视化呈现？
通常情况下，我们会按照结构模型把系统产生的数据分为三种类型：结构化数据、半结构化数据和非结构化数据。结构化数据，即行数据，是存储在数据库里，可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据，它们可以某种标准...
...1创建图的邻接矩阵和邻接表 2验证图的深度优先、广度优先遍历算法 3...
1、邻接表表示的图中分别用DFS和BFS遍历 include <cstdio> include <cstring> include <queue> using namespace std;/// // Description: 图的邻接表的结点 struct Edge { int dest; // 目标结点下标 // int value; // 路径长度 Edge *link; ...
如何学习图论的基本知识?
1.图的定义和基本概念：了解什么是图，节点、边、路径、环等基本概念。2.图的表示方法：掌握图的邻接矩阵和邻接表两种常用的表示方法。3.图的遍历算法：学习深度优先搜索（DFS）和广度优先搜索（BFS）两种基本的图遍历算法。4.最小生成树：了解最小生成树的概念，掌握Prim算法和Kruskal算法两种求解最小...
图的遍历:深度优先搜索(邻接矩阵存放)
int visited[9]; /* 遍历标记数组 */ /*根据已有的信息建立邻接表*/ void creategraph(int node[20][2],int num)/*num指的是图的边数*/ { graph newnode; /*指向新节点的指针定义*/ graph ptr;int from; /* 边的起点 */ int to; /* 边的终点 */ int i;...
数据结构课程设计是什么
2、 主要的数据结构设计说明 图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。3、 程序的主要模板template <class Type> class Graph 4、 程序的主要函数 Graph、link()、DFTraverse()、TopologicalOrder()、TopologicalOrder()、GetVertexPos()、ShortestPath 三、上机结果及...
c语言图的遍历,邻接表存储,深度,广度优先遍历
（1）图的建立，按采用邻接表作为存储结构。（2）从指定顶点出发进行深度优先搜索遍历。（3）从指定顶点出发进行广度优先搜索遍历。include"stdio.h"include"string.h"include"stdlib.h"include"math.h"define MAX_INT 1000 define MAX_VERTEX_NUM 20 define MAX_QUEUE_NUMBER 20 typedef struct ArcNode...
图论算法理论、实现及应用目录
在图的基本概念与存储部分，详细阐述了有向图与无向图、完全图、稀疏图、稠密图、顶点与边的关系、顶点的度数与度序列、二部图、图的同构、子图与生成树以及路径与连通性等概念，同时介绍了图的邻接矩阵和邻接表存储方法，并分析了它们的优缺点。接着，文章深入探讨了图的遍历技术，包括深度优先搜索（...
如何根据带权邻接矩阵推出深度优先遍历
深度优先遍历，先访问第一行不为0的点为1，让后转至1行，找到第二个不为0 的点，3，转至3所在的行，同理找到4，再找到2 。2行中的3与前面重复，无其他不为0的点，剩下的点选5，再找到5行中不为0的点6。深度优先遍历的特点是遍历与这个点相邻的点，了解了邻接表的特点后就会觉得简单了。
计算机都包含什么课程?
1、计算机数学基础 本课程是计算机专业必修的数学基础知识。针对计算机专业的特点，加强了Mathematica数学软件的应用。包含4大模块：微积分、线性代数、概率论。在微积分模块中包含了一元微积分、常微分方程、多元微积分初步、无穷级数、数值计算初步等内容。在线性代数模块中包含了行列式、矩阵、线性方程组的...
采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历,为什么...
这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。首先访问根结点然后遍历左...
