图形结构的存储

例题：

将下方图形结构存储到计算机中，请设计一个数据结构并将其合理的存储起来。

图1.png

方法一： $\color{red}{邻接矩阵}$

网-邻接矩阵.png

无向图--邻接矩阵.png

有向图--邻接矩阵.png

邻接矩阵存储数据结构设计

Demo使用swift的命令行工程

let MAXVEX = 5 //最大定点数

class MGraph: NSObject {
    var numNodes = Int() //图中当前的顶点数
    var numEdges = Int() //图中当前的边数
    var vexList = [String](repeating: "∞", count: MAXVEX) //顶点表
    var arcList = Array<Array<Any>>.init() //存储数据的列表
}

创建图的函数：

func createMGraph(_ G: MGraph) -> Void {
    
    //1、输入顶点数和边数
    print("输入顶点数和边数:")
    let nodes = readLine() ?? "0"
    let edges = readLine() ?? "0"
    G.numNodes = Int(nodes) ?? 0
    G.numEdges = Int(edges) ?? 0
    print("顶点数:\(G.numNodes) " + "边数:\(G.numEdges)")
    
    //2、输入顶点信息和顶点表
    print("输入顶点表")
    for i in 0..<G.numNodes {
        let input = readLine() ?? "∞"
        G.vexList[i] = input
    }

    //3、初始化邻接矩阵
    for i in 0..<G.numNodes {
        var array = Array<String>.init()
        for j in 0..<G.numNodes {
            let temp = i==j ? "0" : "∞"
            array.append(temp)
        }
        G.arcList.append(array)
    }
    
    //4、输入边表信息
    for _ in 0..<G.numEdges {
        print("输入边（Vi，Vj）上的下标i，下标j，权W")
        let i = Int(readLine() ?? "0")!
        let j = Int(readLine() ?? "0")!
        let w = readLine() ?? "∞"
        
        G.arcList[i][j] = w
        //如果是无向图，则矩阵对称
//        G.arcList[j][i] = G.arcList[i][j]
    }
    
    //5、打印邻接矩阵
    for i in 0..<G.numNodes {
        print("")
        for j in 0..<G.numNodes {
            print("\(G.arcList[i][j])", separator: "", terminator: " ")
        }
        print("")
    }
}

createMGraph(MGraph.init()) ///创建图性存储

方法二： $\color{red}{邻接表}$

无向图--邻接表.png

有向图--邻接表.png

网--邻接表.png

邻接矩阵存储数据结构设计

let MAXVEX = 5 //最大定点数

//邻接表的节点
class Node: NSObject {
    var adj_Vex_index:Int = 0 //被指向的下标
    var data:Int = 0 //权重值
    var next:Node? //边指针
}
typealias EdgeNode = Node

//顶点节点表
struct vNode {
    var data:String //顶点的权值
    var firstedge:EdgeNode? = nil //顶点的下一个
}
typealias VertexNode = vNode

var Adjlist = [vNode]()

//总图的一些信息
class Graph: NSObject {
    var adjlist = Adjlist  //顶点表
    var arc_num:Int = 0 //边的个数
    var node_num:Int = 0 //节点的个数
    var is_directed:Bool = false //是不是有向图
}

创建表：

func creatGraph(_ g: Graph) {
    
    //1、顶点，边，是否有向
    print("输入顶点数目，边数和是否有向：")
    let nodeNum = Int(readLine() ?? "0")!
    let arcNum = Int(readLine() ?? "0")!
    let isDirected = Bool(readLine() ?? "false")!
    
    g.node_num = nodeNum
    g.arc_num = arcNum
    g.is_directed = isDirected
    
    //2、顶点表
    print("输入顶点信息")
    for _ in 0..<g.node_num {
        let data = readLine() ?? "V"
        let node = VertexNode.init(data: data)
        g.adjlist.append(node)
    }
    
    //3、输入边信息
    print("输入边信息")
    for _ in 0..<g.arc_num {
        let i = Int(readLine() ?? "0")!
        let j = Int(readLine() ?? "0")! //弧头的下标
        
        //①新建一个节点
        let p = EdgeNode()
        //②弧头的下标
        p.adj_Vex_index = j
        //③头插法插入，插的时候要找到弧尾，那就是顶点数组的下标i
        p.next = g.adjlist[i].firstedge
        //④将顶点数组[i].firstedge 设置为p
        g.adjlist[i].firstedge = p
        
        //无指向的 j->i
        if g.is_directed == false { //无向图
            // j -----> i
            //①新建一个节点
            let d = EdgeNode()
            //②弧头的下标
            d.adj_Vex_index = i
            //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
            d.next = g.adjlist[i].firstedge
            //④将顶点数组[i].firstedge 设置为d
            g.adjlist[j].firstedge = d
        }
    }
}

输出表：

func putGraph(_ g: Graph) {
    print("邻接表中存储的信息：")
    for i in 0..<g.node_num {
        var p = g.adjlist[i].firstedge
        while p != nil {
            print("\(g.adjlist[i].data)->\(g.adjlist[p!.adj_Vex_index].data)", separator: "", terminator: "  ")
            p = p?.next ?? nil
        }
        print("")
    }
}

函数调用：

var g = Graph.init()

creatGraph(g)
putGraph(g)
/*
     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     4 5 false
     输入顶点信息：
     0 1 2 3
     输入边信息：
     0 1 0 2 0 3 2 1 2 3
     邻接表中存储信息:
     0->3 0->2 0->1
     1->2 1->0
     2->3 2->1 2->0
     3->2 3->0
    */
    /*
     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     4 5 true
     输入顶点信息：
     0 1 2 3
     输入边信息：
     1 0 1 2 2 1 2 0 0 3
     邻接表中存储信息:
     0->3
     1->2 1->0
     2->0 2->1
     */