有向图

强连通图在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。即有向图G=(V,E) 中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。单向连通图如果有向图中，对于任意节点v1和v2，至少存在从v1到v2和从v2到v1的路径中的一条，则原图为单向连通图。即设G=<V,E>是有向图，如果u->v意味着图G至多包含一条从u到v的简单路径，则图G为单连通图。强连通图、连通图、单向连通图三者之间的关系是，强连通图必然是单向连通的，单向连通图必然是弱连通图。弱连通图将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

强连通分量：1、v42、v63、v1 v5 v34、v1 v3 v2入度和出度：v1:入1出2v2：入1出1v3：入3出2v4：入0出2v5：入1出2v6：入3出0

给定图G=<V,E>.设G中定点和边的交替序列为v0e1e2…el.若T满足如下条件:v(i-1)和vi是ei的端点(G为有向图时要求v(i-1)是ei的始点，vi是ei的终点)，i=1,2…,l,则称T为v0到vl的通路。vo，vl分别称为此通路的起点和终点。T中所含边的数目l称为T的长度。当v0=vl时，称通路为回路。在无向图G中，若顶点vi与vj之间存在通路，则称vi与vj是连通的。规定vi与自身是连通的。设D为一个有向图。如果略去D中各边的方向所得的无向图是连通图，则称D是弱连通图或连通图。若D中任意2顶点至少一个可达另一个，则称D是单向连通图。若D中任意2顶点都是相互可达的，则称D是强连通图。通过以上定义我们容易知道:有向图的强连通图一定是回路，否则不可互达。无向图的连通图不是回路，但是有回路的无向图一定是连通的。连通分量是指无向图中的极大连通子图。有向图中的极大强连通子图称做有向图的强连通分量。所以只需对所给出的图做分解就可得出。

是啊，那几个顶点号好像顺序不对

给定图G=<V,E>.设G中定点和边的交替序列为v0e1e2…el. 若T满足如下条件：v(i-1)和vi是ei的端点(G为有向图时要求v(i-1)是ei的始点，vi是ei的终点)，i=1,2…,l,则称T为v0到vl的通路。vo，vl分别称为此通路的起点和终点。T中所含边的数目l称为T的长度。当v0=vl时，称通路为回路。在无向图G中，若顶点vi与vj之间存在通路，则称vi与vj是连通的。规定vi与自身是连通的。设D为一个有向图。如果略去D中各边的方向所得的无向图是连通图，则称D是弱连通图或连通图。若D中任意2顶点至少一个可达另一个，则称D是单向连通图。若D中任意2顶点都是相互可达的，则称D是强连通图。通过以上定义我们容易知道:有向图的强连通图一定是回路，否则不可互达。无向图的连通图不是回路，但是有回路的无向图一定是连通的。连通分量是指无向图中的极大连通子图。有向图中的极大强连通子图称做有向图的强连通分量。所以只需对所给出的图做分解就可得出。

强连接组件似乎是指双向通信... 后面不记得这是编译原理的东西吗？ 了解到很久以前... 忘了

给定图G=<V,E>.设G中定点和边的交替序列为v0e1e2…el.若T满足如下条件：v(i-1)和vi是ei的端点(G为有向图时要求v(i-1)是ei的始点，vi是ei的终点)，i=1,2…,l,则称T为v0到vl的通路。vo，vl分别称为此通路的起点和终点。T中所含边的数目l称为T的长度。当v0=vl时，称通路为回路。在无向图G中，若顶点vi与vj之间存在通路，则称vi与vj是连通的。规定vi与自身是连通的。设D为一个有向图。如果略去D中各边的方向所得的无向图是连通图，则称D是弱连通图或连通图。若D中任意2顶点至少一个可达另一个，则称D是单向连通图。若D中任意2顶点都是相互可达的，则称D是强连通图。通过以上定义我们容易知道:有向图的强连通图一定是回路，否则不可互达。无向图的连通图不是回路，但是有回路的无向图一定是连通的。连通分量是指无向图中的极大连通子图。有向图中的极大强连通子图称做有向图的强连通分量。所以只需对所给出的图做分解就可得出。

