有向图
文章目录
有向图
1、术语
2、有向图的数据结构
有向图的API
有向图的数据结构
3、有向图的可达性
DirectedDFS 算法实现
有向图路径问题

1、术语
在有向图中，边是单向的。每条边所连接的两个顶点都是一个有序对，他们的邻接性是单向的。
出度：该顶点指出的边的总数

入度：指向该顶点的边的总数
一条有向边的第一个顶点称为它的头，第二个顶点称为它的尾。将有向边画为由头指向尾的一个箭头。

用 v -> w 表示有向图中一条由v指向w的边。
有向路径

有向环

简单有向环：除了起点和终点必须相同之外，不含有重复的顶点和边的环
路径或环的长度即为其中所包含的边数。
有向图的可达性：当存在从v到w的路径时，称顶点w能够由顶点v达到。

无向图的连通性


2、有向图的数据结构
有向图的API

reverse() 方法，返回该有向图的一个副本，但将其中所有边的方向反转。这样用例就可以找出指向每个顶点的所有边。
有向图的表示：邻接表。边 v -> w 表示为顶点v所对应的邻接链表中包含一个w顶点。

在用邻接表表示无向图时，如果v 在w 的链表中，那么w必然也在v的链表中。但在有向图中这种对称性是不存在的，因为每条边都只会出现一次。


有向图的数据结构
Digraph数据类型与Graph数据类型基本相同。区别是 addEdge() 只调用了一次 add()，而且它还有一个 reverse() 方法来返回图的反向图。
/*DiGraph数据类型*/
public class DiGraph{
    private final int V;    //顶点数目
    private int E;          //边的数目
    private Bag<Integer>[] adj; //邻接表

    public DiGraph(int V){
        this.V = V; this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];    //创建邻接表
        for(int v = 0; v < V; v++)          //将所有链表初始化为空
            adj[v] = new Bag<Integer>();
    }

	public Graph(In in){
        this(in.readInt());      //读取V并将图初始化
        int E = in.readInt();    //读取E
        for(int i = 0;i < E; i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v, w);       //添加一条由v指向w的边   
        }
    }
	
    public int V(){ return V; }
    public int E(){ return E; }

    public void addEdge(int v, int w){
        adj[v].add(w);    //！！！！与无向图的区别，只调用了一次add()
        E++;
    }
    public Iteralbe<Integer> adj(int v){
        return adj[v];
    }
    
	public Digraph reverse(){   //！！！！与无向图的区别，有一个 reverse() 方法来返回图的反向图
		Digraph R = new Digraph(V);
		for(int v = 0; v < V; v++)
			for(int w : adj(v))
				R.addEdge(w, v);
		return R;
	}
}




3、有向图的可达性
深度优先搜索 DFS 解决了单点连通性的问题，使得用例可以判定其他顶点和给定的起点是否连通。
同样在有向图中，

单点可达性给定一幅有向图和一个起点s，回答“是否存在一条从s到达给定顶点v的有向路径？”等类似问题。

多点可达性给定一幅有向图和顶点的集合，回答“是否存在一条从集合中的任意顶点到达给定顶点v的有向路径？”等类似问题。

DirectedDFS 算法实现
/*
 * 有向图的可达性。用例能够判断从给定的一个或者一组顶点能到达哪些其他顶点。
 */
public class DirectedDFS{
    private boolen[] marked;    //使用一个boolean数组来记录和起点s连通的所有顶点
   
    public DirectedDFS(Digraph G, int s){
        marked = new boolen[G.V()];
        dfs(G, s);    
    }
    public DirectedDFS(Digraph G, Iterable<Integer> sources){
        marked = new boolen[G.V()];
        for(int s: sources)
        	if(!marked[s])	
        		dfs(G, s);    
    }
    
    private void dfs(Graph G, int v){
        marked[v] = true;
        for (int w : G.adj(v)){
            if (!marked[w])
                dfs(G, w);
        }
    }

    public boolen marked(int v){ return marked[v]; }
}




下图显示了这个算法在处理有向图的操作轨迹。这份轨迹比相应的无向图算法的轨迹稍稍简单些，因为深度优先搜索本质上是一种适用于处理有向图的算法，每条边都只会被表示一次。


有向图路径问题
单点路径 DepthFirstPaths

单点最短路径 BreadFirstPaths

