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','

b','c','d','e'};
char head[]={'a','a','b','b','c','c'};
char tail[]={'b','d','c','e','d','e'};
//v1v2,v1v4,23,25,34,35,

//cout<<"input the number for vexnum and arcnum:";
//cin>>G.vexnum>>G.arcnum;
G.vexnum =5;
G.arcnum =6;
//cout<<endl;
//cout<<"input"<<G.vexnum<<"char for vexs:";
for(i=0; i < G.vexnum; i++) //输入顶点数据。
G.vertices[i].data=vertices[i];

//cout<<endl;
for(i=0;i<G.vexnum;++i)
G.vertices[i].firstarc=NULL;//初始化顶点指针。

//cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;
j = 0;
k = 0;
for(i=0; i < G.arcnum; i++) //输入弧数据。
{
//cout<<i<<":";
//cin>>hand;
//cin>>tide;
hand=head[i];
tide=tail[i];
while (hand != G.vertices[j].data)
j++;
while (tide != G.vertices[k].data)
k++;
p=new ArcNode;
p->adjvex=j;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p;
p=new ArcNode;
p->adjvex=k;
p->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;

j = 0;
k = 0;
//cout<<endl;
}
}//CreateGraph
//深度遍历G。
void DFSTraverse(ALGraph G, Status (*Visit)(int v))
{
int j;
VisitFunc = Visit;
for( j=0; j<G.vexnum; j++)
visited[j] = 0;
for(j=0; j<G.vexnum; j++)
if(!visited[j])
{
printf("-in_DFSTraverse-j=%d-\n",j);
DFS(G, j);
}
}//DFSTraverse
//从顶点v开始，访问G(和v连通的)。
void DFS(ALGraph G, int v)
{
int w;
visited[v]=1;
VisitFunc(v);
for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))
{
printf("-in_DFS1-v=%d,w=%d-\n",v,w);
if(!visited[w])
DFS(G, w);
printf("-in_DFS2-v=%d,w=%d-\n",v,w);
}
}//DFS

//返回第v个顶点的第一个邻接点。
int FirstAdjVex(ALGraph G, int v)
{
ArcNode *p;
p = G.vertices[v].firstarc;
while(p != NULL)
{
if(visited[p->adjvex] != 1)
return p->adjvex;
p = p->nextarc;
}
return 0;
}//FirstAdjVex

//返回第v个顶点，相对于第w个顶点的邻接点。
int NextAdjVex(ALGraph G, int v, int w)…… 此处隐藏：3519字，全部文档内容请下载后查看。喜欢就下载吧 ……