对于一个有向图顶点的子集S，如果在S内任取两个顶点u和v，都能找到一条u道v的路径，那么称S是强连通的。如果在强连通的顶点集合S中加入其他任意顶点集合后，它都不再是强连通的，那么称S是原图的一个强连通分量。根据以上两个定义，有向图中，任意一个环上的所有点一定在某个强连通分量中，这句话应该是没问题的。只是注意这个环本身可能就是一个强连通分量，当然也可能不是，但是是强连通分量的一个子集，这是没有问题的。

行元素和是该顶点出度，列元素和是该节点入度。

http://wenku.baidu.com/view/4c0646eeb8f67c1cfad6b8f1.html 答案

可达矩阵的主对角线元素等于1，是一种规定。非对角线元素才是根据两点之间是否存在通路确定的。

有内置函数 shortestpath() 或者其他类似的 看看doc有详细说明

围观

邻接矩阵很简单，比如a到b有一条路径为5的路那么arr[a][b]=5，如果没有路，arr[a][b]=0或者一个特定的值，如果没有权的话a，b有路arr[a][b]=1否则arr[a][b]=0。计算能到的其他点，用floyed算法，如果a~b有路，b~c有路，那么a~c有路。

无向图有度的概念。直观来说若一个图中每条边都是无方向的，则称为无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示，举例如下：下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：V(G2)={v1，v2，v3，v4}；E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}。扩展资料：相关概念1、孤立点：V中不与E中任一条边关联的点称为D的孤立点。2、简单图：不含平行边的图称为简单图。3、完备图：图中任两个顶点U与u之间，恰有两条有向边(u，v)，及(v，u)，则称该有向图D为完备图。

判断无向图中是否存在回路（环）的算法描述 如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。

无向图可以看作每条边都有两个方向的有向图写成邻接矩阵的形式的话区别就很清楚:无向图的邻接矩阵一定是对称阵,而有向图则未必

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

是的，有向图顶点集的度数 等于 出度加入度。

存在 一个闭环加上一个孤立点的有向图就不是有向树

就用二维数组就行了有n个点，点的编号是0~n-1 那么就建立a[n-1][n-1]就行了其中 若a[i][j]=0 表示节点i到节点j无弧a[i][j]>0 表示节点i到节点j有弧，且其值为相应的权值无向图其实就是特殊的有向图在无向图中有a[i][j]=a[j][i]

？可以

相同。对于无向图来说，顶点的度就等于与其相邻接的顶点的个数。而对于有向图来说，由于边的方向性，顶点的度很自然地被分为了入度和出度，有向图出度与入度的计算与无向图顶点的度的计算大同小异的。

【完全有向图】有n个顶点的有向图有n(n-1)条边，则此图称为完全有向图。

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

有向图是否有环的判定算法，主要有深度优先和拓扑排序2中方法。1、拓扑排序，如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。2、Strongly Connected Components。我们可以回忆一下强连通子图的概念，就是说对于一个图的某个子图，该子图中的任意u->v,必有v->u，则这是一个强连通子图。这个限定正好是环的概念。所以我想，通过寻找图的强连通子图的方法应该可以找出一个图中到底有没有环、有几个环。3、改进的DFS单纯用DFS是不能够的。如果题目给出的是一个无向图，DFS是可以解决的。但无向图得不出正确结果的。比如：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但其实没有。 我们可以对DFS稍加变化，来解决这个问题。解决的方法如下： 图中的一个节点，根据其C[N]的值，有三种状态： 0，此节点没有被访问过 -1，被访问过至少1次，其后代节点正在被访问中 1，其后代节点都被访问过。 按照这样的假设，当按照DFS进行搜索时，碰到一个节点时有三种可能： 1、如果C[V]=0，这是一个新的节点，不做处理 2、如果C[V]=-1，说明是在访问该节点的后代的过程中访问到该节点本身，则图中有环。 3、如果C[V]=1，类似于2的推导，没有环。 在程序中加上一些特殊的处理，即可以找出图中有几个环，并记录每个环的路径.

