上面是我的实验作业要求：（看不到的同学，移步：https://gitee.com/young-lion/picture-bed/raw/master/202412051939715.png）

下面的代码使用的是go语言：

package mainimport ("fmt"
)// 访问标记数组
var visited []bool
// ----------------------------邻接矩阵表示的图-----------------------------------// 自定义顶点类型Vex，这里简单地包含一个整数值来表示顶点编号，可按需扩展其成员
type Vex struct {id   int    //顶点编号data int    //顶点数据
}// 图的定义，使用邻接矩阵存储结构
type Graph struct {vex   []Vex    // 顶点数组，使用自定义的Vex类型edge  [][]int  // 邻接矩阵，这里边的连接情况用0或1表示是否有边相连，可按需调整n     int      // 顶点个数m     int      // 边数（一条边的长度）
}// 创建节点
func CreateVex(id int, data int) Vex {return Vex{id: id, data: data}
}// 创建邻接矩阵表示的图
func CreateGraph() (n,m int,vex []Vex, edge [][]int) {// 顶点数组fmt.Println("请输入顶点个数：")fmt.Scan(&n)vex = make([]Vex, n)for i := 0; i < n; i++ {fmt.Println("请输入顶点data:")var data intfmt.Scan(&data)vex[i] = CreateVex(i, data)}// 创建空的邻接矩阵edge = make([][]int, n)for i := 0; i < n; i++ {edge[i] = make([]int, n)}// 邻接矩阵// 输入边的数量fmt.Println("请输入边的数量:")fmt.Scan(&m)fmt.Println("请输入边的关系:")for i := 0; i < m; i++ {var start, end intfmt.Scan(&start, &end)// 输入的是值datastartvex := SearchVex(vex, start)endvex := SearchVex(vex, end)startid := startvex.idendid := endvex.id// TODO:调试：//fmt.Println(startid,"--->", endid)edge[startid][endid] = 1//fmt.Println(edge[startid][endid])//edge[endid][startid] = 1 // 无向图，双向边赋值}return
}// 深度优先搜索遍历（基于邻接矩阵的图）
func DFSTraverse(graph *Graph) {visited = make([]bool, graph.n)for i := 0; i < graph.n; i++ {if!visited[i] {DFS(graph, i)}}
}// 深度优先搜索（基于邻接矩阵的图）
func DFS(graph *Graph, index int) {fmt.Printf("%d ", graph.vex[index].data)visited[index] = truefor i := 0; i < graph.n; i++ {if graph.edge[index][i] == 1 &&!visited[i] {DFS(graph, i)}}
}// 广度优先搜索遍历（基于邻接矩阵的图）
func BFSTraverse(graph *Graph) {// 访问标记数组 初始化为false[默认]：都未访问visited := make([]bool, graph.n)// 暂存队列（用切片模拟）queue := make([]int, 0)// 遍历每一个顶点for i := 0; i < graph.n; i++ {// 如果没有访问if!visited[i] {// 先清空队列，避免之前连通分量遗留的顶点干扰当前遍历queue = queue[:0]// 将当前访问的节点位置加入队列queue = append(queue, i)visited[i] = true// 访问fmt.Printf("%d ", graph.vex[i].data)// 找当前层所有点的其他邻接点（遍历队列）for len(queue) > 0 {// 取出队列的第一个点vex := queue[0]queue = queue[1:]for j := 0; j < graph.n; j++ {if graph.edge[vex][j] == 1 && !visited[j] {// 进入队列，进入（逻辑上的）下一层queue = append(queue, j)// 访问新入队的邻接点fmt.Printf("%d ", graph.vex[j].data)visited[j] = true}}}}}
}// 定位顶点
func SearchVex(vex []Vex, data int) Vex {for i := 0; i < len(vex); i++ {if vex[i].data == data {return vex[i]}}return Vex{}
}// 打印邻接矩阵
func PrintEdge(edge [][]int) {for i := 0; i < len(edge); i++ {for j := 0; j < len(edge[i]); j++ {fmt.Print(edge[i][j], " ")}fmt.Println()}
}// 判断是否连通，打印连通分量（修改bfs）
// 广度优先搜索遍历（基于邻接矩阵的图）
func BFSTraverse_judgelinked(graph *Graph) {// 访问标记数组 初始化为false[默认]：都未访问visited := make([]bool, graph.n)// 暂存队列（用切片模拟）queue := make([]int, 0)// 访问到的点数量var count int// 连通分量数var num intfmt.Println("连通分量路径：")// 遍历每一个顶点for i := 0; i < graph.n; i++ {// 如果没有访问// 一般在一个visit中就可以遍历完整个连通图，条件不满足的原因是图是一个非连通图// 准备一个path存放路径path := make([]int, 0)// 优化减少循环次数if count == graph.n {break}if!visited[i] {// 先清空队列，避免之前连通分量遗留的顶点干扰当前遍历queue = queue[:0]// 将当前访问的节点位置加入队列queue = append(queue, i)visited[i] = truecount++// 访问path = append(path, graph.vex[i].data)// 找当前层所有点的其他邻接点（遍历队列）for len(queue) > 0 {// 取出队列的第一个点vex := queue[0]queue = queue[1:]for j := 0; j < graph.n; j++ {if graph.edge[vex][j] == 1 && !visited[j] {// 进入队列，进入（逻辑上的）下一层queue = append(queue, j)// 访问新入队的邻接点path = append(path, graph.vex[j].data)visited[j] = truecount++}}}}// 有连通分量打印if len(path) != 0 {num++fmt.Println(path)}}if num == 1 {fmt.Println("该图是连通图")} else {fmt.Println("该图不是连通图")}
}// 基本思想：从起点开始并加入path，拿着当前节点去遍历其邻接点，有邻接点就加入path，并标记，相等的时候就直接打印path；找不到就回溯，去掉标记，继续搜索
func PrintSimplePath(graph *Graph, start, end int) []int {// 用于存储所有找到的路径（如果要找所有路径时启用，初始注释掉下面这行来实现只找一条路径并打印的功能）// var allPaths [][]intvar path []intvisited := make([]bool, graph.n)var dfs func(int) booldfs = func(current int) bool {// 标记当前节点visited[current] = truepath = append(path, graph.vex[current].data)// 找到终点，直接返回trueif current == end {// 如果只找一条路径，直接打印// fmt.Println(path)// 如果要找所有路径，将当前路径加入到allPaths中// allPaths = append(allPaths, append([]int{}, path...))return true}// 遍历当前节点的所有邻接点for i := 0; i < graph.n; i++ {// 邻接点未被访问过，且存在邻接边if!visited[i] && graph.edge[current][i] == 1 {// 邻接点未被访问过，就继续搜索if dfs(i) {return true}}}// 回溯，移除当前节点path = path[:len(path)-1]visited[current] = falsereturn false}dfs(start)// 如果只找一条路径，无需返回值（直接打印了），如果要找所有路径，返回收集的所有路径// return allPathsreturn path
}// 输入寻路的数据
func SearchPath(graph *Graph) {fmt.Println("请输入起始顶点：")var start intfmt.Scan(&start)fmt.Println("请输入终止顶点：")var end intfmt.Scan(&end)startvex := SearchVex(graph.vex, start)endvex := SearchVex(graph.vex, end)startid := startvex.idendid := endvex.id// 基于上面的函数， 这里求两点之间的简单路径并打印出来path := PrintSimplePath(graph, startid, endid)if len(path) == 0 {fmt.Println("从输入的起始顶点到终止顶点之间不存在路径")return}fmt.Println("从输入的起始顶点到终止顶点之间存在路径，路径为：")fmt.Println(path)
}// 计算顶点的度数（一律看作有向图）
func CaculateDegree(graph *Graph) {edge := graph.edgesumdb := make([]int, graph.n)for i := 0;i < graph.n; i++{// 拿到点,将这行和这列的数字加和sum := 0// 加行hang := 0for j := 0; j < graph.n; j++ {hang += edge[i][j]}// 加列lie := 0for j := 0; j < graph.n; j++ {lie += edge[j][i]}// 加和sum = hang + liesumdb[i] = sum}for i := 0; i < graph.n; i++ {fmt.Println("顶点", graph.vex[i].data, "的度数为：", sumdb[i])}
}//----------------------------------------------------------------------------// ----------------------------邻接表表示的图--------------------------------// 复习：邻接表的存储结构：总的list是一个数组，每个元素是data和邻接节点链表的指针// 节点定义
type Node struct {data intnext *Node// 可以直接存储一个visited值，这样直接就判断是否被访问过：node.visited == true就是被访问过// 或者可以像邻接矩阵一样，用一个visited数组来存储是否被访问过，但是要加id属性
}// 邻接表表示的图（List）
type GraphList struct {datas[] int        // 顶点数据nodes []*Node  // 邻接节点列表n int       // 邻接节点个数m int       // 边数
}func CreateGraphList() *GraphList {// 目的：创建一个邻接表表示的图，返回一个邻接表表示的图graph := new(GraphList)// 填充邻接表fmt.Println("请输入顶点数：")var n intfmt.Scan(&n)var m intfmt.Println("请输入边数：")fmt.Scan(&m)graph.n = ngraph.m = mdatas := make([]int, n)nodes := make([]*Node, n)for i := 0; i < n; i++ {fmt.Println("请输入第", i+1, "个顶点的数据：")var data intfmt.Scan(&data)datas[i] = data}graph.datas = datas// 点和边分开进行填充fmt.Println("请输入边的关系:")for i := 0; i < m; i++ {var start, end intfmt.Scan(&start, &end)// 输入的是值data,要找到元素，需要遍历定位// 先考虑start有效性startIndex := GetIndex(graph, start)if startIndex == -1 {fmt.Println("输入的起始顶点不存在，请重新输入合法的起始顶点")continue}// 再考虑end有效性+end的位置endIndex := GetIndex(graph, end)if endIndex == -1 {fmt.Println("输入的终止顶点不存在，请重新输入合法的终止顶点")continue}// 添加节点:nodes[startIndex]相当于单链表头指针if nodes[startIndex] == nil {// 如果起始顶点邻接链表为空，则直接添加节点newNode := CreateListNode(end)nodes[startIndex] = newNode} else {// 如果起始顶点邻接链表不为空，则找到最后一个节点，添加新的节点cur := nodes[startIndex]for cur.next != nil {cur = cur.next}newNode := CreateListNode(end)cur.next = newNode}}// 返回邻接表graph.nodes = nodesreturn graph
}func PrintGraphList(graph *GraphList) {// 打印邻接表fmt.Println("邻接表为：")for i := 0; i < graph.n; i++ {fmt.Print(graph.datas[i], ":")node := graph.nodes[i]for node != nil {fmt.Print(node.data, " ")node = node.next}}
}// 通过数据找到邻接表中的索引
func GetIndex(graph *GraphList,data int)int{for i := 0; i < len(graph.datas); i++ {if graph.datas[i] == data {return i}}return -1
}func CreateListNode(data int) *Node {node := new(Node)node.data = datanode.next = nilreturn node
}// 基于邻接表的图进行深度优先搜索
func DFSList(graph *GraphList) {visited = make([]bool, graph.n)// 遍历每一个顶点，对满足条件的顶点进行深度优先搜索// 条件：顶点未被访问for i := 0; i < graph.n; i++ {if !visited[i] {// 传入图和顶点位置dfsList(graph, i)}}
}func dfsList(graph *GraphList,index int){// 找当前点的邻接点(遍历当前点的邻接链表) + 未被访问curNode := graph.nodes[index]fmt.Printf("%d ", graph.datas[index])visited[index] = truefor curNode != nil {// 找到邻接点curNode = curNode.nextif curNode != nil{newIndex := GetIndex(graph,curNode.data)if !visited[newIndex] {dfsList(graph, newIndex)}}}
}func BFSList(graph *GraphList) {visited := make([]bool, graph.n)queue := make([]int, 0)for i := 0; i < graph.n; i++ {if!visited[i] {// 未访问，加入队列中，这里加入的是顶点的索引queue = append(queue, i)visited[i] = true// 访问并输出当前顶点数据（只输出一次）fmt.Printf("%d ", graph.datas[i])for len(queue) > 0 {// 取出队列的第一个点（索引）nodeindex := queue[0]queue = queue[1:]// 找当前点的邻接点(遍历当前点的邻接链表) + 未被访问curNode := graph.nodes[nodeindex]for curNode!= nil {newIndex := GetIndex(graph, curNode.data)if!visited[newIndex] {// 邻接顶点未被访问，加入队列，标记为已访问，并输出其数据queue = append(queue, newIndex)visited[newIndex] = truefmt.Printf("%d ", graph.datas[newIndex])}curNode = curNode.next}}}}
}// 判断图是否连通，打印连通分量
func PrintSomeListByBFS(graph *GraphList) {visited := make([]bool, graph.n)queue := make([]int, 0)components := make([][]int, 0)for i := 0; i < graph.n; i++ {path := make([]int, 0)if!visited[i] {// 未访问，加入队列中，这里加入的是顶点的索引queue = append(queue, i)visited[i] = true// 访问并输出当前顶点数据（只输出一次）path = append(path, graph.datas[i])for len(queue) > 0 {// 取出队列的第一个点（索引）nodeindex := queue[0]queue = queue[1:]// 找当前点的邻接点(遍历当前点的邻接链表) + 未被访问curNode := graph.nodes[nodeindex]for curNode!= nil {newIndex := GetIndex(graph, curNode.data)if!visited[newIndex] {// 邻接顶点未被访问，加入队列，标记为已访问，并输出其数据queue = append(queue, newIndex)visited[newIndex] = truepath = append(path, graph.datas[newIndex])}curNode = curNode.next}}}if len(path) > 0 {components = append(components, path)}}fmt.Println("连通分量为：")for _, path := range components {fmt.Println(path)}if len(components) == 1 {fmt.Println("图是连通图")} else {fmt.Println("图不是连通图")}
}// 判断图中指定两点的简单路径（一条就行）
func FindPathList(graph *GraphList){fmt.Println("请输入要查找的起始顶点:")var start intfmt.Scan(&start)fmt.Println("请输入要查找的目标顶点:")var end intfmt.Scan(&end)visited = make([]bool, graph.n)startIndex := GetIndex(graph, start)if startIndex < 0 {// 起始顶点不存在，直接返回return}endIndex := GetIndex(graph, end)if endIndex < 0 {// 目标顶点不存在，直接返回return}// 得到从最底层返回的路径path,ok := dfsFindPath(graph, startIndex, endIndex)if ok{fmt.Println("路径为：", path)}else{fmt.Println("未找到从", start, "到", end, "的简单路径")}
}// 基于dfs的找路
func dfsFindPath(graph *GraphList, curIndex, endIndex int) ([]int, bool) {visited[curIndex] = truepath := make([]int, 0)path = append(path, graph.datas[curIndex])if curIndex == endIndex {return path, true}curNode := graph.nodes[curIndex]for curNode!= nil {nextIndex := GetIndex(graph, curNode.data)if !visited[nextIndex] {subPath, found := dfsFindPath(graph, nextIndex, endIndex)if found {// 返回当前路径和子路径的合并结果return append(path, subPath...), true}}curNode = curNode.next}return nil, false
}// 打印图的各个顶点的度
func PrintListLevel(graph *GraphList) {//1. 邻接表只有出度，如果要算一个顶点的度，需要遍历整个邻接表//2. 可以直接再创建一个逆邻接表，找指定顶点的所有入边，然后求邻接表的出度，再加和degree := make([]int, 0)// 遍历邻接表for i := 0; i < graph.n; i++ {ru_degree := 0chu_degree := 0// 遍历每一个顶点的邻接链表curNode := graph.nodes[i]for curNode!= nil {// 遍历当前顶点的邻接表,计算出度chu_degree++curNode = curNode.next}// 遍历其他点，求入度for j := 0; j < graph.n; j++ {if i != j{curNode := graph.nodes[j]for curNode!= nil {// 遍历当前顶点的邻接表,计算出度if curNode.data == graph.datas[i] {ru_degree++}curNode = curNode.next}}}temp := ru_degree + chu_degreedegree = append(degree, temp)}fmt.Println("顶点及其度数：")for i := 0; i < graph.n; i++ {fmt.Printf("顶点 %d 的度: %d\n", graph.datas[i], degree[i])}
}//--------------------------------------------------------------------------func main() {//------------------------------邻接矩阵测试-------------------------------//// 创建邻接矩阵表示的图n, m, vex,edge := CreateGraph()PrintEdge(edge)// 封装图（邻接矩阵表示的图）graph := Graph{vex: vex, edge: edge, n: n, m: m}// 吸收回车键fmt.Scanln()// 调用深度优先搜索fmt.Println("深度优先搜索结果（邻接矩阵）：")DFSTraverse(&graph)fmt.Println()// 调用广度优先搜索fmt.Println("广度优先搜索结果（邻接矩阵）：")BFSTraverse(&graph)fmt.Println()// 判断图是否为连通图，打印其连通分量BFSTraverse_judgelinked(&graph)// 搜索两点的简单路径SearchPath(&graph)// 打印度数CaculateDegree(&graph)//-------------------------------邻接表测试------------------------------//// 创建并打印邻接表表示的图graphlist := CreateGraphList()PrintGraphList(graphlist)fmt.Println()// 调用深度优先搜索fmt.Println("深度优先搜索结果（邻接表）：")DFSList(graphlist)fmt.Println()// 调用广度优先搜索fmt.Println("广度优先搜索结果（邻接表）：")BFSList(graphlist)fmt.Println()// 判断图是否为连通图，打印其连通分量PrintSomeListByBFS(graphlist)// 搜索两点的简单路径FindPathList(graphlist)// 打印图的各个顶点的度PrintListLevel(graphlist)//-----------------------------------------------------------------------////总结：//深度优先：遍历点集，访问当前点，再访问其邻接点，直到无法访问，再返回上一层，再访问其邻接点，直到无法访问，再返回上一层，直到所有点都被访问完//广度优先：遍历点集，访问当前点（访问+入栈），从队列中取出每一个点找他的邻接点，直到队列为空//打印连通分量：直接改造广度优先遍历，记录所有连通分量（ 个人觉得广度优先的改造更容易 ）//搜索两点的简单路径(一条)：直接改造深度优先遍历（dfs），记录路径，直到找到目标点，返回路径（个人觉得深度优先的改造更容易）//打印图中各顶点的度：直接根据存储结构的不同去特殊计算}

上面代码的最后，我结合邻接矩阵和邻接表的特点，对图的操作做了一个简单的方法总结，如果对你有用，请点个赞？收个藏？或者加个关注？