图由顶点（vertex）和边（edge）组成，通常表示为G =(V,E)
任意两个顶点之间都可以用边来表示它们之间的关系，边集合E可以是空的
1、有向图的边是有明确方向的
2、有向无环图(Directed Acyclic Graph)简称DAG
如果一个有向图，从任意顶点出发，无法经过若干条边回到该顶点，那么它就是一个有向无环图
出度（Out-degree）
一个顶点的出度为x，是指有x条边以该顶点为起点
入度（In-degree）
一个顶点的入度为x，是指有x条边以该顶点为终点
无向图（Undirected Graph）
无向图的边是无方向的
混合图（Mixed Graph）
混合图的边可能是无向的，也可能是有向的
平行边
在无向图中，关联一对顶点的无向边如果多于一条，则称这些边为平行边
在有向图中，关联一对顶点的有向边如果多于一条，并且它们的方向相同，则称这些边为平行边
多重图（Multigraph）
有平行边或者有自环的图
简单图（Simple Graph）
既没有平行边也没有自环的图
无向完全图（Undirected Complete Graph）
无向完全图的任意两个顶点之间都存在边
n个顶点的无向完全图有n(n - 1)/2条边
有向完全图 （Directed Complete Graph）
有向完全图的任意两个顶点之间都存在方向相反的两条边
n个顶点的有向完全图有n(n - 1)条边
稠密图（Dense Graph）:边数接近于或等于完全图
稀疏图 (Sparse Graph）:边数远远小于完全图
有权图（Weighted Graph）
有权图的边可以拥有权值
连通图（Connected Graph）
如果顶点x和y之间存在可相互抵达的路径（直接或间接的路径），则称x和y是连通的
连通分量（Connected Component）
连通分量：无向图的极大连通子图
连通图只有一个连通分量，即其自身
非连通的无向图有多个连通分量
强连通图 （Strongly Connected Graph）
如果有向图中任意两个顶点都是连通的，则称为强连通图
强连通分量（Strongly Connected Component）
强连通分量：无向图的极大连通子图
强连通图只有一个连通分量，即其自身
非连通的无向图有多个强连通分量
import Foundation
import UIKit
class Graph<V: Hashable,E: Hashable> {
private var vertices = Dictionary<V,Vertex<V,E>>() //存放顶点
private var edges = Set<Edge<V, E>>() //存放所有的边
var edgesSize : Int {
get {
return edges.count
}
} //有多少边
var verticesSize : Int {
get {
return vertices.count
}
} //有多少顶点
//顶点
class Vertex<V: Hashable,E: Hashable> : Hashable{
var value : V? //顶点上的值
var inEdges = Set<Edge<V, E>>() //以这个点为终点的边 进来这个点的边
var outEdges = Set<Edge<V, E>>()//以这个点为起点的边 从这个点出去的边
func hash(into hasher: inout Hasher) {
hasher.combine(value)
// hasher.combine(inEdges)
// hasher.combine(outEdges)
}
static func == (lhs: Graph.Vertex<V, E>, rhs: Graph.Vertex<V, E>) -> Bool {
return lhs === rhs
}
init(_ v: V){
value = v
}
}
//边
class Edge<V: Hashable,E: Hashable> : Hashable{
var form : Vertex<V,E>//起点
var to : Vertex<V,E>//终点
var weight :E?//权值
func hash(into hasher: inout Hasher) {
hasher.combine(form)
hasher.combine(to)
// hasher.combine(weight)
}
init(_ form:Vertex<V,E>,_ to:Vertex<V,E>){
self.form = form
self.to = to
}
//起点和终点一样 认为是同一条边
static func == (lhs: Graph.Edge<V, E>, rhs: Graph.Edge<V, E>) -> Bool {
return (lhs.form == rhs.form) && (lhs.to == rhs.to)
}
}
func printGraph(){
for key in vertices.keys{
let value:Vertex = vertices[key]!
print(key,value.value! as Any)
for edge in value.inEdges {
print(key,"进来的边",edge.form.value!,edge.to.value!)
}
for edge in value.outEdges {
print(key,"出去的边",edge.form.value!,edge.to.value!)
}
}
for value in edges{
print(value.weight as Any,value.form.value! as Any,value.to.value! as Any)
}
}
//添加顶点
func addVertex(_ v:V){
if let _ = vertices[v] {
return
}
vertices[v] = Vertex<V,E>(v)
}
//删除顶点
func removeVertex(_ v:V){
guard let tempV = vertices.removeValue(forKey: v) else {
return
}
for e in tempV.outEdges {
e.to.inEdges.remove(e)
edges.remove(e)
}
for e in tempV.inEdges {
e.form.outEdges.remove(e)
edges.remove(e)
}
}
//添加边
func addEdge(_ form:V, _ to:V){
addEdge(form, to, nil)
}
//添加边(带权值)
func addEdge(_ form:V, _ to:V ,_ weight :E?){
//判断顶点是否存在
var tempForm : Vertex<V,E>? = nil
if let temp = vertices[form] {
tempForm = temp
}else {
tempForm = Vertex<V,E>(form)
}
var tempTo : Vertex<V,E>? = nil
if let temp = vertices[to] {
tempTo = temp
}else {
tempTo = Vertex<V,E>(to)
}
guard let tempForm = tempForm, let tempTo = tempTo else{
return
}
//创建一个边
let fe = Edge<V,E>(tempForm,tempTo)
fe.weight = weight
if tempForm.outEdges.remove(fe) != nil {
tempTo.inEdges.remove(fe)
edges.remove(fe)
}
//权值不一样的话 会更新
tempForm.outEdges.insert(fe)
tempTo.inEdges.insert(fe)
edges.insert(fe)
vertices[form] = tempForm
vertices[to] = tempTo
}
//删除边
func removeEdge(_ form:V, _ to:V){
//判断顶点是否存在
guard let tempForm = vertices[form], let tempTo = vertices[to] else{
return
}
let fe = Edge(tempForm,tempTo)
if tempForm.outEdges.remove(fe) != nil {
tempTo.inEdges.remove(fe)
edges.remove(fe)
}
}
}
网友评论