关于欧拉图的定理　　1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；　　2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；　　3.有向连通图D是欧拉图，当且仅当D中每个结点的入度＝出度　　4.有向连通图D含有欧拉通路，当且仅当D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1。（起始点s的入读=出度+1，结束点t的出度=入度+1 或两个点的入读=出度）

基本思想是使用深度优先搜索以每个顶点作为深度优先搜索的起始结点，如果一次深度优先搜索即可访问到图中所有结点，则该结点即为根。如此每个结点作为起点执行一次深度优先搜索即可找出所有的根。算法： 深度优先搜索是一种很简单的算法，在外面套一层循环就可以了。

错的（不一定要完全只要节点都满足双向即可）有向图的邻接矩阵有可能是对称矩阵，假设任意两个结点之间如果有连接就是双向连接，这种情况下邻接矩阵就是对称矩阵

问题一：画出下图的邻接表和逆邻接表 我用PPT画了一下。请采纳。 问题二：邻接表和逆邻接表 图的邻接表，反映的是节点的 出度 邻接情况； 图的逆邻接表，反映的是节点的 入度 邻接情况。 求采纳 问题三：将下面的有向图，画出其邻接表。 1->2->3 2->4 3->4->5 4 5->4 问题四：在有向图的邻接表和逆邻接表两种存储中,那种便于顶点出度计算 10分 因此要在多个邻接顶点之间约定一种访问次序。@由于图中可能存在回路，在访问某个顶点之后，可能沿着某条路径又回到图的深度优先搜索遍历算法p88 联通的无回路的无向图，简称树。树中的悬挂点又成为树叶，其他顶点称为分支点。 问题五：已知有向图的邻接表存储结构如下图所示 深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3穿来深度优先，访问v3后，在其链表中第一个邻接顶点是v4 接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问 所以序列为v1, v3, v4, v5, v2 再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推 于是过程是先v1，再顺链将v3，v2依次访问完，然后再依次访问v3和v2的各个未访问邻接顶点，v3链表中顺链可以访问v4，v5，所以最后访问序列为v1, v3, v2, v4, v5 问题六：在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零 这句话对吗 当然不对了

1,4,2,3！！！！

答案是C有向图 m个表结点对应m条边，每条边都是有向的考概念

在有向图G中，如果对于每一对vi，vj属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。

不是，最简单的例子，四个节点，每两个组成一个强连通图（互相指向对方），但是整体却不是

解法一：深度遍历假设图以邻接矩阵表示，一条深度遍历路线中如果有结点被第二次访问到，那么有环。我们用一个变量来标记某结点的访问状态（未访问，访问过，其后结点都被访问过），然后判断每一个结点的深度遍历路线即可。因为采用邻接矩阵存储，一般至少需要将矩阵中元素的一半给过一下，由于矩阵元素个数为n^2， 因此时间复杂度就是O(n^2)。如果采用邻接表存储，则只存储了边结点(e条边，无向图是2e条边)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。解法二：拓扑排序方法是重复寻找一个入度为0的顶点，将该顶点从图中删除（即放进一个队列里存着，这个队列的顺序就是最后的拓扑排序，具体见程序），并将该结点及其所有的出边从图中删除（即该结点指向的结点的入度减1），最终若图中全为入度为1的点，则这些点至少组成一个回路。采用邻接矩阵存储时，遍历二维数组，求各顶点入度的时间复杂度是O(n^2)。 遍历所有结点，找出入度为0的结点的时间复杂度是O(n)。对于n个入度为0的结点，删除他们的出边的复杂度为O(n^2)。 所以总的复杂度为O(n^2)。对于邻接表，遍历所有边，求各顶点入度的时间复杂度是O(e)，即边的个数。遍历所有结点，找出入度为0的结点的时间复杂度是O(n)，即顶点的个数。遍历所有边，删除入度为0的结点的出边的复杂度为O(e)，即边的个数。所以总的时间复杂度是O(n+e)。

