7.4.1无向图的连通分量和生成树

============================================================
e1:建立无向图的深度优先森林(DFSForest,G2).
// xx.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "stdio.h"
#include "stdlib.h"
//#####################图的邻接表声明，和相关操作。
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int VRType;
typedef char VertexType;
typedef int Status;


typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置。
struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
//int w;

void CreateGraph(ALGraph &G);
void DFSTraverse(ALGraph G, Status (*Visit)(int v));
Status printGraph(int v);
int FirstAdjVex(ALGraph G, int v);
int NextAdjVex(ALGraph G, int v, int w);
void DFS(ALGraph G, int v);
//#####################树的孩子兄弟链表声明，和相关操作。
//树的孩子兄弟链表。

typedef char TElemType;
typedef struct CSNode
{
TElemType data;
CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

typedef CSTree QElemType;
//typedef char TElemType;
TElemType Nil=' ';
void DFSForest(ALGraph G,CSTree &T);
void DFSTree(ALGraph G,int v,CSTree &T);
TElemType GetVex(ALGraph G,int v);
void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType));
TElemType Value(CSTree p);
void vi(TElemType c);
//#####################队列的声明，和相关操作。
//队列的链式存储结构
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr;

struct LinkQueue
{
QueuePtr front,rear;
};

Status DeQueue(LinkQueue &Q,QElemType &e);
Status InitQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
Status EnQueue(LinkQueue &Q,QElemType e);
//##################
void main( void )
{
printf("-------beg-----\n");
int i;
ALGraph G;
ArcNode *p;
CSTree cst;
CreateGraph(G);

for(i= 0; i < G.vexnum; i++)
{
printf("-%d#%c",i,G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p != NULL)
{
printf("--->");
printf("%c",G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
printf("------------------------in_main_before_DFSTraverse--\n");
DFSTraverse(G, printGraph);
printf("------------------------in_main_before_DFSForest--\n");
DFSForest(G,cst);
printf("-----------------------------------------before_LevelOrderTraverse--\n");
//printf("--");
LevelOrderTraverse(cst,vi);
//printf("--\n");
printf("-------end-----\n
");
}//main
//建立无向图。
void CreateGraph(ALGraph &G)
{
int i, j = 0, k = 0;
char hand, tide;
ArcNode *p;
char vertices[]={'a','

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库7.4.1无向图的连通分量和生成树在线全文阅读。