2015/05/18

【C++】用vector實作adjacency list




1. include
?
1
2
#include <list>
#include <vector>

2. 建立edge class 並宣告
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class edge{
private:
    int weight, vertex_id;
     
public:
    edge(int w, int id){
        weight = w;
        vertex_id = id;
    }
    int getWeight() const{
        return weight;
    }
    int getId() const{
        return vertex_id;
    }
};
 
vector<list<edge>> adjList(N);

3. 判斷是否相連
?
1
2
3
4
5
6
7
8
9
int if_connect(int u, int v){
    vector<list<edge>>::iterator i = adjList.begin();
    i += u;
    list<edge> li = *i;
    for (list<edge>::iterator j = li.begin(); j != li.end(); j++) {
        if ((*j).getId() == v) return 1;
    }
    return 0;
}

4. 回傳edge的weight
?
1
2
3
4
5
6
7
8
9
int get_edge_weight(int u, int v){
    vector<list<edge>>::iterator i = adjList.begin();
    i += u;
    list<edge> li = *i;
    for (list<edge>::iterator j = li.begin(); j != li.end(); j++) {
        if((*j).getId() == v) return (*j).getWeight();
    }
    return -1; //not_connected
}

5. Code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <list>
#include <vector>
#define N 4
 
using namespace std;
 
class edge{
private:
    int weight, vertex_id;
     
public:
    edge(int w, int id){
        weight = w;
        vertex_id = id;
    }
    int getWeight() const{
        return weight;
    }
    int getId() const{
        return vertex_id;
    }
};
 
vector<list<edge>> adjList(N);
 
int if_connect(int u, int v){
    vector<list<edge>>::iterator i = adjList.begin();
    i += u;
    list<edge> li = *i;
    for (list<edge>::iterator j = li.begin(); j != li.end(); j++) {
        if ((*j).getId() == v) return 1;
    }
    return 0;
}
 
int get_edge_weight(int u, int v){
    vector<list<edge>>::iterator i = adjList.begin();
    i += u;
    list<edge> li = *i;
    for (list<edge>::iterator j = li.begin(); j != li.end(); j++) {
        if((*j).getId() == v) return (*j).getWeight();
    }
    return -1; //not_connected
}
 
int main(){
    /***建圖***/
    adjList[0].push_back(edge(4,1));
    adjList[0].push_back(edge(2,2));
    adjList[1].push_back(edge(4,0));
    adjList[1].push_back(edge(5,2));
    adjList[2].push_back(edge(2,0));
    adjList[2].push_back(edge(5,1));
    adjList[2].push_back(edge(1,3));
    adjList[3].push_back(edge(1,2));
     
/***遍歷***/
    vector<list<edge>>::iterator i;
    int v = 0;
    for (i = adjList.begin(); i != adjList.end(); i++) {
        printf("%d: ", v++);
        list<edge> li = *i;
        for (list<edge>::iterator j = li.begin(); j!= li.end(); j++)
            printf("(v=%d, w=%d) ", (*j).getId(), (*j).getWeight());
        puts("");
    }
    return 0;
}



於
標籤：