有向图、无向图
有向图和无向图是我们常用到的术语，本文属于简单的科普帖。
全部由无向边构成图称为无向图（Undirected Graph）,全部由有向边构成图称为有向图（Directed Graph）。有向，顾名思义，有方向。本文中顶点Vertex（V），边Edge（E）
（1）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的条数则称为入读。其中，入度+出度，我们称为A的度。注意特殊情况：如图：A有一个自环，起点和终点都是自己，此时出度算一度，入度也算一度。如图：A的出度为3，入度也为2，A的度的5。


（2）描述图的邻接矩阵和关联矩阵

【邻接矩阵】
定义：

设无向图G=(V,E),其中顶点集V=v1,v2,…,vn，边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数，可能取值为0,1,2,…，称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。
示例，求图所示简单图的邻接矩阵？



解：根据定义，可求得该无向图的邻接矩阵为


邻接矩阵的存储特点：

（a）无向图的邻接矩阵一定是一个对称矩阵，有向图不一定是。

*（b）邻接矩阵所需的存储空间值域只与顶点数有关系。

（c）用邻接矩阵存储图，容易判断两个点之间是否有边。

（d）如果一个有向图的邻接矩阵为三角矩阵（主对角线为0），则它的拓扑排序一定存在。

*（e）小技巧：

无向图：邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度；

有向图：邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度，第i列非零元素的个数正好是第i个顶点Vi的入度。
【关联矩阵】
定义：

设任意图G=(V,E)，其中顶点集V=v1,v2,…,vn，边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系，可能取值为0,1，-1，称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。



mij 表示i行j列，探究顶点Vi和边Ej之间的关系，形成下列的关联矩阵

示例：



关联矩阵


连通图、连通分量
连通图：无向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为连通图。

连通分量：无向图中极大连通子图称为连通分量。
强连通图、强连通分量
强连通图：有向图中，若从顶点u到顶点v有路径，称为u，v是连通的。若图中任意两个顶点均是连通的，则称为强连通图。

连通分量：无向图中极大连通子图称为强连通分量。特：强连通图只有强连通分量（本身），非强连通图有多个强连通分量。
另外，本文参考路了下面两位作者的优秀博客

https://blog.csdn.net/Hanging_Gardens/article/details/55670356

https://blog.csdn.net/legendaryhaha/article/details/83049101

目录：

一：无向图

1.定义

2.图形化解释

3.结合​表达式介绍

二：有向图

1.定义

2.图形化解释

3.结合​表达式介绍

有向图和无向图区别： 

三：简单图

1.定义

2.图形化解释

四：完全无向图

1.定义

2.图形化解释

五： 有向完全图

1.定义

2.图形化解释

一：无向图

1.定义


若顶点 到之间的边没有方向，则称这条边为 无向边（Edge）

用无序偶对 来表示

如果图中任意两个顶点之间的边都是无向边，则称该图为 无向图

 

无向图顶点的边数叫做 度


2.图形化解释


下图所示即为无向图：




3.结合表达式介绍


由于无向图是无方向的，连接顶点的边

可以表示成无序对

也可以写成



对于上图中的无向图 来说



其中顶点集合

边集合


 

二：有向图

1.定义


若从顶点  到  的边有方向，则称这条边为 有向边，也称为 弧（Arc）

用有序偶 来表示，称为弧尾（Tail），称为弧头（Head）

如果图中任意两个顶点之间的边都是有向边，则称该图为 有向图（Directed graphs）

 

有向图顶点分为 入度（箭头朝自己） 和 出度（箭头朝外）


2.图形化解释


如下图所示即为一个有向图：




3.结合表达式介绍


连接到顶点到的有向边就是弧

是弧尾

 是弧头

表示弧，注意不能写成

 

对于上图的有向图



其中顶点集合 

弧集合 


有向图和无向图区别： 


注：看清楚了，无向边用小括号表示

而有向边则是使用尖括号表示


 

三：简单图

1.定义


在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图


2.图形化解释


如下所示的两个图就不属于简单图：




 

四：完全无向图

1.定义


在无向图中，如果任意两个顶点之间都存在边，则称该图为 无向完全图


2.图形化解释


如下图所示即为一个无向完全图：




 

五： 有向完全图

1.定义


在有向图中，如果任意两个顶点之间都存在 方向互为相反 的两条弧，则称该图为 有向完全图


2.图形化解释


如下图所示即为一个有向完全图：




 

无向图的邻接表





有向图的邻接表



无向图的邻接矩阵


有向图的邻接矩阵