就此题来说，答案应该是一般。另外给出另一方面的分析，希望能对此题有所帮助。题目：若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为？（比原题加了个有序的）答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

先写出图的邻接矩阵a求出a^2,a^3,a^4,a^5（1）初级回路：a，a^2,a^3,a^4中主对角线上元素的和（2）a^4中第1行第2列的元素a^5中第1行第1列的元素（3）v1,v3,v4（4）a+a^2+a^3+a^4然后将所有非0元素改为1就是可达矩阵

问题来源于做题 力扣-顺丰科技智慧物流校园技术挑战赛 中的第一题。 没阅读《剑指Offer》之前看到题时不会做，在阅读过程中有自己的解题想法，也看到《剑指Offer》中提到的解法。先按自己的想法实现，结果发现了自己想法的误区，所以在这里记录一下误区及原因，以及正确的解法。 如下图，红线为故意加入的一个导致有向图中形成环。 如上图中节点 8 被两个箭头指向，所以它的入度为 2；有一个指向 12 的箭头，所以出度为 1。同理，上图节点 5入度为 1，出度为 2。 考虑到有环，所以直观的想法是：沿着路走，如果某条路一直导致重复走某些节点，那么就证明存在环。 细节： 问题就出在判断有环的条件上，你不好判断某几个点是一直在循环。考虑如下几点： 考虑边是正确的想法。但如何判断有环条件还需要进一步考虑细节： 但上方最后一个方案还是有问题的：没有考虑 “孤岛” 的存在，如只有一个 A 节点没有入度也没有出度，或 A、B 节点相互有向连接。如果加逻辑判断又该怎么加呢？ 此时已经差不多很接近正确的解法了，具体参考下节吧。 《剑指Offer-专项突击版》在图-拓扑排序 一节中有提到解法。文中主要讲的是拓扑排序，我这里转化一下针对于查环描述： 每次从有向图中取出一个入度为 0 的节点删除，同时删除该节点及所有以他为起点的边，若最终图为空则证明无环，最终非空则证明有环。 为什么呢？：我们来单独考虑一个单环，那么环中每一个点都是入度为 1，出度也为 1，即不可能入度为 0。按上面删环的描述过程，如果环存在，这个环中的的每个点都无法有机会变成入度为 0 的点，因此就证明了环的存在。 力扣-顺丰科技智慧物流校园技术挑战赛 。 整体思路：通过每次删除入度为 0 的边，最后判断是否还有删除不到的边存在。删除不到就是因为不存在入度 0 的边了。若存在就是有环，否则无环。 细节： 综上： 每次通过入度为 0 的 heads 数组中取一个，遍历它的下一个节点 target，删除此路 edge，并更新 target 的入度（减一），若 target 入度为 0，加入到 heads 中，以备下次分析到 。

可以。有向图的路径是可以相交的，在地图中可以选择软件并打开向图的路径，可以在使用路径时期前找好最简便的路径，防止在路上使用时导致堵车的现象。

不可以。有向图在数学上是表示物件与物件之间的关系的方法，是图论的基本研究对象，连接的对象是除自己以外的物件，因此是不能自己连自己的，有向图是一副具有方向性的图，是有一组顶点和一组有方向的边组成的，每条方向的边都连接着一对有序的顶点。

有向图边分四种，分别为： 1.此节点未被访问过，则此次的访问关系边（发起点——>接受点）称为树边（tree edge）； 2.此节点被访问过但此节点的子孙还没访问完，换句话说，此次的发起点的源头可以追溯到接收点，则此次访问关系边称为后向边（back edge）； 3.此节点被访问过且此节点的子孙已经访问完，而且发起点是搜索初始边，则称为前向边（down edge）； 4.此节点被访问过且此节点的子孙已经访问完，而且发起点不是搜索初始边，则称为横叉边（cross edge）。 其实这种分类只是相对的，也会随着dfs的改变而改变，比如搜索入口、搜索顺序等。

