graph.cpp

数据结构（C＋＋版）的演示程序

// Graph.cpp: implementation of the CGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "BFSearch.h"
#include "Graph.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraph::CGraph()
{
    int i,  j;
    numVertex  =  0;
    numEdge =  0;
    for(i=0;  i<20;  i++)
	{
        mark[i]  = UNVISITED;
		pos[i].x = 0;
		pos[i].y = 0;
	}
    for(i=0;  i< 20;  i++)  // Edges start w/  0 weight
        for(j=0; j<20; j++) 
			matrix[i] [j] = 0;

}

int CGraph::n()     // Number of vertices
{  
	return numVertex;   
}  
int CGraph::e()     // Number of edges
{  
	return numEdge;    
}
int CGraph::first(int v)  // Return v's first neighbor
{    
    int i;
	if(v < 0)
		return -1;
    for  (i=0;  i<numVertex;  i++)
        if  (matrix[v][i] != 0)  return i;
    return i;           // Return n if none
}
int CGraph::next(int v1,  int v2)   // Get v1's neighbor after v2
{
    int i;
	if((v1 < 0)||(v2 < 0))
		return -1;
    for(i=v2+1;  i<numVertex;  i++)
        if  (matrix[v1][i]  != 0) return i;
    return  i;
}

int CGraph::getEdge(int v1,  int v2)
{
    return matrix[v1][v2];
}

int CGraph::getMark(int v)  
{ 
	if(v<0)
		return -1;
	return mark[v];  
}
void CGraph::setMark(int v,  int val)  
{ 
	mark[v]  = val;  
}
void CGraph::AddVertex(CPoint p)
{
	pos[numVertex].x = p.x;
	pos[numVertex].y = p.y;
	if(numVertex<20)
		numVertex++;
}
void CGraph::SetEdge(int v1,  int v2,  int w)  
{
    if(matrix[v1][v2] == 0)  
		numEdge++;
    matrix[v1][v2]  = w;
}