C语言编写程序实现图的遍历操作
图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(C语言程序):
#include
#include
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex;
struct node *next;
}JD;
typedef struct EdgeNode
{
int vexdata;
JD *firstarc;
}TD;
typedef struct
{
TD ag[m];
int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
JD *p;
int visited[80];
printf("visit vertex:%d->",G->ag[i].vexdata);
visited[i]=1;
p=G->ag[i].firstarc;
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void creat(ALGRAPH *G)
{
int i,m1,j;
JD *p,*p1;
printf("please input the number of graph
");
scanf("%d",&G->n);
for(i=0;in;i++)
{
printf("please input the info of node %d",i);
scanf("%d",&G->ag[i].vexdata);
printf("please input the number of arcs which adj to %d",i);
scanf("%d",&m1);
printf("please input the adjvex position of the first arc
");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2 ;j<=m1;j++)
{
printf("please input the position of the next arc vexdata
");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;
}
}
}
int visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
int i;
for(i=0;in;i++)
visited[i]=0;
for(i=0;in;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以临接表存储一个图;
");
creat(G);
printf("下面以深度优先遍历该图
");
DFSTraverse(G);
getchar();
}
在C语言编程中,图的创建和遍历:
#include
#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=0;ivexnum;i++) /*邻接矩阵初始化*/
for(j=0;jvexnum;j++)
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=0;jvexnum;j++)
if((g->arcs[i][j]==1)&&(!visited[j]))
dfs(j,g);
}
void tdfs(graph *g) /*深度优先搜索整个图*/
{
int i;
printf("
从顶点%C开始深度优先搜索序列:",g->vexs[0]);
for(i=0;ivexnum;i++)
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=0;jvexnum;j++)
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=0;ivexnum;i++)
if(visited[i]!=TRUE)
bfs(i,g);
printf("
");
}
void init_visit() /*初始化访问标识数组*/
{
int i;
for(i=0;i<N;i++)
visited[i]=FALSE;
}
int main()
{
graph ga;
int i,j;
createGraph(&ga);
printf("无向图的邻接矩阵:
");
for(i=0;i<ga.vexnum;i++)
{
for(j=0;j<ga.vexnum;j++)
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++等。
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#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 = 0; i < num; 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; /* 插入节点 */
}
}
/********************** 图的深度优先搜寻法********************/
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 = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
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 = 1; i <= 8; i++ )
{
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 = 0; i < num; i++ ) /* 第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 = 1; i <= 8; i++ ) /*顶点结构数组初始化*/
{
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 = 1; i <= 8; i++ )
{
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();
}
怎么编写C语言程序,如:Helloworld的?
1、点击确定即可,创建出一个helloworld.c的小程序,然后我们就可以编写我们的Hello World小程序了。此时就需要我们的VC++ 6.0来编译此程序,编译无错误才运行此程序,编译按钮和运行按钮如下图的红色箭头处:2、或者可以点击组建工具栏下的编译菜单项,然后再点击执行菜单项,也有快捷键,按Ctrl+F7编译...
帮下忙用C语言编写下这道题的程序,关于指针和调用函数的题?_百度知 ...
按照题目要求编写的C语言程序如下(见图)
C语言编程 编写程序,在屏幕上输出下面的图案(要求用for 循环实现...
1、先双击打开桌面上的C-Free5软件。2、打开编程软件以后,创建一个新页面来编写程序;可以直接点击空白页面,也可以先点击【文件】,再点击【新建】。3、代码:#include<stdio.h>\/\/头文件,int main(void)\/\/主函数{ printf("打印一个C图案:"); printf("\\n"); printf(" ***"); ...
for语句的执行过程和流程图
for循环是C语言编程中的一种循环语句。1、具体执行过程:1)求解表达式1。2)求解表达式2。若其值为真,则执行 for 语句中指定的语句,然后执行第3步;若表达式2值为假,则结束循环,转到第5步。3)求解表达式3。4)转回上面第2步继续执行。5)循环结束,执行 for 语句下面的语句。注意:执行过程...
编写C语言程序输出以下图案 ### *** ### ** #,要有详细过程,悬赏秒结...
这个程序非常简单。它包括一个main函数,该函数使用printf函数来输出指定的图案。printf函数是C语言中用于输出文本的函数。在上面的程序中,我们调用printf函数并将所需的文本作为参数传递。要输出多个字符串,只需在每个字符串之间添加适当的空格或其他分隔符即可。在本例中,我们将所有字符串组合成一个大...
如何编写C语言图形程序?
图 1 打开文件 方法2 在Turbo C for Windows 集成实验与学习环境中的“我的程序”下用鼠标双击你要打开的C程序即可(此处列出最近使用的8个文件)图 2 在“我的程序”中打开程序 方法3在Turbo C for Windows 集成实验与学习环境中,依次用鼠标单击“文件\/我的程序”菜单,打开“我的程序”对话框...
c语言编写流程图
流程图:c语言代码:include <stdio.h> int main(){ int i,sum=0;for(i=1;i<=100;i++)sum+=i;printf("%d\\n",sum);return 0;}
一个c语言的程序题?
然后,在main()函数中定义一个头节点指针,并用它来存储整个链表 请点击输入图片描述 接下来,实现从键盘输入五个整数并将它们尾插入链表中 请点击输入图片描述 最后,实现链表中的插入和删除操作,并输出链表中的所有元素 下面是一个可行的c语言程序,该程序实现了从键盘输入五个整数并存储在链表中,...
怎样用c语言编写一段程序实现奇数和呢?
将变量i从1开始,依次赋值每一个奇数,直到不符合条件(i<=100),即到i=99停止循环。将每一个i值依次累加,求得的和即为题目所求奇数和。2、设计程序框图如下:3、依照程序框图编写程序如下#include<stdio.h> int main() { int i,sum=0; \/\/定义两...
[Linux]编写一个简单的C语言程序,编写Makefile文件。
c语言程序:#include <linux\/init.h>#include <linux\/module.h>MODULE_LICENSE("Dual BSD\/GPL");static int hello_init(void){ printk(KERN_ALERT "Hello, world\\n"); return 0;}static void hello_exit(void){ printk(KERN_ALERT "Goodbye, cruel world\\n");}module_init(hello_init);module_exit(hell...
哀宋夏桑: 在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 /*图的邻接矩e799bee5baa6e4b893e5b19e...
托克逊县15028828251: 诚求用C语言编一个实现图的创建及两种遍历的代码. - ?
哀宋夏桑: /* 首先访问出发点v,并将其标记为已访问过; 然后依次从v出发搜索v的每个邻接点w. 若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止. 若此...
托克逊县15028828251: 菜鸟请教各位一个关于图的遍历的C语言程序 - ?
哀宋夏桑: Mgraph CreatUDG(Mgraph G),函数要有返回值或直接用void CreatUDG(Mgraph *G). Boolean Visited[MAX]中的Boolean好像没定义. 如果要实现广度优先遍历还得用到队列.
托克逊县15028828251: C语言图的遍历. - ?
哀宋夏桑: #include <iostream> #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点...
托克逊县15028828251: C语言图的创建和遍历算法,紧急 - ?
哀宋夏桑: 图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(C语言程序): #include#...
托克逊县15028828251: c语言图的遍历,邻接表存储,深度,广度优先遍历 - ?
哀宋夏桑: (1) 图的建立,按采用邻接表作为存储结构.(2) 从指定顶点出发进行深度优先搜索遍历.(3) 从指定顶点出发进行广度优先搜索遍历.#include"stdio.h"#include"string.h"#include"stdlib.h"#include"math.h"#define MAX_INT 1000#define ...
托克逊县15028828251: 图的遍历c++语言实现?? - ?
哀宋夏桑: void PreOrder(BTNode *b) { if(b!=NULL) { countdata; PreOrder(b->lchild); PreOrder(b->rchild); } }
托克逊县15028828251: 求C语言高手为我实现一个图的深度优先遍历?
哀宋夏桑: 我现在这个是用类C语言写的图的深度优先搜索算法,如果有疑问,可以联系我,QQ:444511220 Boolean visited[MAX]; //访问标志数组,定义成全局变量 Status (* VisitFunc)(int v); //函数变量 void DFSTraverse(Graph G, Status (* Visit)(int y)) ...
托克逊县15028828251: 那位提供一个c语言的图的遍历的演示要求用如下?
哀宋夏桑: 深度优先遍历的递归算法 (1)深度优先遍历算法 int visited[MaxVertexNum]; //访问标志向量是全局量 void DFSTraverse(ALGraph *G) { //深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同 int i; for(i=0;i<G->n;i++) ...
托克逊县15028828251: 求一个C语言编程,图的遍历,深度优先和广度优先搜索的程序.要浅显易懂的~~~~?
哀宋夏桑: 给你一个作为参考吧 #include <iostream> #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct...