/*///////////////////含此友//////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*///////////////////////////////////////////////////////////谈槐//*/
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex /* 顶点数据信息 */
struct node *nextnode/* 指下一顶点的指标 */
}
typedef struct node *graph /* 图形的结构新型态 */
struct node head[9] /* 图形顶点数组 */
int visited[9] /* 遍历标记数组 */
/********************根据已有的信息建立邻接表********************/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode/*指向新节点的指针定义*/
graph ptr
int from /* 边的起点 */
int to /* 边的终点 */
int i
for ( i = 0i <numi++ )/* 读取边线信息，插入邻接表*/
{
from = node[i][0]/*边线的起点*/
to = node[i][1] /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node))
newnode->vertex = to /* 建立顶点内容 */
newnode->nextnode = NULL /* 设定指标初值 */
ptr = &(head[from])/* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历扒慧至链表尾 */
ptr = ptr->nextnode/* 下一个顶点 */
ptr->nextnode = newnode /* 插入节点*/
}
}
/********************** 图的深度优先搜寻法********************/
void dfs(int current)
{
graph ptr
visited[current] = 1 /* 记录已遍历过 */
printf("vertex[%d]\n",current) /* 输出遍历顶点值 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex) /* 递回遍历呼叫 */
ptr = ptr->nextnode /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} }
int i
clrscr()
for ( i = 1i <= 8i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i/*设定顶点值 */
head[i].nextnode = NULL /* 指针为空 */
visited[i] = 0/* 设定遍历初始标志 */
}
creategraph(node,20) /*建立邻接表 */
printf("Content of the gragh's ADlist is:\n")
for ( i = 1i <= 8i++ )
{
printf("vertex%d ->",head[i].vertex)/* 顶点值*/
ptr = head[i].nextnode/* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 印出顶点内容 */
ptr = ptr->nextnode/* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("\nThe end of the dfs are:\n")
dfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
getch()
}
/*//////////////////////////////////////////*/
/*图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex
struct node *nextnode
}
typedef struct node *graph /* 图的结构指针*/
struct node head[9] /* 图的顶点数组 */
int visited[9] /* 遍历标记数组 */
int queue[MAXQUEUE] /* 定义序列数组 */
int front = -1 /* 序列前端*/
int rear = -1 /* 序列后端*/
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode/* 顶点指针 */
graph ptr
int from /* 边起点 */
int to /* 边终点 */
int i
for ( i = 0i <numi++ )/* 第i条边的信息处理*/
{
from = node[i][0] /* 边的起点 */
to = node[i][1] /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node))
newnode->vertex = to /*顶点内容 */
newnode->nextnode = NULL /* 设定指针初值 */
ptr = &(head[from]) /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode/* 下一个顶点 */
ptr->nextnode = newnode /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE )/* 检查伫列是否全满 */
return -1 /* 无法存入 */
rear++ /* 后端指标往前移 */
queue[rear] = value /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1 /* 为空，无法取出 */
front++ /* 前端指标往前移 */
return queue[front] /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr
/* 处理第一个顶点 */
enqueue(current) /* 将顶点存入队列 */
visited[current] = 1 /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current) /* 打印输出遍历顶点值 */
while ( front != rear )/* 队列是否为空 */
{
current = dequeue() /* 将顶点从队列列取出 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex)/* 奖定点放入队列 */
visited[ptr->vertex] = 1/* 置遍历标记为1*/
printf(" Vertex[%d]\n",ptr->vertex)/* 印出遍历顶点值 */
}
ptr = ptr->nextnode/* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} }
int i
clrscr()
puts("This is an example of Width Preferred Traverse of Gragh.\n")
for ( i = 1i <= 8i++ )/*顶点结构数组初始化*/
{
head[i].vertex = i
head[i].nextnode = NULL
visited[i] = 0
}
creategraph(node,20) /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n")
for ( i = 1i <= 8i++ )
{
printf(" vertex%d =>",head[i].vertex)/* 顶点值 */
ptr = head[i].nextnode/* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 打印输出顶点内容 */
ptr = ptr->nextnode/* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("The contents of BFS are:\n")
bfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
getch()
}
思路：以邻接表或邻接矩阵为存储结构，实现连通无向图的深度和广度优先遍历。以用户指定的结点为起始点
，分别输出每吵桐种遍历下的结点访问序列和相应的生成树的边集。
设图的结点不超过30个，每升洞坦个结点用一个编号表示。通过输入图的全部边输入一个图，每个边为一个数对
可以对颤启边的输入顺序作出某种限制。注意，生成树和生成边是有向边，端点顺序不能颠倒。
在C语言编程中，图的创建和遍历：
#include<stdio.h>
#define N 20
#define TRUE 1
#define FALSE 0
int visited[N]
typedef struct /*队列的定义*/
{
int data[N]
int front,rear
}queue
typedef struct /*图的邻接矩阵*/
{
int vexnum,arcnum
char vexs[N]
int arcs[N][N]
}
graph
void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/
void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/
void tdfs(graph *g) /*深度优先搜索整个图*/
void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/
void tbfs(graph *g) /*广旦拍度优先搜索整个图*/
void init_visit() /*初始化访问标识数组*/
void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/
{ int i,j
char v
g->vexnum=0
g->arcnum=0
i=0
printf("输入顶点序老绝列(以#结束)：
")
while((v=getchar())!='#')
{
g->vexs[i]=v /*读入顶点信息*/
i++
}
g->vexnum=i /*顶点数目*/
for(i=0i<g->vexnumi++) /*邻接矩阵初始化*/
for(j=0j<g->vexnumj++)
g->arcs[i][j]=0
printf("输入边的信息：
")
scanf("%d,%d",&i,&j) /*读入边i,j*/
while(i!=-1) /*读入i,j为－1时结束*/
{
g->arcs[i][j]=1
g->arcs[j][i]=1
scanf("%d,%d",&i,&j)
}
}
void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/
{
int j
printf("%c",g->vexs[i])
visited[i]=TRUE
for(j=0j<g->vexnumj++)
if((g->arcs[i][j]==1)&&(!visited[j]))
dfs(j,g)
}
void tdfs(graph *g) /*深度优先搜索整个图*/
{
int i
printf("
从顶点%C开始深度优先搜索序列：",g->vexs[0])
for(i=0i<g->vexnumi++)
if(visited[i]!=TRUE)
dfs(i,g)
}
void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/
{
int i,j
queue qlist,*q
q=&qlist
q->rear=0
q->front=0
printf("%c",g->vexs[k])
visited[k]=TRUE
q->data[q->rear]=k
q->rear=(q->rear+1)%N
while(q->rear!=q->front)
{
i=q->data[q->front]
q->front=(q->front+1)%N
for(j=0j<g->vexnumj++)
if((g->arcs[i][j]==1)&&(!visited[j]))
{
printf("%c",g->vexs[j])
visited[j]=TRUE
q->data[q->rear]=j
q->rear=(q->rear+1)%N
}
}
}
void tbfs(graph *g) /*广度优先搜索整个图*/
{
int i
printf("
从顶点%C开始广度优先搜索序列：",g->vexs[0])
for(i=0i<g->vexnumi++)
if(visited[i]!=TRUE)
bfs(i,g)
printf("
")
}
void init_visit() /*初始化访问标识数组*/
{
int i
for(i=0i<Ni++)
visited[i]=FALSE
}
int main()
{
graph ga
int i,j
createGraph(&ga)
printf("模含羡无向图的邻接矩阵：
")
for(i=0i<ga.vexnumi++)
{
for(j=0j<ga.vexnumj++)
printf("%3d",ga.arcs[i][j])
printf("
")
}
init_visit()
tdfs(&ga)
init_visit()
tbfs(&ga)
return 0
}
C语言编程，顾名思义，就是用C语言来进行计算机编程工作。
C语言是国际上广泛流行的,很有发展前途的计算机高级语言.它适合作为系统描述语言,即可用来编写系统软件,也可用来编写应用软件.
C语言是一种引用广泛，并且实现灵活的一种计算机编程语言，用C语言编出来的程序，可以在很多平台上运行，可移植性强。具体的C语言编程内容请参加C或者C++等。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）