有向图和无向图是什么

有向图就是任意两个邻接点之间只有一条弧，而不是两条弧，只允许从一个邻接点到另一个邻接点，而不能反过来。无向图相反，就是任意两个邻接点之间有两条弧，方向是相反的，它们构成一条“边”，说明两个邻接点之间是互通的。其他的图称为混合图，图中邻接点之间即有边，又有弧的，不统一。

有向图是单向的，有箭头，例如路径可以从A节点到B节点，但不可以从B节点到A节点；无向图是双向的，没有箭头，路径可以从A到B，也可以从B到A

有向图是一个二元组<V,E>，其中1.V是非空集合，称为顶点集。2.E是V×V的子集，称为弧集。

有向网和有向图的区别：1、有向网有权值，有向图没有权值。2、图是一种数据结构，图由点集和边集组成，边集为点与点之间的连线的集合，边有方向，叫有向图，边无方向叫无向图，边有权值，就叫网。

0、1和无穷三者不可能同时出现。无向和有向无权图中用1表示能够直接到达，0表示不能一步到达。带权图中正数代表路径权值，无穷表示一步无法到达。

一个图（Graph）是表示物件与物件之间的关系的方法，是图论的基本研究对象。一个图看起来是由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称为边）组成的。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。图又有各种变体，包括简单图/多重图；有向图/无向图等，但大体上有以下两种定义方式。

你对有向与无向的理解不正确，1．有向图 若图G中的每条边都是有方向的，则称G为有向图(Digraph)。（1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。 【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。（2）有向图的表示 【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)={v1，v2，v3} E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}2．无向图 若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对(vi，vj)和(vj，vi)表示同一条边。（2）无向图的表示 【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为： V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)} V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}所以，几个顶点之间有无边或者是弧取决于两个顶点之间的方向性。

去看一下有关 图论 的书吧

首先你要知道有向图的定义有向图是一个二元组<V,E>，其中1.V是非空集合，称为顶点集。2.E是V×V的子集，称为弧集。运筹学的有向图都是带权的,所以在此基础上存在函数F:E |-> R^+,使得对于任意e∈E,存在w∈R^+,f(e)=w.其中R^+表示正实数

有向图。导航地图默认是向北的，导航行驶过程中方向则会指示所行驶的方向。所以导航地图是有向图。

1，观察有向图；2，画出矩阵框，并表示邻接点；3，从第一行开始画矩阵；4，通则写上路径长度，不同写上无穷大；5，依次画完剩余行，就画好了有向图的邻接矩阵。有向图的度：有向图入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目1，记为OD(v).顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)。度：个点的度(degree)指图中与该点相连的边数(又叫做价)。在复杂图中，自环会让度增加2。根据不同的定义还可以细分为最大度(maximumdegree)和最小度(minimumdegree)。

区别是带不带“权”也就是权值 无向网是有的 而无向图是没有的 类似的有向网和有向图。有/无 向图如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。[编辑]简单图一个图如果没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；每条边所关联的是两个不同的顶点则称为简单图(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。正则图：如果图中所有顶点的度皆相等，则此图称为正则图欧拉图:存在经过所有边一次(可以多次经过点)的路径的图哈密顿图:存在经过所有点一次的路径的图

无向图的邻接矩阵一定是对称的.因为如果一个点i到j有边,则aij=aji=1;所以都是对称的.但是有向图就不一定了,点i到j有边,aij=1,但j到i不一定有边,则aji不一定等于1、有向图用邻接矩阵更加节省存储空间.因为无向图的邻接矩阵是对称的,所以也就是多用了一些存储空间.

就是9个这个可以构造性的方法来说明构造:这样的图至少有9个顶点证明:假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图连通无向图构成条件:边=顶点数*(顶点数-1)/2顶点数>=1,所以该函数存在单调递增的单值反函数所以边与顶点为增函数关系所以28个条边的连通无向图顶点数最少为8个所以28条边的非连通无向图为9个(加入一个孤立点)

1.拓扑排序: 还有顶点未输出,但已经不存在没有前驱的顶点了2.深搜:从一个顶点出发存在搜回到自己的路径

可以含有孤立点，也可以没有一个有向图就是一个二元组<V,E>V是顶点集 E是边集孤立点就是无边关联的点有向图里可以存在一个不关联边的点。即孤立点望采纳

是有向简单图，没有重复边，也没有环。

设边数为E首先,有向连通的一个必要条件是图的无向底图连通,这意味着E >= n-1其次,证明E > n-1.因当E=n-1时,无向底图为树,任取两顶点s,t,从s到t有且只有一条无向路径,若有向路径s->t连通,则有向路径t->s必不存在.得证再次,证明E可以=n.设n个顶点v1,v2,...vn,顺次连接有向边v1v2,v2v3...vn-1vn,vnv1,这个环是有向连通的.因此最少有n条边.

如图所示为一个非有向无环图，因为A点出发向B经C可回到A，形成一个环。将从C到A的边方向改为从A到C，则变成有向无环图。中文名有向无环图外文名DAG （Directed acyclic graph）在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。性质：有向无环图的生成树个数等于入度非零的节点的入度积。

1．有向图 若图G中的每条边都是有方向的，则称G为有向图(Digraph)。（1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。 【例】表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，和是两条不同的有向边。（2）有向图的表示 【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)={v1，v2，v3} E(G1)={，，}2．无向图 若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对(vi，vj)和(vj，vi)表示同一条边。（2）无向图的表示 【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为： V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)} V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)} 注意： 在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。3．图G的顶点数n和边数e的关系（1）若G是无向图，则0≤e≤n(n-1)/2 恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)（2）若G是有向图，则0≤e≤n(n-1)。 恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

