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

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:

8 60 70 12 04 12 43 5

Sample Output:

{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 } 001 packagemain002 003 import (004 "fmt"005 "container/heap"006 "container/list"007 )008 var visited = make([]bool, 10)//题目给出顶点数不会超过10，至少为1009 var G =make([]IntHeap,10)010 011 func main(){012 varNumOfV,NumOfEint013 //接受顶点数和边数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,v2int020 _, 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]=false040 }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(vint) (){053 visited[v]=true054 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(vint) (){064 varls =list.New()065 visited[v]=true066 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]= true076 fmt.Printf("%d",neibor)077 ls.PushBack(neibor)078 }079 }080 }081 }082 083 //heap操作,最小堆084 type IntHeap []int085 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:= *h098 n:= len(old)099 x:= old[n-1]100 *h =old[0: n-1]101 returnx102 }