怎么根据邻接表画深度优先图_中华文本库
题图 14 题图 16 题图 16.给出图 G: (1).画出 G 的邻接表表示图; (2).根据你画出的邻接表,以顶点①为根,画出 G 的深度优先生成树和广度优先生成树...
深度优先遍历非递归实现,图采用邻接表表示_计算机软件及应用_IT/计算机_专业资料。《数据结构》 张振宇版 C语言 习题实现1 #include &alloc.h& 2 #define MAXSIZ...
无向邻接图的深度优先遍历_IT/计算机_专业资料。理解并实现无向图邻接表的创建的算法,理解并实现无向图的深度优先遍历的算法;转换成程序并上机实现,并按要求撰写实...
基于邻接矩阵和 邻接表存储结构的递归和非递归的算 法实现 目录 20.1 概述 20.2 深度优先遍历 20.3 深度优先遍历的性质 20.4 广度优先遍历 20.5 广度优先...
D、先序遍历 5、采用邻接表存储的图,其广度优先遍历类似于二叉树的 A、按...对)( 4、一个图的广度优先搜索使是唯一的。 错)( 5、图的深度优先搜索序列...
键盘输入数据,建立一个有向图的邻接表。 2.在有向图的邻接表的基础上计算各顶点的度。 3.采用邻接表存储实现有向图的深度优先遍历。 4.采用邻接表存储实现有...
采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A )(。 A.先序遍历 B...画出由所有关键活动构成的图, 指出 哪些活动加速可使整个工程提前完成。 ...
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历_计算机软件及应用_IT/计算机_专业资料。/*【基本要求】 以邻接多重表为存储结构,实现连通无向...
所示的非连通图,建立它的邻接表,并根据邻接表写出它的深度优先搜索遍历 算法。...8-8 一个有向图 10、对图 8-9 所示的图,画出它的邻接多重表存储结构。...
A.一个图的邻接矩阵表示是唯一的 B.一个图的邻接表表示是不唯一的 C.一个...? (1)画出该图的图形; (2) 根据邻接矩阵从顶点 a 出发进行深度优先遍历和...当前位置:&&
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构第7章_图_答案
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://jz.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口#include &stdio.h&
#include &stdlib.h&
#include &stdbool.h&
#include &limits.h&
#include "aqueue.h"
#define MAX_VALUE INT_MAX
#define MAX_NUM 100
typedef char node_
typedef struct matrix
node_type vertex[MAX_NUM];//节点信息
int arcs[MAX_NUM][MAX_NUM];//矩阵
int vertexs,//节点数,边数
void g_create(Graph * graph)
printf("输入节点个数:");
scanf("%d", &graph-&vertexs);
getchar();//接受回车键
printf("输入节点信息:");
for ( i = 0; i & graph-& i++ )
scanf("%c", &graph-&vertex[i]);
getchar();
for ( i = 0; i & graph-& i++ )//初始化矩阵
for ( j = 0; j & graph-& j++ )
graph-&arcs[i][j] = MAX_VALUE;
graph-&brim = 0;//初始化边数
// i 代表行数, j 是用来循环的, k 代表列数
for ( i = 0; i & graph-& i++ )
printf("输入与%c节点相邻的节点与权值,输入#号键结束\n", graph-&vertex[i]);
for ( j = 0; j & graph-& j++ )
scanf("%c", &c);
if ( c == '#' )
getchar();
scanf("%d", &num);
for ( k = 0; k & graph-& k++ )
if ( graph-&vertex[k] != c )
graph-&arcs[i][k] =
graph-&brim++;
getchar();
graph-&brim /= 2;
void g_printMatrix(Graph * graph)//打印矩阵状态
printf("brim = %d\n", graph-&brim);
for ( i = 0; i & graph-& i++ )
for ( j = 0; j & graph-& j++ )
printf("%-10d ", graph-&arcs[i][j]);
printf("\n");
//深度优先遍历
static void dfs_graph(Graph * graph, bool visited[], const int i);
void g_depth_first_search(Graph * graph)
bool visited[graph-&vertexs];
for ( i = 0; i & graph-& i++ )
visited[i] = false;
visited[0] = true;
dfs_graph(graph, visited, 0);
printf("\n");
static void dfs_graph(Graph * graph, bool visited[], const int i)
printf("%c\t", graph-&vertex[i]);
for ( j = 0; j & graph-& j++ )//依次检查矩阵
if ( graph-&arcs[i][j] != MAX_VALUE && !visited[j] )//i 代表矩阵的行, j 代表矩阵的列
visited[j] = true;
dfs_graph(graph, visited, j);
//广度优先遍历
void g_breadth_first_search(Graph * graph)
Q//队列存储的是节点数组的下标(int)
bool visited[graph-&vertexs];
q_init(&queue);
for ( i = 0; i & graph-& i++ )
visited[i] = false;
visited[0] = true;
q_push(&queue, 0);
while ( !q_empty(&queue) )
pos = q_front(&queue);
printf("%c\t", graph-&vertex[pos]);
for ( i = 0; i & graph-& i++ )//把队头元素的邻接点入队
if ( !visited[i] && graph-&arcs[pos][i] != MAX_VALUE )
visited[i] = true;
q_push(&queue, i);
q_pop(&queue);
printf("\n");
//最小生成树prim算法
static void init_prim(Graph * graph, Graph * prim_tree);
void Prim(Graph * graph, Graph * prim_tree)
bool visited[graph-&vertexs];
int i, j, k,
int power, power_j, power_k;
for ( i = 0; i & graph-& i++ )
visited[i] = false;
init_prim(graph, prim_tree);
visited[0] = true;
for ( i = 0; i & graph-& i++ )
power = MAX_VALUE;
for ( j = 0; j & graph-& j++ )
if ( visited[j] )
for ( k = 0; k & graph-& k++ )
if ( power & graph-&arcs[j][k] && !visited[k] )
power = graph-&arcs[j][k];
//min power
if ( !visited[power_k] )
visited[power_k] = true;
prim_tree-&arcs[power_j][power_k] =
static void init_prim(Graph * graph, Graph * prim_tree)
prim_tree-&vertexs = graph-&
for ( i = 0; i & prim_tree-& i++ )//初始化节点
prim_tree-&vertex[i] = graph-&vertex[i];
for ( i = 0 ; i & prim_tree-& i++ )//初始化矩阵
for ( j = 0; j & prim_tree-& j++ )
prim_tree-&arcs[i][j] = MAX_VALUE;
//最小生成树kruskal算法
typedef struct
int//边的始点下标
int//边的终点下标
int//边的权值
static void init_kruskal(Graph * graph, Graph * kruskal_tree);
static void my_sort(Edge * arr, int size);
void kruskal(Graph * graph, Graph * kruskal_tree)
int visited[graph-&vertexs];
Edge edge[graph-&brim];
int v1, v2, vs1, vs2;
for ( i = 0; i & graph-& i++ )
visited[i] =
for ( i = 0; i & graph-& i++ )
for ( j = i + 1; j & graph-& j++ )
if ( graph-&arcs[i][j] != MAX_VALUE )
edge[k].head =
edge[k].tail =
edge[k].power = graph-&arcs[i][j];
init_kruskal(graph, kruskal_tree);
my_sort(edge, graph-&brim);
for ( i = 0; i & graph-& i++ )
v1 = edge[i].
v2 = edge[i].
vs1 = visited[v1];
vs2 = visited[v2];
kruskal_tree-&arcs[v1][v2] = graph-&arcs[v1][v2];
for ( j = 0; j & graph-& j++ )
if ( visited[j] == vs2 )
visited[j] = vs1;
static void init_kruskal(Graph * graph, Graph * kruskal_tree)
kruskal_tree-&vertexs = graph-&
kruskal_tree-&brim = graph-&
for ( i = 0; i & graph-& i++ )
kruskal_tree-&vertex[i] = graph-&vertex[i];
for ( i = 0; i & graph-& i++ )
for ( j = 0; j & graph-& j++ )
kruskal_tree-&arcs[i][j] = MAX_VALUE;
static void my_sort(Edge * arr, int size)
for ( i = 0; i & size - 1; i++ )
for ( j = i + 1; j & j++ )
if ( arr[i].power & arr[j].power )
tmp.head = arr[i].
tmp.tail = arr[i].
tmp.power = arr[i].
arr[i].head = arr[j].
arr[i].tail = arr[j].
arr[i].power = arr[j].
arr[j].head = tmp.
arr[j].tail = tmp.
arr[j].power = tmp.
int main(void)
Graph prim_
Graph kruskal_
g_create(&graph);
g_printMatrix(&graph);
printf("\n");
g_depth_first_search(&graph);
g_breadth_first_search(&graph);
Prim(&graph, &prim_tree);
g_printMatrix(&prim_tree);
g_depth_first_search(&prim_tree);
g_breadth_first_search(&prim_tree);
kruskal(&graph, &kruskal_tree);
g_printMatrix(&kruskal_tree);
#ifndef _QUEUE_H
#define _QUEUE_H
#define MAXSIZE 10
typedef struct queue
void q_init(Queue * queue);//初始化
void q_push(Queue * queue, const int data);//入队
void q_pop(Queue * queue);//出队
bool q_empty(Queue * queue);//为空
bool q_full(Queue * queue);//为满
int q_size(Queue * queue);//队大小
int q_front(Queue * queue);//队头元素
int q_back(Queue * queue);//队尾元素
void q_destroy(Queue * queue);//销毁
#endif //_QUEUE_h
#include &stdio.h&
#include &stdlib.h&
#include &assert.h&
#include &stdbool.h&
#include "aqueue.h"
void q_init(Queue * queue)
queue-&arr = (int *)malloc( sizeof(int) * MAXSIZE );//初始化数组
assert(queue-&arr != NULL);
queue-&front = 0;
queue-&rear = 0;
void q_push(Queue * queue, const int data)
if ( q_full(queue) )
queue-&arr[queue-&rear++] =//入队，队尾+1
queue-&rear = queue-&rear % MAXSIZE;//如果队尾
void q_pop(Queue * queue)
if ( q_empty(queue) )
queue-&front = ++queue-&front % MAXSIZE;//front+1，对MAXSIZE取余
bool q_empty(Queue * queue)
return queue-&front == queue-&
bool q_full(Queue * queue)
return queue-&front == (queue-&rear + 1) % MAXSIZE;
int q_size(Queue * queue)
return (queue-&rear - queue-&front) % MAXSIZE;
int q_front(Queue * queue)
assert( !q_empty(queue) );
return queue-&arr[queue-&front];
int q_back(Queue * queue)
assert( !q_empty(queue) );
return queue-&arr[queue-&rear - 1];
void q_destroy(Queue * queue)
free(queue-&arr);
阅读(...) 评论()后使用快捷导航没有帐号？
查看: 649|回复: 5
求问关于数据结构的题
新手上路, 积分 6, 距离下一级还需 94 积分
在线时间0 小时
主题帖子积分
新手上路, 积分 6, 距离下一级还需 94 积分
新手上路, 积分 6, 距离下一级还需 94 积分
请问根据图的邻接表如何画出广度优先生成树和深度优先生成树？求各位帮帮忙
新手上路, 积分 4, 距离下一级还需 96 积分
在线时间0 小时
主题帖子积分
新手上路, 积分 4, 距离下一级还需 96 积分
新手上路, 积分 4, 距离下一级还需 96 积分
新手上路, 积分 4, 距离下一级还需 96 积分
在线时间0 小时
主题帖子积分
新手上路, 积分 4, 距离下一级还需 96 积分
新手上路, 积分 4, 距离下一级还需 96 积分
把链接表的本质看懂，你就知道了
在线时间0 小时
主题帖子积分
大概意思应该是这样
顾名思义 就是广 就是把一个节点的所有邻节点都访问了 才访问下一个节点的所有邻节点
所以 在邻接表中 首先把指定节点的所有邻节点 也就是和这个节点链接的节点访问了（为了知道下一个节点还要将这些节点都依次进队列）然后从队列出出一个节点 再次进行相应的操作（访问没有访问过的接点哈 访问过的就不访问了）最后直到所有节点都访问完 就可以了
深度优先也差不多一个道理 只是要用到栈的思想。。
不知道你看懂没 表述能力太差了哈
新手上路, 积分 6, 距离下一级还需 94 积分
在线时间0 小时
主题帖子积分
新手上路, 积分 6, 距离下一级还需 94 积分
新手上路, 积分 6, 距离下一级还需 94 积分
JackxXxly 发表于
大概意思应该是这样
顾名思义 就是广 就是把一个节点的所有邻节点都访问了 才访问下一个节点的所 ...
我懂了，谢谢哈
在线时间0 小时
主题帖子积分
我爱马玉玉 发表于
我懂了，谢谢哈
您还剩5次免费下载资料的机会哦~
扫描二维码下载资料
使用手机端考研帮，进入扫一扫在“我”中打开扫一扫，扫描二维码下载资料
Powered by Discuz!