指电流或电压的大小，方向完全相同，它主要用在交流电路分析中，因交流电不仅有大小还有方向

无向图的邻接矩阵一定是对称的.因为如果一个点i到j有边,则aij=aji=1;所以都是对称的.但是有向图就不一定了,点i到j有边,aij=1,但j到i不一定有边,则aji不一定等于1、有向图用邻接矩阵更加节省存储空间.因为无向图的邻接矩阵是对称的,所以也就是多用了一些存储空间.

有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。解释如下：强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。强连通图具有如下定理：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点) 但如果所有的对应元素都相同,就无法判断是有向图还是无向图

01 首先要观察带权有向图的特点，找到表头和带权值，分析一下，这样更好画表格。 02 画出图上的表头，一共有5个，分别为0、1、2、3、4，也就是图形中圆圈里的数字。 03 画出邻接表。接着在数字0的后面画出三个格子，有一个箭头标示，然后在第一个格子里写上连接顶点，第二个格子写上带权值，接着画第二个表，第二个表的最后符号要用^来放置。 04 按照相同的方法，将所有的表都写好，很简单，参考如下。 特别提示 以上为个人经验，供大家参考。

通路叫交替行走有向图数学。根据查询相关公开信息通路图论中的概念。一个图中（无向图或有向图），点与边交替连接成为通路，一条通路有它的起点和终点叫交替行走。

稀疏和稠密是相对的，一般以比较的方式出现，比如某一图中甲乙两地。如果同一幅图判断疏密可与比例尺或者经纬线表示的距离结合，判断坡度大小。

根据集合E，顶点1发出两个弧指向2、4，顶点2发出弧指向3，顶点4发出两个弧指向2、3.拓扑序列选择无前驱顶点输出，输出后删除该顶点及其发出的弧，直到无顶点可输出时停止。故其一种拓扑序列为：1，4，2，3

A 、1

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是 比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。 图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。 1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。 2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。 7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。 8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。 9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。 10、子图：对于图G=（V，E），G"=（V",E"），若存在 V"是V的子集， E"是E的子集，则称图 G"是G的的一个子图。 11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图： 12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。 13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。 14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。 将上图存储到计算机中，请设计一个数据结构并将其合理存储起来？ 所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n个确定的顶点，即V ={v0,v1，···，vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵的元素为： A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的边 ；2，若(vi,vj）或<vi,vj>不是E(G)中的边。 若G是网，则邻接矩阵可定义为： A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。 （2）对于无向图，邻接矩阵的第i行或第i列非零元素或非&元素的个数正好是第i个顶点的度TD(vi)。 （3）对于有向图，邻接矩阵的第i行货第i列非零元素或非&元素的个数正好是第i个顶点的出度OD(vi)或如度ID(vi)。 （4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。 在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点树和边树。故可将其形式描述如下： 邻接表（Adjacency List）是图的一种顺序存储于链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。 在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。对于网的边表需再增设一个存储边上的信息（如权值等）的域（info）。

强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路(单节点除外)至少有n条边,正好可以组成一个环！

这里的有向图，应该指强连通有向图。如果允许孤点，有1条弧也行。强连通有向图，满足两个条件：（1）没有孤点；（2）任何两点A、B，至少存在1条路径，从A到B；也至少存在1条路径，从B到A。A>B>C>D,A-->D,存在；D--->A不存在。n个顶点排在一个圆周上，需要的弧最少。n条。

深搜中枚举时由大到小就是这个结果

矩阵的元素数目为N^2 也就是答案B非零元素数目为E 也就是答案C

我来试试。 既然每个顶点都在一个回路中，那么，一个回路只要有一个顶点已知，那么，这个回路里面所有的顶点都已知了。 因此，最小的n就等于图G中的极大连通分量的个数。然后根据每个顶点继续寻找下一顶点，直到所有顶点都遍历完成。 这是算法的基本思想。

如图

2倍

有向图在图中的边是有方向的，表现出来就是有个箭头指示方向，节点只能单向通信或传递消息，相当于单行道，无向图边没方向是双向的，边连接的两个节点有通路可以双向通信，类似于双行道。无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边。有向图，一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。扩展资料：的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：V(G2)={v1，v2，v3，v4}E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}V(G3)={v1，v2，v3，v4，v5，v6，v7}E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}参考资料来源：百度百科-无向图

