awe的程設筆記

Graph ADT

Graph.h:

#ifndef GRAPH_H
#define GRAPH_H

class Graph
{
private:
void operator = ( const Graph& ) {} // protected assignment
Graph(const Graph&) {} // protected constructor
public:
Graph(){}
virtual ~Graph() {}

//initialize a graph of n vertice
virtual void Init(int n ) = 0;

//return the number of vertice and edges
virtual int n() = 0;
virtual int e() = 0;

//return v's first neighbor
virtual int first(int v) = 0;

//return v's next neighbor
virtual int next(int v ,int w) = 0;

//Set the weight for an edge
// i, j : the vertice
// wgt : Edge weight
virtual void setEdge(int v1 ,int v2 ,int wgt) = 0;

// Delete an edge
// i , j : the vertice
virtual void delEdge(int v1,int v2) = 0;

//Determine if an edge is in the Graph
// i,j : the vertice
//Retutn : true if edge i,j has non-zero weight
virtual bool isEdge(int i ,int j) = 0;

//Return an Edge's weight
// i,j : the vertices
// Return : the weight of edge i,j or zero
virtual int weight(int v1,int v2) = 0;

//Get and Set the mask value of a vertex
// v : The vertex
// val : the value to set
virtual int getMark(int v) = 0;
virtual void setMark(int v ,int val) = 0;
};
#endif

matrix graph 實作介面

graphm.h

#include"Graph.h"
#include<iostream>

using namespace std;

static const int UNVISITED = 0;
static const int VISITED = 1;

class Graphm : public Graph
{
private:
int numVertex , numEdge; // Store numbers of vertices end edges
int **matrix; // Pointer to 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) // Initialize the Graph
{
int i;
numVertex = n;
numEdge = 0;

mark = (int*) new int[numVertex] ;

for(i = 0 ; i < numVertex ; i++)
{
mark[i] = UNVISITED;
}
matrix = (int**) new int*[numVertex];

for(i = 0 ; i < numVertex ; i++)
{
matrix[i] = (int*) 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; }

int first(int v) // return first neighbor of vertice 'v'
{
for(int i = 0 ; i < numVertex ; i++)
{
if(matrix [v][i] != 0 )
return i;
}
return numVertex; //Return n if none
}

int next(int v , int w) // Return next neighbor of 'v' after 'w'
{
for(int i = w+1 ; i < numVertex ; i++)
{
if(matrix[v][i] != 0)
return i;
}
return numVertex;
}

void setEdge(int v1 ,int v2 , int wt)
{
while(wt <= 0 )
{
cout<<"ilegal weight value!"<<endl;
cout<<"Please try another : ";
cin >> wt;
}

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 v1,int v2)
{
return matrix[v1][v2] != 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;}

void print()
{
for(int i = 0 ; i < numVertex ; i++)
{
for(int j = 0 ; j < numVertex ; j++)
{
cout<<matrix[i][j]<<"\t";
}
cout<<endl;
}
}
};

功能測試程式，與深廣度優先搜尋

main.cpp

#include"Graphm.h"
#include<iostream>
#include"Graph.h"
#include"AQueue.h"
using namespace std;

AQueue<int> traverseQueue(8);

void DFS(Graph* , int);
void BFS(Graphm* ,int , Queue<int>* Q);

int main()
{
Graphm G1(6);
int vertex1,vertex2,weight;

for(int i = 0 ; i < 7;i++)
{
cout<<"Please enter Edge: ";
cin>>vertex1>>vertex2;
G1.setEdge(vertex1,vertex2,1);
}

G1.print();

cout<<"Depth first Search: ";
DFS(&G1,0);
cout<<endl;

for(int i = 0 ; i < G1.n() ; i++)
{
G1.setMark(i,UNVISITED);
}

cout<<"Breadth first Search: ";
BFS(&G1,0,&traverseQueue);
return 0;
}

void DFS(Graph *G , int v)
{
cout<<v<<" ";
G->setMark(v,VISITED);
for(int w = G->first(v) ; w < G->n() ; w = G->next(v,w) )
{
if(G->getMark(w) == UNVISITED)
DFS(G,w);
}
}

void BFS(Graphm *G , int start ,Queue<int>* Q)
{
int v,w;
Q->enqueue(start);
G->setMark(start,VISITED);

while(Q->length() != 0)
{
v = Q->dequeue();
cout<<v <<" ";
for( w = G->first(v); w < G->n() ; w = G->next(v,w))
{
if(G->getMark(w) == UNVISITED)
{
G->setMark(w,VISITED);
Q->enqueue(w);
}
}
}
cout<<endl;
}

附錄: 廣度優先搜尋需要的佇列資料結構

Queue ADT

Queue.h:

#ifndef QUEUE_H
#define QUEUE_H

template <typename E>
class Queue
{
private:
void operator = (const Queue&){}
Queue (const Queue&) {}
public:
Queue(){};
virtual ~Queue(){}

virtual void clear() = 0;
virtual void enqueue(const E&) = 0;
virtual E dequeue() = 0;

virtual const E& frontValue()const = 0;
virtual int length() const = 0;
};
#endif

陣列環形Queue實作介面

AQueue.h

#include"Queue.h"
#include<iostream>

using namespace std;

const int defaultSize = 10;

template <typename E>
class AQueue : public Queue<E>
{
private:
int maxSize;
int front;
int rear;
E* listArray;

public:
AQueue(int size =defaultSize)
{
maxSize = size + 1;
rear = 0;
front = 1;
listArray = new E[maxSize];
}

~AQueue()
{
delete [] listArray;
}

void clear() {rear = 0 ; front = 1; }

void enqueue(const E& item)
{
if( (rear +2 )% maxSize == front) // Queue is full
{
E* newListArray = new E [maxSize *2 -1];
int newRear = 0;
while(front != (rear+1) % maxSize)
{
newListArray[newRear++] = listArray[front];
front = (front+1)% maxSize;
}
front = 0;
rear = newRear -1;
maxSize = maxSize* 2 -1;
delete [] listArray;
listArray = newListArray;
}
rear = (rear+1)%maxSize;
listArray[rear] = item;
}

E dequeue()
{
if(length() != 0 )
{
E it = listArray[front];
front = (front +1 )%maxSize;
return it;
}
else
{
cerr<<"This Queue is empty"<<endl;
}
}

const E& frontValue()const
{
if(length() != 0)
return listArray[front];
else
cerr<<"This Queue is empty"<<endl;
}

virtual int length()const
{
return ((rear + maxSize - front + 1)% maxSize);
}
};