图的邻接表

图

上图中有4个顶点5条边：

起始顶点	目标顶点	权值	边编号
A	B	9	1
D	C	8	2
A	B	5	3
B	D	6	4
A	C	7	5

---

邻接表

这里用数组来实现邻接表：

邻接表

• U V W : U[i]->V[i] 权值为 W[i], 边编号为 i;
• first: first[i] 表示 i（A, B, C, D）号顶点的第一条边；
• next : next[i] 表示 i（1，2，3，4，5）号边的下一条边；

构建邻接表

看图不说话

1.png 2.png 3.png 4.png 5.png

---

// 顶点编号：0，1，2，3 表示顶点 A，B，C，D
// 边编号：0，1，2，3，4
var u = [5]int{0, 3, 0, 1, 0}
var v = [5]int{3, 2, 1, 3, 2}
var w = [5]int{9, 8, 5, 6, 7}

func AdjacencyList() ([4]int, [5]int) {

        for i := 0; i < 5; i++ {
                fmt.Println(u[i], " -> ", v[i], " ", w[i])
        }

        first := [4]int{-1, -1, -1, -1}
        next := [5]int{-1, -1, -1, -1, -1}

        fmt.Println("fisrt : ", first)
        fmt.Println("next: ", next)
        fmt.Println("-----------------------")

        // 遍历5条边
        for i := 0; i < 5; i++ {
                next[i] = first[u[i]] // 将第i条边的下一条边设置为 u[i]号顶点的当前第一条边
                first[u[i]] = i       // 将u[i]号顶点的第一条边设置为当前边
        }

        fmt.Println("first: ", first)
        fmt.Println("next: ", next)

        return first, next
}

结果

---

用邻接表存储图的空间复杂度是O(M) （M边数），查找的时间复杂度也 为O(M)

遍历顶点的出边：

func TraverseEdge(point int, first [4]int, next [5]int) {
        k := first[point]
        for -1 != k {
                fmt.Println(u[k], " -> ", v[k], " ", w[k])
                k = next[k]
        }
}