图的基本算法的实现

#include"graph.h"
/*
*直观显示邻接表结构
*/
void Graph::DisplayStruct(){

ArcNode * arc;


for( int i = 0; i < graph.nVex; i ++){
arc = graph.adjlist[i].firstarc;
cout << "顶点" << i << endl;
while( arc){
cout << "邻接点" << arc->adjvex << " 权重" << arc->weight << endl;
arc = arc ->nextarc;
}
}
}
/*
*初始化bVisited数组，为每次遍历做准备
*/
void Graph::InitVisitArray(){
for( int i = 0; i < graph.nVex; i ++) bVisited[i] = false;
}//InitVisitArray

/*
*construct
*初始化图为空图，即让所有顶点的firstarc为NULL
*/
Graph::Graph(){

for( int i = 0; i < MaxSize; i++){
graph.adjlist[i].firstarc = NULL;
}
graph.nVex = MaxSize;
}//Graph

/*
*DFS深度优先搜索
*/
void Graph::DFS( int StartVex){
cout << StartVex; bVisited[StartVex] = true;


ArcNode * arc = graph.adjlist[StartVex].firstarc;


while( arc){
if( ! bVisited[arc->adjvex]){
DFS( arc ->adjvex);
}
arc = arc->nextarc;
}
}//DFS

/*
*BFS广度优先搜索
*/
void Graph::BFS( int StartVex){
int qu[MaxSize], front = -1, rear = -1;
ArcNode * arc; int p;


rear = ( rear + 1) % MaxSize;
qu[rear] = StartVex;
cout << StartVex;
bVisited[StartVex] = true;


while( front != rear){
front = ( front + 1) % MaxSize;
p = qu[front];
arc = graph.adjlist[p].firstarc;
while( arc){
if( ! bVisited[arc->adjvex]){
rear = ( rear + 1) % MaxSize;
qu[rear] = arc->adjvex;
cout << arc->adjvex;
bVisited[arc->adjvex] = true;
}
arc = arc->nextarc;
}
}
}//BFS

/*
*从邻接矩阵构造邻接表
*/
void Graph::MatrixToAdjlist( int data[][MaxSize]){
ArcNode * arc;


for( int row = 0; row < MaxSize; row ++){
for( int col = 0; col < MaxSize; col ++){
if( data[row][col] != INF){
arc = new ArcNode;
arc->adjvex = col; arc->weight = data[row][col];
arc->nextarc = graph.adjlist[row].firstarc;
graph.adjlist[row].firstarc = arc;
}
}
}
}//MatrixToAdjlist

/*
*邻接表转化为邻接矩阵
*/
void Graph::AdjlistToMatrix(){
ArcNode * arc;
int row, col;


for( row = 0; row < graph.nVex; row ++){
for( col = 0; col < graph.nVex; col ++){
matrix[row][col] = INF;
}
}


for( int i = 0; i < graph.nVex; i ++){
arc = graph.adjlist[i].firstarc;
while( arc){
matrix[i][arc->adjvex] = arc->weight;
arc = arc->nextarc;
}
}


for( row = 0; row < graph.nVex; row ++){
for( col = 0; col < graph.nVex; col ++){
if( matrix[row][col] == INF) cout << "INF\t";
else cout << matrix[row][col]<< "\t";
}
cout << endl;
}
}//AdjlistToMatrix

/*
*深度优先搜索非递归算法
*/
void Graph::DFS2( int StartVex){
int st[MaxSize], top = -1;
ArcNode * arc; int p;


st[++top] = StartVex;
cout << StartVex;
bVisited[StartVex] = true;

while( top > -1){
p = st[top--];
arc = graph.adjlist[p].firstarc;
while( arc){
if( ! bVisit

ed[arc->adjvex]){
st[++top] = arc->adjvex;
cout << arc->adjvex;
bVisited[arc->adjvex] = true;
}
arc = arc->nextarc;
}
}

}//DFS2

/*
*Prim算法构造最小生成树。Prim算法是添加边的算法
*/
void Graph::Prim( int StartVex){
int closest[MaxSize], lowcost[MaxSize];
int edges = 1;//已加入的边数
int minedge;
int min;//最小


for( int i = 0; i < graph.nVex; i ++){
closest[i] = StartVex;
lowcost[i] = matrix[StartVex][i];
}
lowcost[StartVex] = 0;
cout << "顶点" << StartVex << "已加入V中" << endl;


while( edges < graph.nVex){
min = INF;
for( i = 0; i < graph.nVex; i++){
if( lowcost[i] && lowcost[i] < min){
min = lowcost[i];
minedge = i;
}
}
cout << "顶点" << minedge << "已加入V中" << endl;
lowcost[minedge] = 0;
edges ++;
for( i = 0; i < graph.nVex; i++){
if( lowcost[i] && lowcost[i] > matrix[minedge][i]){
lowcost[i] = matrix[minedge][i];
closest[i] = minedge;
}
}
}

}//Prim

/*
*Kruscal算法产生最小生成树。该算法为一种选边贪心算法。
*/
void Graph::Kruscal( int StartVex){
struct Edge{
int u, v, weight;
};
int vset[MaxSize];//存储每个顶点的连通分量
Edge edge[2*MaxSize];//存储边集
int edges = 0;//代表生成的第几条边
int p = 0;//边集伪指针
int u, v;//暂存取出的边的起始点和终点

int row, col;
for( row = 0; row < graph.nVex; row ++){//初始化edge数组和vset数组
for( col = 0; col < graph.nVex; col ++){
if( matrix[row][col] != INF){
edge[edges].u = row; edge[edges].v = col; edge[edges].weight = matrix[row][col];
edges ++;
cout << " * " ;
}
}
vset[row] = row;
}
//Sort(vset);

int i;
edges = 1;
while( edges < graph.nVex){
u = edge[p].u; v = edge[p].v;//取出一条边
if( vset[u] != vset[v]){//若可以，加入V中
cout << "边" << u << ">>" << v << "加入V中" << endl;
edges ++;
for( i = 0; i < graph.nVex; i ++){//修正vset连通分量数组
if( vset[i] == vset[u]){
vset[i] = vset[v];
}
}
}
p ++;//访问下一条边
}
}//Kruscal