-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathGraphm.cpp
More file actions
77 lines (67 loc) · 1.62 KB
/
Graphm.cpp
File metadata and controls
77 lines (67 loc) · 1.62 KB
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
70
71
72
73
74
75
76
77
//implementation for the adjacency matrix representation
class Grpahm : public Graph
{
private:
int numVertex, numEdge; //number of verteces, edges
int **matrix; //pointer to the adjacency matrix
int *mark; //pointer to mark array
public:
Graphm(int numVert)
{Init(numVert);}
~Graphm()
{
delete [] mark;
for (int i=0; i< numVertex; i++)
delete [] matrix[i];
delete [] matrix;
}
void Init(int n)
{
int i;
numVertex = n;
numEdge = 0;
mark = new int[n];
for (i=0; i<numVertex; i++)
mark[i] = UNVISITED;
matrix = (int**) new int*[numVertex];
for (i=0; i<numVertex; i++)
matrix[i] = new int[numVertex];
for (i=0; i<numVertex; i++)
for (int j=0; j<numVertex; j++)
matrix[i][j]=0;
}
int n() {return numVertex;}
int e() {return numEdge;}
//return first neighbor of "v"
int first(int v)
{
for (int i=0; i<numVertex; i++)
if (matrix[v][i] != 0) return i;
return numVertex;
}
//return v's next neighbor after w
int next(int v, int w)
{
for (int i=w+1; i<numVertex; i++)
if (matrix[v][i] != 0)
return i;
return numVertex;
}
//set edge (v1,v2) to "wt"
void setEdge(int v1, int v2, int wt)
{
Assert(wt>0, "Illegal weight value");
if (matrix[v1][v2] == 0) numEdge++;
matrix[v1][v2] = wt;
}
void delEdge(int v1, int v2)
{
if (matrix[v1][v2] != 0) numEdge--;
matrix[v1][v2] = 0;
}
bool isEdge(int i, int j)
{return matrix[i][j] != 0;}
int weight(int v1, int v2) {return matrix[v1][v2];}
int getMark(int v) {return mark[v];}
void setMark(int v, int val) {mark[v] = val;}
};