package test; import java.util.*; public class GectorGraph {    private Point root;    private List<List<String>> circlePath;     public GectorGraph(String pointName) {        root=new Point(pointName);    }    public GectorGraph(Point point) {        root=point;    }         public boolean hasCirclePath(){        findCirclePath();        return circlePath.size()>0;    }         public void findCirclePath(){        List<Point> CirclePoints=findCirclePoint();        if(circlePath==null){circlePath=new ArrayList<List<String>>();}        for(Point tempPoint:CirclePoints){            List<String> pointPath=new ArrayList<String>();            findPointPath(tempPoint,root,pointPath);            pointPath.add(root.pointName);            circlePath.add(pointPath);        }    }         public boolean findPointPath(Point target,Point currentPoint,List<String> pointPath){        if(currentPoint.equals(target)){return true;}        if(!currentPoint.hasNext()){return false;}        List<Point> pointList= currentPoint.getNextPointList();        for(Point tempPoint:pointList){            if(tempPoint.equals(root)){continue;}            if(findPointPath(target,tempPoint,pointPath)){                pointPath.add(tempPoint.pointName);                return true;            }        }        return false;    }         private List<Point> findCirclePoint(){        if(!root.hasNext()){return null;}        List<Point> circlePoints=new ArrayList<Point>();        findCirclePoint(root,root,circlePoints);        return circlePoints;    }    private void findCirclePoint(Point root,Point currentPoint,List<Point> circlePoints){        if(!currentPoint.hasNext()){return;}        List<Point> pointList= currentPoint.getNextPointList();        for(Point tempPoint:pointList){            if(tempPoint.equals(root)){circlePoints.add(currentPoint);}            else{findCirclePoint(root,tempPoint,circlePoints);}        }    }    public void showPath(){        if(circlePath==null){System.out.println("Error");}        for(List<String> tempList:circlePath){            StringBuffer pathString=new StringBuffer();            int tempListIndex=tempList.size()-1;            for(;tempListIndex>-1;tempListIndex--){                pathString.append(tempList.get(tempListIndex));                if(tempListIndex!=0){pathString.append("->");}            }            System.out.println(pathString.toString());        }    }    public static void main(String[] args) {        Point root=new Point("root");                 List<Point> p3=new ArrayList<Point>();        for(int i=0;i<3;i++){            p3.add(new Point("3/1/"+i));        }        List<Point> p4=new ArrayList<Point>();        for(int i=0;i<3;i++){            p4.add(new Point("3/2/"+i));        }         List<Point> p2=new ArrayList<Point>();        for(int i=0;i<2;i++){            p2.add(new Point("2/"+i));        }                 p3.add(0,root);        p3.get(2).addNextPoint(root);        p4.get(0).addNextPoint(root);        p2.get(0).addNextPointList(p3);        p2.get(1).addNextPointList(p4);        root.addNextPointList(p2);                 GectorGraph gg=new GectorGraph(root);        if(gg.hasCirclePath()){            gg.showPath();        }    }}class Point{    public String pointName;    private List<Point> nextPointList;    public Point(String pointName) {        this.pointName=pointName;    }    public void addNextPoint(Point p){        if(nextPointList==null){nextPointList=new ArrayList<Point>();}        nextPointList.add(p);    }    public void addNextPointList(List<Point> pList){        if(nextPointList==null){nextPointList=new ArrayList<Point>();}        nextPointList.addAll(pList);    }    public boolean hasNext(){        return nextPointList!=null&&!nextPointList.isEmpty();    }    public List<Point> getNextPointList() {        return nextPointList;    }    public void setNextPointList(List<Point> nextPointList) {        this.nextPointList = nextPointList;    }}

