数据结构 图 部分 问题

几个关于数据结构中图的问题！~

对于第一个问题： 权值一般代表一个抽象出来的路径长度，你想想既然是长度会是负数吗，如果你硬要说有，其实也无妨，“一个正常的图每个边都减去一个同样大的值不是为负了吗？”，这种做法并不影响程序的运行，只是失去了一些实际上的意义而已 第二个问题：迪杰斯特拉算法在求1：从一个源点到其他结点的最短路径时时间复杂度是O（n2），2：求每一对顶点间的最短路径其实就是多套一层for循环，这是当然是O（n3）了啊，这时和Floyd算法复杂度一样 5555回答完了哦

我测试过你这段代码，是没有问题的。
从 bug 的提示来看，我猜测应该是你载入的 .h 文档有重复的定义导致的，请检查其他地方是否也定义了 VertexType 这个结构


我在 VC6 上测试下面的代码是没有问题的，你可以看看

#include

typedef int InfoType;
#define MAXV 100 //最大顶点个数
//以下定义邻接矩阵类型
typedef struct
{
int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{
int edges[MAXV][MAXV]; //邻接矩阵
int vexnum,arcnum; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode //弧的结点结构类型
{
int adjvex; //该弧的终点位置
struct ANode *nextarc; //指向下一条弧的指针
InfoType info; //该弧的相关信息,这里用于存放权值
} ArcNode;
typedef int Vertex;
typedef struct Vnode //邻接表头结点的类型
{
Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
void main()
{
VertexType a;
MGraph b;
ArcNode c;
VNode d;
ALGraph e;
}

（3）写出以V1为出发点对图进行广度优先搜索所得到的所有可能的访问序列共有24种：记住一句话“先被访问的顶点的邻接点优先于后被访问的顶点的邻接点先被访问”V1被遍历后，V1的邻接点要优先被遍历，V1的邻接点有4个：V2，V3，V4，V6，所以主要是结点V2，V3，V4，V6的排列顺序的不同。第一个被遍历的结点是V1，最后一个被遍历的结点是V5。分别用1，2，3，4，5，6表示结点V1，V2，V3，V4，V5，V6。123465123645124365124635126345126435132465132645134265134625136245136425142365142635143265143625146235146325162345162435163245163425164235164325（4）写出以V1为出发点对图进行深度优先搜索所得到的所有可能的访问序列。深度优先遍历 即邻接点优先遍历，也就是说某一顶点（Vm）被遍历后，只要该结点还有邻接点(Vn)未被遍历，则遍历该结点(Vn)。第一种遍历：V1，V2，V4，V6，V5，V3。第二种遍历：V1，V3，V5，V2，V4，V6。第三种遍历：V1，V3，V5，V4，V6，V2。第四种遍历：V1，V4，V6，V5，V2，V3。第五种遍历：V1，V4，V6，V5，V3，V2。第六种遍历：V1，V6，V5，V2，V4，V3。第七种遍历：V1，V6，V5，V3，V2，V4。第八种遍历：V1，V6，V5，V3，V4，V2。第九种遍历：V1，V6，V5，V4，V2，V3。第十种遍历：V1，V6，V5，V4，V3，V2。 2、假设第1题的图是无向图（即不要箭头），分别按克鲁斯卡尔 (Kruskal)算法和普里姆（prim）算法求它的最小生成树。普里姆（prim）算法： 克鲁斯卡尔 (Kruskal)算法：

同学这不是书上基本上一样的哈！？
多看书就回了的，我这手机看不到图不好帮你！
相信你自己能攻克的！

---

凤庆县18953689810： 数据结构 图的问题、.一个n个顶点的有向强连通图最多有 条边,最少有 条边.一个n个顶点的无向连通图最多有 条边,最少有 条边. - ？
鄂艺红花：[答案] 一个n个顶点的有向强连通图最多有 n(n-1) 条边,最少有 n 条边. 一个n个顶点的无向连通图最多有n(n-1) /2 条边,最少有 n-1 条边.

凤庆县18953689810： 关于C语言数据结构中的图的一些问题 - ？
鄂艺红花： G有两个集合V和E组成,记为G=(V,E)这句就是说,图G是由顶点(V)和边(E)组成的,因为顶点和边都可以有多个,所以可以说是顶点的集合和边的集合,可以记为G=(V,E);V是顶点的有穷非空集合这句就是说,一个图形,必须要先有点才能画成图,就比如一个三角形,要先有顶点,才能画边是一样的道理,点是必须存在而且是有限的,这样才能够成图形,所以说顶点是有穷非空集合;E是边的集合上边已经说过了,因为边可以有多个,所以E可以说是边的集合边是V中顶点的偶对,一个图形,比如三角形,每个顶点都由两条边连着,一对,所以说是偶对.E可以是空集,若E为空,则G只有顶点没有边一个点也可以是图形,可以没有边,没有边的图形也就只剩下顶点了

凤庆县18953689810： 数据结构的问题在一个图中,所有顶点的度数之和等于图的边数的2倍. 1、 错 2、 对 2.有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的入度.... - ？
鄂艺红花：[答案] 在一个图中,所有顶点的度数之和等于图的边数的2倍.2、 对 2.有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i... 2、 对 5.为了实现图的遍历,其深度优先搜索算法使用的一个辅助数据结构为() .a、栈 6.二叉树是非线性数据结构,所以...

凤庆县18953689810： 有关数据结构的几个问题? - ？
鄂艺红花： 数据结构是计算机存储、组织数据的方式.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合.通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率的算法.数据结构往往同高效的检索算法和索引技术有关.

凤庆县18953689810： 数据结构问题 - ？
鄂艺红花： 谈谈如何学习数据结构: 1.如果你没有学过C语言,或者C语言学的不好的时候把数据结构当成一本数学书来学,它所讲述的都是一些简单的图论.在你的大脑中的主线不能丢失:线性结构,树结构和图结构.当你不再考虑复杂的程序设计时,...

凤庆县18953689810： 设N个顶点E条边的图用邻接表存储,则求每个顶点入度的时间复杂度为...？
鄂艺红花： 对于头的部分,删除操作是将头指针指向第二个结点即可;插入操作为将头指针指向新结点,新结点指向新插入的结点即可 对于尾的部分,因为有尾指针,相当于我们能获取到尾结点,指向新结点即可完成插入操作;但是由于是单链表,尾结点中不存在指向前驱的指针,而删除操作需要把倒数第二个结点的next指针置null,所以只能从头开始遍历,故此选项与长度有关!

凤庆县18953689810： 数据结构链表部分问题 - ？
鄂艺红花： 不一样,第一题是在p之前插入结点,第二题在p之后插入结点.

凤庆县18953689810： 有关数据结构的问题? - ？
鄂艺红花： 例如,记录的存储方式是顺序结构存储还是B树结构存储1.三个层次是: 1)模式 模式也称逻辑模式或概念模式,定义与数据有关的安全性;数据的存储记录结构有何规定等. 2.两级映象(纠正一下你的说法,不是两级映射) 1)外模式/模式映...

凤庆县18953689810： 超难数据结构问题!!!!!？
鄂艺红花： 1.排序,在任意位置插入元素,在删除任意位置的元素. 2.有.分别为20和21.因为21>10*2 3.折半查找只适用于有序表,且限于顺序存储结构. 顺序查找的ASL为(n+1)/2,折半查找的ASL为(log(下标2)(n+1)-1).所以在顺序表的查找中,折半查找的效率比顺序查找高. 4.快速排序平均性能最佳.直接插入辅助空间要求最少.shell排序,堆排序,快速排序不稳定.