有向图

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条边.

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、有向图用邻接矩阵更加节省存储空间.因为无向图的邻接矩阵是对称的,所以也就是多用了一些存储空间.

如果有对称元素 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

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

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

有向图是单向的，有箭头，例如路径可以从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．有向图若图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)}所以，几个顶点之间有无边或者是弧取决于两个顶点之间的方向性。

这是矩阵实现的有向图非带权，实现了判断是否有回路的功能，至于判断弧头弧尾，用矩阵很容易实现，代码如下#pragma onceenum GraphStyle //style of graph{ DG, DN, UDG, UDN};const int MAX_VERTEX_NUM=20; //maxmium of vertextemplate<class T>class ALGraphMatrix{public: ALGraphMatrix() { cirlceCount=0; numVertices=0; numEdges=0; style=DG; } ~ALGraphMatrix(){}; void AddVertex(const T&); //void RemoveVertex(const T&); void AddEdge(const T&,const T&); //void RemoveEdge(const int,const int); int GetNumVertexs() { return numVertices; } int GetNumEdges() { return numEdges; } int LocateVertex(const T&); bool JudgeCircle(const int n); void Print();private: int numVertices; int numEdges; GraphStyle style; T vertices[MAX_VERTEX_NUM]; //邻接矩阵，对无权图，用1或0表示相邻否，带权图，则为权值类型 int adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int visited[MAX_VERTEX_NUM]; int circleNum[MAX_VERTEX_NUM]; int cirlceCount;};template<class T>void ALGraphMatrix<T>::AddVertex(const T&vex){ if (numVertices<MAX_VERTEX_NUM) { vertices[numVertices++]=vex; } else cout<<"the AlGraphMAtrix is full"<<endl;}template<class T>void ALGraphMatrix<T>::AddEdge(const T& s,const T& e){ int startNum=-1,endNum=-1; for (int i=0;i<numVertices;i++) { if (vertices[i]==s) { startNum=i; } if (vertices[i]==e) { endNum=i; } } if (startNum==-1||endNum==-1) { cout<<"No such element"<<endl; } else{ adjMatrix[startNum][endNum]=1; numEdges++; }}template<class T>bool ALGraphMatrix<T>::JudgeCircle(const int n){ circleNum[0]=0; bool flag=false; visited[n]=1; for (int i=0;i<numVertices;i++) { if (adjMatrix[n][i]==1) { visited[i]++; circleNum[++cirlceCount]=i; if (visited[i]==2) { cout<<"A circle exits in the ALGraph,it"s"<<endl; for (int k=0;k<cirlceCount;k++) { if (circleNum[k]==i) { for (int j=k;j<cirlceCount;j++) { cout<<vertices[circleNum[j]]<<" -> "; } cout<<vertices[circleNum[cirlceCount]]<<endl<<endl; return true; } } } else { flag=JudgeCircle(i); if (flag) { return true; } } } } return false;}template<class T>void ALGraphMatrix<T>::Print(){ cout<<"Number of vertex is "<<numVertices<<",they are"<<endl; for (int i=0;i<numVertices;i++) { cout<<vertices[i]<<" "; } cout<<endl; cout<<"Number of edges is "<<numEdges<<",they are "<<endl; for (int j=0;j<numVertices;j++) { cout<<vertices[j]<<" --> "; for (int k=0;k<numVertices;k++) { if (adjMatrix[j][k]==1) { cout<<vertices[k]<<" "; } } cout<<endl; }}测试程序#include "ALGraphMatrix.h"#include <iostream>using namespace std;int main(){ cout<<"This program tests whether a"<< " circle exits in a UD(stored with matrix)"<<endl<<endl; ALGraphMatrix<char> alg; cout<<"input the charactors you want to insert into the ALgrph"<<endl; char cha; //cin.get(); //Clear the stream while ((cha=cin.get())!=" ") { if (cha==" ") { continue; } alg.AddVertex(cha); } cout<<endl; cout<<"input some edges insert into the ALgraph"<<endl <<"For example(a b),end with (# #)"<<endl; char e1,e2; cin>>e1>>e2; while (true) { if (e1=="#"&&e2=="#") { break; } else { alg.AddEdge(e1,e2); cin>>e1>>e2; } } cout<<endl; cout<<"Now this is the info of the ALgraph"<<endl; alg.Print(); cout<<endl; if (!alg.JudgeCircle(0)) cout<<"No circle exits in the Algraph"<<endl; cout<<"Good job"<<endl; system("pause"); return 0;}

无向有向都能做。不带权更简单，所有边的权值都设为1即可。

带权有向图中每个顶点的度怎么理解方法；因为与顶点连通的顶点可能是相邻的顶点，也可能是相邻的相邻的顶点。连通指的是两个顶点之间有路径，若一个图是连通的，则和任意一个顶点连通的顶点数位N-1，N为图的顶点总数。顶点的度指的是与该顶点相关联的边的总数。两个顶点相邻指的是该两个顶点之间有边连接，这条边依附于这两个顶点存在。所以D是错的，B是对的