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

//名词解释：
//一个连通图（对于无向图）的生成树是一个极小的连通子图，它含有途中所有的顶点，但只有足以构成一个树的n-1条边。
//下面的程序为通过DFS深度优先遍历一个非连通图（会生成>1的生成树,用孩子兄弟链作为生成森林的存储结构）。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"



#define MAX_VERTEX_NUM 20//最大的顶点数



//边结点
typedef struct Edge {
struct Edge *next;//指向下一个边的指针
int index;//该边所依赖的顶点的位置
}Edge;

//顶点
typedef struct  {
char name[10];//顶点的名字
Edge * first;//指向依赖该顶点的第一条边
}Vertex;


typedef struct  {
int ver_num;//顶点的数
int edge_num;//边数
Vertex vertexs[MAX_VERTEX_NUM];
}Undigraph;


//根据名字找到顶点的位置
int get_location (Undigraph *ud,char * name) {
int i;
for (i = 0;i < ud->ver_num;i++) {
if (0 == strcmp(name,ud->vertexs[i].name)) {
return i;
}
}
return -1;
}

//创建一个边
Edge* new_edge () {
Edge *edge = (Edge*)malloc(sizeof(Edge));
if (NULL == edge) {
exit(-1);
}
edge->next = NULL;
return edge;
}
//建立无向图
void create_undigraph (Undigraph * ud) {
int k,i,j;
char v1[10],v2[10];
Edge *edge = NULL;
scanf ("%d%d",&(ud->ver_num),&(ud->edge_num));//输入顶点数和边的数量
//初始化顶点
for (k = 0;k < ud->ver_num;k++) {
scanf("%s",ud->vertexs[k].name);
ud->vertexs[k].first = NULL;
}
//初始化边
for (k = 0; k < ud->edge_num;k++) {
scanf ("%s %s",v1,v2);
i = get_location (ud,v1);
j = get_location (ud,v2);

edge = new_edge ();
edge->index = j;
edge->next = ud->vertexs[i].first;
ud->vertexs[i].first = edge;

edge = new_edge ();
edge->index = i;
edge->next = ud->vertexs[j].first;
ud->vertexs[j].first = edge;
}
}

//返回下标为v的顶点的第一个邻接点，有返回，没有返回NULL
Edge* first_adjacent_vertex (Undigraph *ud,int v) {
if (v < 0 || v >= ud->ver_num) {
return NULL;
}
return ud->vertexs[v].first;
}

//返回edge后的第一个邻接点，有返回，没有返回NULL
Edge* next_adjacent_vertex (Edge *edge ) {
if (NULL == edge) {
return NULL;
}
return edge->next;
}


//用于记录顶点是否被访问过的标志数组
int visited[MAX_VERTEX_NUM];


//------树的二叉链表（孩子-兄弟）存储表示---------
typedef struct CSNode {
char name[10];//图中顶点的名字
struct CSNode *first_child,*next_sibling;
}CSNode,*Tree;



CSNode * create_CSNode (){
CSNode * node = (CSNode*)malloc(sizeof(CSNode));
if (NULL == node) {
exit(-1);
}
node->first_child = NULL;
node->next_sibling = NULL;
return node;
}
//
void dfs_tree (Undigraph *ud,int v,Tree *t) {
Edge *edge = NULL;
CSNode *p = NULL;
strcpy((*t)->name,ud->vertexs[v].name);
visited[v] = 1;
 edge = first_adjacent_vertex (ud,v);
while (NULL != edge) {
if (0 == visited[edge->index]) {
CSNode *node = create_CSNode ();
if (NULL == (*t)->first_child) {
(*t)->first_child = node;
}else {
p->next_sibling = node;
}
p = node;
dfs_tree (ud,edge->index,&p);
}
edge = edge->next;
}
}


void dfs_forest (Undigraph *ud,Tree *t) {
int i;
CSNode *node = NULL;
CSNode *p = NULL;
memset (visited,0,sizeof(visited));
for (i = 0;i < ud->ver_num;i++) {
if (0 == visited[i]) {
node = create_CSNode ();
if (NULL == (*t)) {//根节点
(*t) = node;
}else {
p->next_sibling = node;//其他生成树的根
}
p = node;
dfs_tree (ud,i,&p);
}
}
}

//遍历二叉树

void traverse (Tree  tree) {
if (tree != NULL) {
printf ("%s-",tree->name);
traverse (tree->first_child);
traverse (tree->next_sibling);
}
}
int main () {
Undigraph ud;
Tree  tree = NULL;
create_undigraph (&ud);
dfs_forest (&ud,&tree);
traverse (tree);
return 0;
}