PAT:05-1. List Components (25),Go语言解答

u013564276 · · 1660 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题目大概意思：给定一个有N个顶点和E个边的无向图，请分别用DFS和BFS遍历无向图。假定顶点编号为0到N-1，在遍历的时候总是从最小编号的顶点出发，在访问相邻结点的时候，按升序的方式访问。

For a given undirected graph with N vertices and E edges, pleaselist all the connected components by both DFS and BFS. Assume thatall the vertices are numbered from 0 to N-1. While searching,assume that we always start from the vertex with the smallestindex, and visit its adjacent vertices in ascending order of theirindices.

Input Specification:

Each input file contains one test case. For each case, the firstline gives two integers N (0

Output Specification:

For each test case, print in each line a connected component inthe format "{ v1 v2 ... vk }". First print the result obtained byDFS, then by BFS.

Sample Input:

Sample Output:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

001 package main
002
003 import (
004   "fmt"
005   "container/heap"
006   "container/list"
007 )
008 var visited = make([]bool, 10)//题目给出顶点数不会超过10，至少为1
009 var G =make([]IntHeap, 10)
010
011 func main(){
012   varNumOfV,NumOfE int
013   //接受顶点数和边数
014   _, err:= fmt.Scanf("%d %d\n",&NumOfV,&NumOfE)
015   iferr != nil {
016     fmt.Println("error", err)
017   }
018   fori := 0; i<</SPAN>NumOfE; i++{//给顶点列表装入数据
019     var v1, v2int
020     _, err =fmt.Scanf("%d%d\n",&v1,&v2)
021     if err != nil {
022        fmt.Println("error",err)
023     }
024     heap.Push(&G[v1],v2)
025     heap.Push(&G[v2],v1)
026   }
027   //************************************
028   //开始遍历
029   //*************************************
030   fori:= 0; i<</SPAN>NumOfV; i++ {
031     if !visited[i]{
032        fmt.Print("{ ")
033        dfs(i);
034        fmt.Print("}\n")
035     }
036   }
037   //重置visited数组
038   fori := range visited {
039     visited[i]= false
040   }
041   fori := 0; i<</SPAN>NumOfV; i++ {
042     if !visited[i]{
043        fmt.Print("{ ")
044        bfs(i)
045        fmt.Print("}\n")
046     }
047   }
048 }
049 //深度优先搜索（Depth First Search, DFS）：
050 //访问下一个可见的未被访问的元素，
051 //如果所有的可见元素都被访问过，则返回上一个元素
052 func dfs(v int) (){
053   visited[v] =true
054   fmt.Printf("%d",v)
055   for_,neibor := range G[v]{ //遍历相邻节点
056     if !visited[neibor] {
057        dfs(neibor)
058     }
059   }
060 }
061 //广度优先搜索（Breadth First Search, BFS）:
062 //类似层序遍历的思想，使用队列来操作，先把1放入队列，出队时，将1的所有邻接点放入队列
063 func bfs(v int) (){
064   varls = list.New()
065   visited[v] =true
066   fmt.Printf("%d", v)
067   ls.PushBack(v)
068   forls.Len() != 0 {
069     ele := ls.Front()
070     ls.Remove(ele)
071     theV := ele.Value.(int)//theV.Value是接口类型，所以需要断言
072
073     for _,neibor := range G[theV]{//遍历相邻节点
074        if !visited[neibor] {
075         visited[neibor] = true
076         fmt.Printf("%d", neibor)
077         ls.PushBack(neibor)
078        }
079     }
080   }
081 }
082
083 //heap操作,最小堆
084 type IntHeap []int
085
086 func (hIntHeap)Len() int    { returnlen(h) }
087 func (hIntHeap)Less(i, jint) bool { return h[i]<</SPAN> h[j] }
088 func (hIntHeap)Swap(i, jint)   { h[i], h[j] =h[j], h[i] }
089
090 func (h*IntHeap) Push(xinterface{}){
091   // Push andPop use pointer receivers because they modify the slice'slength,
092   // not justits contents.
093   *h =append(*h,x.(int))
094 }
095
096 func (h*IntHeap) Pop() interface{} {
097   old:= *h
098   n:= len(old)
099   x:= old[n-1]
100   *h =old[0 : n-1]
101   returnx
102 }

有疑问加站长微信联系（非本文作者）