有向图D=<V,E>,如图所示,求: (1)D中a到d长度为5的通路有多少条?(2)D中a到d长度小于等于3的通路有多少条?(3)D中d到自身长度小于等于3的回有多少条?注意:要求有计算过程。

这个算法的效率应该是理论上最好的了，因为要求出两点间所有的路径，必须考察每种可能（否则的话信息量不够），所以这个回溯法是唯一的方法。至于运算的速度，取决于你的图的规模和顶点的数目，这个算法的复杂度是O(VE)。内存耗光的问题一般不会出现，我试过用这个计算5000个节点的随机地图，速度还是蛮快的，一下子就出解了。该算法很简单，基本思想就是回溯。

有向完全图不仅仅要任意两个点之间都有边，而是要都有一对相反的边，这答案都没搞懂有向图的一些概念。有向完全图一定是强连通图，显然的，但是强连通图不一定是有向完全图，因为连通是指有路径，路径不一定是两点之间的边。

麻烦你把这道题拍照，然后去百度作业帮搜索一下，那里边有比较详细的解答过程，希望我的回答能够帮助的你

无向图可以看作每条边都有两个方向的有向图写成邻接矩阵的形式的话区别就很清楚:无向图的邻接矩阵一定是对称阵,而有向图则没有

无向图中顶点v的度，是关联于该顶点的边的数目。

n条你能给我保证？

(*G).arcs[i][j]=b;//记录下两点之间的权值下面再加上一句：(*G).arcs[j][i]=b;

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

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

底下那俩别瞎误人子弟了 完全有向图最多n（n-1）条边 除以2是无向图的

设D=<V,E>为n阶有向简单图（即不含平行边，也不含环的图），若对于任意的顶点u,v属于V，既有有向边<u,v>,又有<v,u>,则称D是n阶有向完全图。数目求法：利用乘法原理，n×(n-1)就是最多的有向图边。

