8000 完成建图 · mohuishou/go-algorithm@2559768 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2559768

Browse files
mohuishoumohuishou
committed
完成建图
1 parent 945fff2 commit 2559768

File tree

4 files changed

+78
-5
lines changed

4 files changed

+78
-5
lines changed

‎Graph/Graph.go

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,13 @@
11
package Graph
22

3+
import (
4+
"bufio"
5+
"io"
6+
"os"
7+
"strconv"
8+
"strings"
9+
)
10+
311
// EdgeType 边的权值类型
412
type EdgeType int
513

@@ -42,3 +50,58 @@ func (graph Graph) AddEdge(s, t VextexType, weight EdgeType) {
4250
edge.next = graph[s].FisrtEdge
4351
graph[s].FisrtEdge = edge
4452
}
53+
54+
//BuildGraph 通过读取文件建图
55+
//文件格式要求:
56+
//顶点个数 边数
57+
//顶点v1 顶点V2 边的权重
58+
//...
59+
func BuildGraph(path string) (graph Graph) {
60+
f, err := os.Open(path)
61+
if err != nil {
62+
panic(err)
63+
}
64+
buf := bufio.NewReader(f)
65+
66+
i := 0
67+
//边的数目
68+
var enum int
69+
for {
70+
line, err := buf.ReadString('\n')
71+
if err != nil {
72+
if err == io.EOF {
73+
return graph
74+
}
75+
panic(err)
76+
}
77+
line = strings.TrimSpace(line)
78+
data := strings.Split(line, " ")
79+
if i == 0 {
80+
n, err := strconv.Atoi(data[0])
81+
if err != nil {
82+
panic(err)
83+
}
84+
enum, err = strconv.Atoi(data[1])
85+
if err != nil {
86+
panic(err)
87+
}
88+
graph = CreateGraph(n)
89+
} else if i <= enum {
90+
s, err := strconv.Atoi(data[0])
91+
if err != nil {
92+
panic(err)
93+
}
94+
t, err := strconv.Atoi(data[1])
95+
if err != nil {
96+
panic(err)
97+
}
98+
weight, err := strconv.Atoi(data[2])
99+
if err != nil {
100+
panic(err)
101+
}
102+
graph.AddEdge(VextexType(s), VextexType(t), EdgeType(weight))
103+
}
104+
i++
105+
}
106+
107+
}

‎Graph/Graph_test.go

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,18 @@
11
package Graph
22

33
import (
4+
"fmt"
45
"testing"
56
)
67

78
func TestGraph(t *testing.T) {
8-
graph := CreateGraph(3)
9-
graph.AddEdge(0, 1, 1)
10-
graph.AddEdge(0, 2, 2)
11-
graph.AddEdge(1, 2, 3)
9+
graph := BuildGraph("test.txt")
10+
fmt.Println(graph)
11+
e := graph[1].FisrtEdge
12+
for e != nil {
13+
if e.v != 2 || e.weight != 3 {
14+
t.Fatal("错误：建图失败，e.v!=2,e.weight!=3")
15+
}
16+
e = e.next
17+
}
1218
}

‎Graph/README.MD

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
11
Graph
22
====
33

4-
建图
4+
邻接表法建图

‎Graph/test.txt

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
3 3
2+
0 1 1
3+
0 2 2
4+
1 2 3

0 commit comments

Comments
 (0)
0