带权值的有向图和网的关系

有向网 有向图 无向网 无向图是什么意思？ 急！~

图是一种数据结构（你可以参考任何一本数据结构的的书，有形象的描述），图由点集和边集组成，边集为点与点之间的连线的集合，边有方向，叫有向图，边无方向叫无向图，边有权值，就叫网

class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN);
ListNode* cur = head;
while (cur !=nullptr)
{
ListNode* pos = findInsertPos(&dummy, cur->val);
ListNode* tmp = cur->next; //记录当前遍历节点的下一个节点，以便继续遍历下个节点
cur->next = pos->next;
pos->next = cur;
cur = tmp;
}

区别是带不带“权”也就是权值 无向网是有的 而无向图是没有的 类似的有向网和有向图。

有/无 向图如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。[编辑]简单图一个图如果没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；每条边所关联的是两个不同的顶点则称为简单图(simple graph)。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如(x,x)的序对不能属于E。而无向图的边集必须是对称的，即如果 ，那么 。[编辑]多重图若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。[编辑]基本术语在顶点1有一个环阶（Order）：图G中顶集V的大小称作图G的阶。子图（Sub-Graph）：图G'称作图G的子图如果以及 。生成子图（Spanning Sub-Graph）：指满足条件V(G') =V(G)的G的子图G。度（Degree）是一个顶点的度是指与该顶点相关联的总边数，顶点v的度记作d(v)。度和边有如下关系：。出度(out-degree) 和入度 (in-degree)：对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为 do ，是指有 do 条边以该顶点为起点，或说与该点关联的出边共有do条。入度的概念也类似。邻接矩阵环(loop)：若一条边的两个顶点相同，则此边称作环。路径（path）：从顶点 u 到顶点 v 的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk， ei的起点终点为vi及vi - 1； k 称作路径的长度； v_0=u，称为路径的起点； v_k=v，称为路径的终点。如果 u=v，称该路径是闭的，反之则称为开的；如果 v_1 , ... , v_k 两两不等，则称之为简单路径(simple path)（注意，u=v 是允许的）。行迹（trace）：如果路径P(u,v)中边各不相同，则该路径称为u到v的一条行迹。轨道（track）：即简单路径。闭的行迹称作回路（circuit），闭的轨道称作圈（Cycle）。（现存文献中的命名法并无统一标准。比如在另一种定义中，walk 对应上述的 path，path 对应上述的 track ， trail 对应上述的 trace。）距离（distance）： 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称作从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。距离矩阵桥（bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。[编辑]图的存储表示数组（邻接矩阵）存储表示（有向或无向）邻接表存储表示前向星存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。[编辑]图的遍历图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); //对尚未访问的顶点调用DFS}void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); //访问第v个顶点for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)，//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空(0)。 if(!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS}图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void BFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit;for(v=0; v<G.vexnum, ++v) visited[v] = FALSE; initQueue(Q); //置空辅助队列Q for(v=0; v<G.vexnum; ++v) if(!visited[v]){ visited[v]=TRUE; VisitFunc(v); EnQueue(Q, v); //v入队列 while(!QueueEmpty(Q)){ DeQueue(Q, u); //队头元素出队并置为u for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w为u的尚未访问的邻接顶点 Visited[w]=TRUE; VisitFunc(w); EnQueue(Q, w); } } }}
[编辑]图的重要类型树平面图连通图强连通图有向无环图AOV网AOE网完全图：每一对不同顶点间都有边相连的的图，记作Kn。二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。正则图：如果图中所有顶点的度皆相等，则此图称为正则图欧拉图:存在经过所有边一次(可以多次经过点)的路径的图哈密顿图:存在经过所有点一次的路径的图

---

微山县18384905767： 问个数据结构的问题:有权图 和 网 的区别是什么? - ？
陶路怡神： 边上带权的图称网,两个词的含义基本相同

微山县18384905767： 请学过计算机专业的专业人士解答(最好是学过数据结构的) - ？
陶路怡神： 1.对对于连通的带权图,其生成树也是带权的.生成树各边的权值总和称为该树的权.2.对AOE网(Activity On Edge)即边表示活动的网.AOE-网也是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间.利用...

微山县18384905767： 关于C语言数据结构中的图的一些问题 - ？
陶路怡神： 图的定义图(Graph)是由非空的顶点集合和一个描述顶点之间关系――边(或者弧)的集合组成,其形式化定义为:G=(V,E)V={vi| vi∈dataobject}E={( vi,vj)| vi, vj ∈V ∧P(vi, vj)} 其中,G表示一个图,V是图G中顶点的集合,E是图G中边的...

微山县18384905767： 数据结构邻接矩阵矩阵 - ？
陶路怡神： 的确错了,首先:这是有向图,因为弧是有序偶(用尖括号)<1,2>........ 所以,画图时必须用箭头,如:①→②; 第三说明一点,带权值的图也叫网,有无向网和有向网,有向图不带权值 自己再画试试

微山县18384905767： 数据结构的“图的生成树”是如何定义的? - ？
陶路怡神： 定义1:对于无向图G和一棵树T来说,如果T是G的子图,则称T为G的树,如果T是G的生成子图,则称T是G的生成树. 定义2:对于一个边上具有权值的图来说,其边权值和最小的生成树称做图G的最小生成树. 若一个无向图G的生成子图是一...

微山县18384905767： 关键路径含义?是否最多只有一条 - ？
陶路怡神： 是的. aoe (activity on edges)网络 :如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(activity),用边上的权值表示活动的持续时间(duration), 用顶点表示事件(event),则这样的有向图叫做用边表示活动的网络,简...

微山县18384905767： 叶子结点带权的二叉树是什么意思(注:树结点间的边相关的数叫做权) 这句话怎么理解 - ？
陶路怡神： 你说的是哈夫曼树吧?树的每个节点数据域data可以放一个特定的数来代表它的值,可以叫做权值. 以下来自百科: 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 2、结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积. 3、树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL.

微山县18384905767： 网络图是是带权有向图还是带权图 - ？
陶路怡神： 是带权有向图

微山县18384905767： 最优二叉树算法的基本概念 - ？
陶路怡神： 最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.那么什么是二叉树的带权路径长度呢?在前面我们介绍过路径和结点的路径长度的概念,而二叉树的路径长度则是...

微山县18384905767： OD矩阵和邻接矩阵是一回事么? - ？
陶路怡神： 这是图论的知识,OD矩阵是图顶点的出度的矩阵 图的邻接矩阵如下介绍1.图的邻接矩阵表示法在图的邻接矩阵表示法中: ① 用邻接矩阵表示顶点间的相邻关系 ② 用一个顺序表来存储顶点信息2.图的邻接矩阵(Adacency Matrix)设G=(V,E)是...