图（Graph）是由顶点的有穷非空集合和顶点 (Vertex) 之间边 (Edge) 的集合组成，通常称为: G(V,E),G 代表一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。图中的元素称为顶点，顶点之间的逻辑关系用边来表示。

1、图的基本概念

---

无向边：若顶点 Vi 到 Vj 之间的边没有方向，则称这条边为无向边(Edge),用无序偶对 (Vi,Vj)来表示。

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

有向边： 若从顶点 Vi 和 Vj的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶 <Vi,Vj> 来表示，Vi 称为弧尾 (Tail), Vj 称为弧头(Head)。

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

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

无向完全图： 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有 n个顶点的无向完全图有n*(n-1)/2 条边。n 个顶点可以连 n-1 条线，但是顶点互相连接会重复，所以要除以 2。

有向完全图： 在有向图图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有 n 个顶点的有向完全图有 n*(n-1) 条边。

稀疏图和稠密图： 有很少条边或弧的称为稀疏图，反之称为稠密图。

网： 与图的边或弧相关的数叫做权重 (Weight)。这种带权的图通常称为网 Network。

子图： 假设有两个图 G=(V,{E})和 G1=(V1,{E1}),如果 V1包含于V 且 E1包含于E,则称G1是 G的子图。

2、图的顶点和边之间的关系

  对于无向图 G=(V,{E})，如果边 (v,v')∈E ,则称 顶点 v 和 v' 互为邻接点 (Adjacent), 即 v和 v' 相邻接。顶点 v 的度 (Degree) 是和 v相关联的边的数目。记为 TD(v)。

  对于有向图 G=(V,{E}) 如果 <v,v'>∈E ，则称顶点 v邻接到顶点 v',顶点 v' 邻接自顶点 v。 以顶点 v 为头的弧的数目称为 v 的入度 (InDegree) ,记为 ID(v);以 v 为尾的弧的数目称为 v 的出度 (OutDegree),记为 OD(v); 顶点 v的度为 TD(v)=ID(v)+OD(v)。

  无向图 G=(V,{E}) 中从顶点 v到 v'的路径 (path) 是一个顶点序列。

路径的长度是路径上的边或弧的数目。

  第一个顶点到最后一个顶点相同的路径称为回路或环 (Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

3、连通图相关术语

  在无向图 G 中，如果从顶点 V 到顶点 V' 有路径，则称 v和 v'是连通的。如果对于图中任意两个顶点 vi、vj∈V , v和 v'都是连通的，则称 G 是连通图。 无向图中的极大连通子图称为连通分量。 强调

• 要是子图
• 子图要是连通的。
• 连通子图含有极大顶点数。
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

在有向图 G 中，如果对于每一对 vi、vj∈V, vi≠vj, 从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大连通子图称为有向图的强连通分量。

连通图的生成树： 是一个极小的连通子图，它含有图中全部 n 个顶点，但是只有足以构成一棵树的 n-1 条边。

如果一个由向图恰有一个顶点的入度为 0 ,其余顶点的入度均为 1 ,则是一棵有向树。入度为0 表示根结点，其余顶点入度为 1 表示数的非根结点的双亲只有一个。

4、邻接矩阵

  图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边和弧的信息。

邻接表： 数组和链表相结合的存储方法。 边集数组： 是由两个以为数组构成。一个存储顶点的信息；另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(wieght)组成。

5、图的遍历

首先我们来构建一个图

function Graph(v) {    
    this.vertices = v;    
    this.edges = 0;    
    this.adj = [];    
    for (let i = 0; i < this.vertices; ++i) {       
        this.adj[i] = [];        
    }    
    this.addEdge = addEdge;    
    this.showGraph = showGraph; 
    this.dfs = dfs;   
    this.bfs=bfs;
    this.edgeTo=[];//用于保存一个顶点到下一个顶点的所有边 
    this.marked = []; //存放访问过的结点   
    for (let i = 0; i < this.vertices; ++i) {       
        this.marked[i] = false; 
    }
} 
//给图添加邻接点 
function addEdge(v, w) {    
    this.adj[v].push(w);    
    this.adj[w].push(v);    
    this.edges++; 
}
//展示图
function showGraph() {    
    for (let i = 0; i < this.vertices; ++i) {  
        let putstr=(i + " -> ");       
        for (let j = 0; j < this.vertices; ++j ) {          
            if (this.adj[i][j] != undefined) {             
                putstr+=(this.adj[i][j] + '  ');          
            }       
        }       
        console.log(putstr)    
    }    
}
const g=new Graph(5)
g.addEdge(0,1);  
g.addEdge(0,2);  
g.addEdge(1,3);  
g.addEdge(2,4);  
g.showGraph();

1、深度优先遍历（DFS）

  从图中某个顶点 V 出发，访问此顶点，然后从 V 的未被访问的邻接点出发，深度优先遍历图，直到图中所有和 V 有路径相通的顶点都被访问到。就像一棵树的前序遍历（根左右）。

function dfs(v) {    
    this.marked[v] = true;    
    if (this.adj[v] != undefined) {       
        console.log("Visited vertex:  " + v);    
    }    
    for(const w of this.adj[v]) {       
        if (!this.marked[w]) {          
            this.dfs(w);       
        }    
    } 
}

2、广度优先遍历（BFS）

  类似于树的层序遍历。从第一个顶点开始，尝试访问尽可能靠近它的顶点。本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始点最远的层。使用了抽象的队列而不是数组来对已访问过的顶点进行排序。 算法的基本工作原理如下：

• 查找与当前顶点相邻的未访问顶点，将其添加到已访问顶点列表及队列中。
• 从图中取出下一个顶点 v ,将其添加到已访问的顶点列表。
• 将所有与 v

function bfs(s) {   
    //存放与当前结点相邻且未被访问过的结点 ，按先后顺序排列
    const queue = []; 
    //表示已经访问过了    
    this.marked[s] = true;   
    //存放已经访问过的结点 
    queue.push(s); // 添加到队尾    
    while (queue.length > 0) { 
        //从图中取出下一个顶点v       
        var v = queue.shift(); // 从队首移除       
        if (v!==undefined) {          
            console.log("Visisted vertex:  " + v);       
        }       
        for(const w of this.adj[v]) { 
            //查找与当前顶点相邻的为访问顶点，将其添加到已访问顶点列表及队列中         
            if (!this.marked[w]) {           
                this.marked[w] = true;  
                this.edgeTo[w]=v;   
                //将所有与 v 相邻的未访问顶点添加到队列        
                queue.push(w);          
            }       
        }    
    } 
}

6、查找最短路径

在广度优先搜索的基础上执行最短路径。

function Graph(v) {    
    this.vertices = v;    
    this.edges = 0;    
    this.adj = [];    
    for (let i = 0; i < this.vertices; ++i) {       
        this.adj[i] = [];        
    }    
    this.addEdge = addEdge;    
    this.edgeTo=[];//用于保存一个顶点到下一个顶点的所有边 
    this.marked = []; //存放访问过的结点   
    for (let i = 0; i < this.vertices; ++i) {       
        this.marked[i] = false; 
    }
} 
//给图添加邻接点 
function addEdge(v, w) {    
    this.adj[v].push(w);    
    this.adj[w].push(v);    
    this.edges++; 
}
function pathTo(s,v) {      
    if (!this.hasPathTo(v)) {       
        return undefined;    
    }    
    const path = [];    
    for (let i = v; i != s; i = this.edgeTo[i]) {       
        path.push(i);    
    }    
    path.push(s);    
    return path; 
} 
 
function hashPathTo(v) {     
    return this.marked[v]; 
}
const g=new Graph(8)
g.addEdge(0,1);  
g.addEdge(0,2);  
g.addEdge(1,3);  
g.addEdge(3,4); 
g.addEdge(1,5);  
g.addEdge(2,4);
g.addEdge(2,6); 
g.addEdge(4,7)
g.bfs(0);//输出顺序为 0,1,3,4,2,6,7,5
g.dfs(0);//输出顺序为0,1,2,3,5,4,6,7（层序遍历）
var paths = g.pathTo(0,4); 
let path=''
while (paths.length > 0) {    
    if (paths.length > 1) {       
       path+=paths.pop() + '-';    
    }     
    else {       
        path+=paths.pop();    
    } 
}
console.log(path)

7、拓扑排序

拓扑排序算法与深度优先搜索类似