有向图的邻接矩阵不一定是对称的，因为它是有方向的，假如从a到b是可以通行的，但是从b到a则是逆行，为0。

1．有向图 若图G中的每条边都是有方向的，则称G为有向图(Digraph)。（1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。 【例】表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，和是两条不同的有向边。（2）有向图的表示 【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)={v1，v2，v3} E(G1)={，，}2．无向图 若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。（1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对(vi，vj)和(vj，vi)表示同一条边。（2）无向图的表示 【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为： V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)} V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)} 注意： 在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。3．图G的顶点数n和边数e的关系（1）若G是无向图，则0≤e≤n(n-1)/2 恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)（2）若G是有向图，则0≤e≤n(n-1)。 恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

二者的区别：　　邻接矩阵（AdjacencyMatrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：　　①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。　　②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。　　③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

图1是电网络及其线图的例子，其中的线段称作支路，点称作节点，若每条支路都规定了方向就是有向图，否则为无向图。树定义为包含线图中所有节点但不含回路的联通子图，线图中属于该树的支路叫作树支，其它则为连支。一个线图通常有许多棵树，图2为图1(b)线图的一些树。设线图有n+1个节点和b条支路，则树支恰有n条，连支则有b-n条。利用树可以系统地找出最大数目的独立回路组，方法是选定一棵树，给树每增添一条连支，就构成一个只包含该连支的回路，并称为基本回路，这样由b-n条连支共可得出b-n个独立的基本回路组。3.1 图的矩阵表示节点和支路的关系还可用矩阵来表示。如下图3及图4。回路矩阵B是描述回路与支路间关系的（b-n）行b列的矩阵，其中的元素bij取值为1，则表示支路ej包含在回路ci中，且方向一致，取值为-1则表示方向相反，取值为0则ej不在回路ci中。B矩阵可由基本回路组或其线性组合来形成，是一个非奇异矩阵。除A、B外还有其它描述线图的矩阵，如割集矩阵、邻接矩阵等，并统称为拓扑矩阵。3.2 电网络方程式 借助于网络拓扑和矩阵方法，可以系统地建立电网络方程，并且便于用计算机处理。令Ib和Ub分别代表电网络的支路电流矢量和支路电压矢量，则可将电路的基尔霍夫电流定律(KCL)和电压定律(KVL)表示为KCL：AIb=0 (n个独立方程）KVL：BUb=O (b-n个独立方程）由此得出b个由网络拓扑性质确定的独立方程，再加上b个由支路元件性质确定的电流和电压关系式，就足以解出各支路的电流和电压(共2b个待求量）。由这三组方程还可导出含较少待求量的方程组，如节点电压方程组、回路电流方程组和节偶电压方程组等。

拓扑排序一定是三角矩阵。上三角矩阵指的主对角线下方的元素全为零，而对角矩阵指的是主对角线上方与下方的元素都为零。所以对角阵一定是上三角阵，但上三角阵不一定是对角阵。可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。非计算机应用：拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。

        加权基因共表达网络分析 (WGCNA, Weighted correlation network analysis)是基于基因的共表达特性进行基因模块聚类，以探索基因与性状之间的关联性，基因模块与性状的关联性，并筛选网络中的核心基因。 相关概念 co-expression network (共表达网络)： 一种无方向性的，加权网络，网络的节点代表基因（也可以是蛋白质、代谢产物等），网络的变可以描述基因和基因间共表达程度的高低。为了衡量基因间共表达程度的高低，在计算基因间相关系数（例如皮尔森相关系数）的基础上，对其进行β次方加权，进而可以强化强相关性节点的关系。 Weighted (加权) ：指对相关性值进行幂次运算 。 这种处理方式强化了强相关，弱化了弱相关或负相关，使得相关性数值更符合无标度网络特征，更具有生物意义。如果没有合适的 power ，一般是由于部分样品与其它样品因为某种原因差别太大导致的，可根据具体问题移除部分样品或查看后面的经验值。 Adjacency matrix(邻接矩阵) ：邻接矩阵有分布在0-1之间的数值组成，是基因和基因之间的加权相关性值构成的矩阵，用来描述节点间相关性强度。 TOM (Topological overlap matrix) ：拓扑重叠是通过比较两个节点和网络中其他节点的加权相关性来定量描述节点间相似性的方法。把邻接矩阵转换为拓扑重叠矩阵，以降低噪音和假相关，获得的新距离矩阵，这个信息可拿来构建网络或绘制TOM图。 Module(模块) ：指具有高拓扑重叠相似性的基因集，即高度内连的基因集。共表达模块是更加非相似性矩阵，利用聚类算法获得的。在无向网络中，模块内是高度 相关 的基因。在有向网络中，模块内是高度 正相关 的基因。把基因聚类成模块后，可以对每个模块进行三个层次的分析：1. 功能富集分析查看其功能特征是否与研究目的相符；2. 模块与性状进行关联分析，找出与关注性状相关度最高的模块；3. 模块与样本进行关联分析，找到样品特异高表达的模块。 Module eigengene （ME） ：给定模块的第一主成分，代表整个模块的基因表达谱，用来描述模块在各样品中的表达模式。 Module membership (MM) ：指给定基因和给定ME之间的相关系数，描述基因属于一个模块的可靠性。 Intramodular connectivity （模块内连通性） ：某一个基因的模块内连通性等同于该基因与模块内其他基因关联程度之和，该值越大说明这个基因在模块中越处于核心位置。 Connectivity (连通性) ：类似于网络中 "度"(degree)的概念。每个基因的连连通性是与其相连的基因的边属性之和。 Hub gene ：关键基因 (连接度最多或连接多个模块的基因)。 Gene significance (GS)： 基因显著性，定义单个基因与外部信息的关联性，即基因与某个性状的相关性。 基本分析流程 1.建立关系矩阵：计算两个基因表达量之间的相关系数，构建成关系矩阵。 2. 建立邻接矩阵：根据基因表达的相关系数进行加权计算，构建邻接矩阵。 3. 建立拓扑重叠矩阵：计算节点间的相异程度，将邻接矩阵转换为拓扑重叠矩阵。 4.基因模块识别：基于拓扑邻接矩阵，进行层级聚类分析，并根据设定标准切分聚类结果，获得不同的基因模块，用聚类树的分枝和不同颜色表示。 5. 核心模块选择：根据表型特征确定核心模块。 6.核心基因筛选：基于基因连通性筛选核心基因，并围绕核心基因进行网络构建WGCNA分析输入数据         鉴于WGCNA依靠基因的共表达情况进行分析，因此必须要有足够的样本数，才能保证相关系数计算的准确性；此外样本必须包含丰富的变化信息，才能鉴定出有意义的基因模块。因此WGCNA对于输入数据有一定的要求：1.不包含生物学重复的独立样本组：样本数>=8；2.包含生物学重复的样本组：样本数>=15；3. 输入数据要求是进行标准化的数据；4. 输入数据的基因数建议不要超过5000（可以根据变化程度或者表达丰度进行筛选；基因越多，运行时间越长）。

有向无环图DAG 顶点表示活动的网络AOV网：用DAG图表示一个工程，其顶点表示活动，有向边<vi,vj>表示活动vi必须先于活动vj进行 拓扑排序（由一个有向无环图的顶点组成的序列） 1.每个顶点出现且仅出现一次 2.若顶点A在序列中排在顶点B之前，则图中不存在B到A的路径 每个DAG图都有一个或多个拓扑排序序列。 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序序列中，每个顶点有唯一的前驱后继关系，再做拓扑排序时，则排序结果是唯一的。 若邻接矩阵是三角矩阵的话拓扑排序一定存在，反之不一定。 步骤 1.从DAG图中选择一个没有前驱的顶点并输出（必须在它之前进行大的活动已经都完成了） 2.从图中删除该顶点和所有以它为起点的有向边 3.重复1，2直到当前的DAG图为空或当前图中不存在无前驱的结点为止。后者说明有环。 栈 时间复杂度O(|V|+|E|) 用深度优先遍历也可以实现拓扑排序 若已知无环图，则可用拓扑排序来改进Dijkstra算法 以拓扑顺序来选取顶点，运行时间为O(|E|+|V|) 用边表示活动的网络AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销。 1.只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 2.只有在进入某一顶点的各有向边所代表的活动都已结束，该顶点所代表的事件才能发生。 仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始。仅有一个出度为0的顶点，结束结点（汇点），表示整个工程的结束。 有些活动是可以并行进行的 从源点都汇点的路径可能有多条，所有路径上的活动都完成了整个工程才算结束，所以把路径长度最大的称为 关键路径 ，其上的活动称为 关键活动 。完成整个工程的最短时间就是关键路径的长度。关键活动不能按时完成，则整个工程的完成时间都会受到影响。 事件Vk的最早发生时间Ve(k) 从开始顶点V到Vk的最长路径长度 Ve(V)=0 Ve(k)=Max{Ve(j)+Weight(Vj, Vk)} 从前往后计算 事件Vk的最迟发生时间Vl(k) 在不推迟整个工程完成的前提下，即保证它所指向的时间Vi在Ve(i)时刻能够发生时，该事件最迟必须发生的时间。 Vl(汇点)=Ve(汇点) Vl(j)=Min{Vl(k)-Weight(Vj, vk)} 从后往前计算 活动Ai的最早开始时间E(i) 等于该活动的起点所表示的事件的最早发生时间 活动Ai的最迟开始时间L(i) 等于该活动的终点所表示的事件的最迟发生时间减去该活动所需要的时间 活动Ai可以拖延的时间D(i) 其最早开始时间与最迟开始时间的差值 若为0的话，就代表该活动必须要如期完成，否则会拖延完成整个工程的进度，则该活动是关键活动。

指数分布的期望：E（X）=1/λ。指数分布的方差：D（X）=Var（X）=1/λ²。指数分布与分布指数族的分类不同，后者是包含指数分布作为其成员之一的大类概率分布，也包括正态分布，二项分布，伽马分布，泊松分布等等。六个常见分布的期望和方差：1、均匀分布，期望是（a+b）/2，方差是（b-a）的平方/12。2、二项分布，期望是np，方差是npq。3、泊松分布，期望是p，方差是p。4、指数分布，期望是1/p,方差是1/(p的平方)。5、正态分布，期望是u，方差是&的平方。6、x服从参数为p的0-1分布，则e(x)=p，d(x)=p(1-p)。

指数分布的分布函数是µ=1/λ，σ2=1/λ2。指数分布的分布函数公式是µ=1/λ，σ2=1/λ2。在概率理论和统计学中，指数分布（也称为负指数分布）是描述泊松过程中的事件之间的时间的概率分布，即事件以恒定平均速率连续且独立地发生的过程。简介在概率理论和统计学中，指数分布（也称为负指数分布）是描述泊松过程中的事件之间的时间的概率分布，即事件以恒定平均速率连续且独立地发生的过程。这是伽马分布的一个特殊情况。它是几何分布的连续模拟，它具有无记忆的关键性质。除了用于分析泊松过程外，还可以在其他各种环境中找到。指数分布与分布指数族的分类不同，后者是包含指数分布作为其成员之一的大类概率分布，也包括正态分布，二项分布，伽马分布，泊松分布等等。

指数分布的方差是θ的平方。要注意以谁为参数，若以λ为参数，则是e(x)=1/λ d(x)=1/λ²，若以1/λ为参数，则e(x)= λ，d(x)=λ²。指数分布描述了事件以恒定平均速率连续且独立地发生的过程，是一种连续概率分布。其重要特征是无记忆性，可以用来表示独立随机事件发生的时间间隔。指数方差的应用在电子元器件的可靠性研究中，通常用于描述对发生的缺陷数或系统故障数的测量结果。这种分布表现为均值越小，分布偏斜的越厉害。指数分布应用广泛，在日本的工业标准和美国军用标准中，半导体器件的抽验方案都是采用指数分布。此外，指数分布还用来描述大型复杂系统（如计算机）的平均故障间隔时间MTBF的失效分布。但是，由于指数分布具有缺乏“记忆”的特性。因而限制了它在机械可靠性研究中的应用，所谓缺乏“记忆”，是指某种产品或零件经过一段时间t0的工作后,仍然如同新的产品一样，不影响以后的工作寿命值，或者说，经过一段时间t0的工作之后，该产品的寿命分布与原来还未工作时的寿命分布相同。显然，指数分布的这种特性，与机械零件的疲劳、磨损、腐蚀、蠕变等损伤过程的实际情况是完全矛盾的，它违背了产品损伤累积和老化这一过程。所以，指数分布不能作为机械零件功能参数的分布形式。

概率密度是一个常量，概率密度函数是变化的，有一个定义域，有一个值域，可以根据自变量的值求的对应的函数值