1、无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边。2、有向图，一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。扩展资料定义针对有向图而言的，它是一个包含有向图的所有点的线性序列，且满足两个条件：a有向图的每个顶点只出现一次。b若存在一条从顶点A到顶点B的路径，那么在序列中顶点A应该出现在顶点B的前面。邻接矩阵和关联矩阵定义：设D（V,E）是有向图，其中V={v1,v2,v2?vn},E={e1,e2,e3,?em}称A(D)=(aij)nxn是D的领接矩阵，其中aij是以vi为起始点，以vj为终点的边的条数。若图D中无环，则称M(D)=（mij）nxm为关联矩阵。[i，j是下标，n是点的个数，m是边的数量注意：1.关联矩阵是针对边来说的，所以矩阵大小为n*m。参考资料来源：百度百科—无向图参考资料来源：百度百科—有向图

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

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

有向图就是路径有方向，带箭头的那种图

#include <stdio.h>#include<stdlib.h>typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 int *info; // 该弧相关信息的指针}ArcNode;typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧}VNode, AdjList[50];typedef struct { AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数}ALGraph;int locateALG(ALGraph g,int v){ for(int i=0;i<g.vexnum;i++){ if(g.vertices[i].data==v) return i; } return -1;}int CreateADG(ALGraph &g){ int i,j,k,l; ArcNode *p; int v1,v2; int c; printf("请输入有向图的顶点数:"); scanf("%d",&g.vexnum); while(g.vexnum>50){ printf(" 请输入有向图的顶点数："); scanf("%d",&g.vexnum); } i=g.vexnum*(g.vexnum-1); printf("请输入有向图的边数:"); scanf("%d",&g.arcnum); while(g.arcnum>i){ printf(" 请输入有向图的边数："); scanf("%d",&g.arcnum); } getchar(); printf("请依次输入有向图的各个顶点:"); for(i=0;i<g.vexnum;i++){//输入顶点信息 scanf("%d",&c); l=locateALG(g,c); if(l>=0){ printf("输入的顶点重复，请重新输入 "); i--; continue; } g.vertices[i].data=c; g.vertices[i].firstarc=NULL; } for(k=0;k<g.arcnum;k++){//输入边的信息 printf("请输入第%d条弧的起点与终点(用逗号分隔)：",k+1); scanf("%d,%d",&v1,&v2); i=locateALG(g,v1); j=locateALG(g,v2); if(i<0||j<0||i==j||(g.vexnum<0)){ k--; continue; } p=(ArcNode*)malloc(sizeof(ArcNode));//建立结点 if(!p) return -1; p->adjvex=j; p->nextarc=g.vertices[i].firstarc;//顶点i的链表 g.vertices[i].firstarc=p;//添加到最左边 } printf("有向图的邻接表创建成功 "); return 1;}void printGra(ALGraph G){ ArcNode *p; int i; printf("图中有%d个顶点，%d条弧： ",G.vexnum,G.arcnum); for(i=0;i<G.vexnum;i++){ p=G.vertices[i].firstarc; printf("%d ",G.vertices[i].data); while(p){ printf("<%d,%d>",G.vertices[i].data,G.vertices[p->adjvex].data); p=p->nextarc; } printf(" "); }}int main(void){ ALGraph g; CreateADG(g); printGra(g); return 0;}

有向图g可拓扑排序的判别条件是：每个顶点出现且只出现一次。判别，读音pàn bié，汉语词语，指根据不同点加以区分，辨别。根据不同点加以区分，辨别。示例：清·王夫之《姜斋诗话》卷二：“文章本静业，故曰‘仁者之言蔼如也"，学术风俗皆於此判别。”判，汉语常用字（一级字），会意兼形声字，最早见于战国文字。本义指分开、判分；由判分可引申为半、分辨、评断、判决义，用作半时“判”也可写作“牉”，以上义均读为pàn。“判”亦可表不顾、豁出去之义，这种意义上的“判”旧读为pān。判，会意兼形声字。从刀，从半，半亦表音。本义指分开、判分。《广雅·释诂一》：“判，分也。”《左传·庄公三年》：“纪于是乎始判。”杜预注：“判，分也。”由判分可引申为半、分辨、评断、判决义。用作半时，判也可写作“牉”。唐玄应《一切经音义》卷二：“判，古文胖，又作牉。”《周礼·地官·媒氏》：“掌万民之判。”郑玄注：“判，半也，得偶而合。”唐宋官制，以高官兼低职称判。元黄公绍《古今韵会举要·翰韵》：“宰相出典州曰判。”此用其假借义。以上义均读为pàn。

总度数(D)等于边数(e)的两倍。D=2e图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)。对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。扩展资料对于有向图，情形就不同了，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。设D是一个有向图，且u、v∈D，若存在从顶点u到顶点v的一条路径，则称从顶点v到顶点u可达。可达的慨念与从u到v的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。可达性是一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。

如图

如果结点vi与vj之间有边相连则邻接矩阵aij = 1否则aij = 0

呵呵，我回答了楼主说的是不是距离矩阵？

，邻接矩阵可以表示多重图，有多条边。离散数学卷子吧。如图，如有疑问或不明白请追问哦！

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

因为邻接矩阵的[i][j]代表的是i顶点到j顶点有无弧，因此i行上非零元素个数为vi的出度

如果对角线上元素为1，不就存在环了吗

程序我邮箱里都放着，都是原来上数据结构时写的～～

就此题来说，答案应该是一般。另外给出另一方面的分析，希望能对此题有所帮助。题目：若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为？（比原题加了个有序的）答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

这里的有向图，应该指强连通有向图。如果允许孤点，有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中的极大连通分量的个数。然后根据每个顶点继续寻找下一顶点，直到所有顶点都遍历完成。 这是算法的基本思想。

如图

有向图在图中的边是有方向的，表现出来就是有个箭头指示方向，节点只能单向通信或传递消息，相当于单行道，无向图边没方向是双向的，边连接的两个节点有通路可以双向通信，类似于双行道。无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有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个空间。

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