用C语言编程实现图的遍历算法

C语言编写程序实现图的遍历操作~

楼主你好，下面是源程序！

/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include
#include
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]
",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:
");
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("
"); /* 换行 */
}
printf("
The end of the dfs are:
");
dfs(1); /* 打印输出遍历过程 */
printf("
"); /* 换行 */
puts(" Press any key to quit...");
getch();
}




/*//////////////////////////////////////////*/
/* 图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include
#include
#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]
",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]
",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.
");
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:
");
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("
"); /* 换行 */
}
printf("The contents of BFS are:
");
bfs(1); /* 打印输出遍历过程 */
printf("
"); /* 换行 */
puts(" Press any key to quit...");
getch();
}


在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++等。

图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，最近阿杰做了关于图的遍历的算法，下面是图的遍历深度优先的算法（C语言程序）：
#include<stdio.h>
#include<malloc.h>
#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\n");
scanf("%d",&G->n);
for(i=0;i<G->n;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\n");
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\n");
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;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以临接表存储一个图；\n");
creat(G);
printf("下面以深度优先遍历该图 \n");
DFSTraverse(G);
getchar();
}

---

那坡县13756257256： C语言编程 图的创建与遍历 - ？
缑石垴安： 在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...

那坡县13756257256： C语言图的创建和遍历算法,紧急 - ？
缑石垴安： 图的遍历是指按某条搜索路径访问图中每个结62616964757a686964616fe59b9ee7ad9431333332626161点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下...

那坡县13756257256： 图的深度优先遍历c语言算法 - ？
缑石垴安： #include <stdio.h> int m,n; bool w[100][100],visited[100]; void dfs(int i){ visited[i] = true; printf(＂%d ＂,i); for(int j = 0;j<n;j++) if(w[i][j] && !visited[j]) dfs(j); } int main(){ scanf(＂%d%d＂,&m,&n); int a,b; for(int i = 0;i<m;i++){ scanf(＂%d%d,&a,&b); w[a][b...

那坡县13756257256： 诚求用C语言编一个实现图的创建及两种遍历的代码. - ？
缑石垴安： /* 首先访问出发点v,并将其标记为已访问过; 然后依次从v出发搜索v的每个邻接点w. 若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止. 若此...

那坡县13756257256： 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; //顶点...

那坡县13756257256： 菜鸟请教各位一个关于图的遍历的C语言程序 - ？
缑石垴安： Mgraph CreatUDG(Mgraph G),函数要有返回值或直接用void CreatUDG(Mgraph *G). Boolean Visited[MAX]中的Boolean好像没定义. 如果要实现广度优先遍历还得用到队列.

那坡县13756257256： 求C语言高手为我实现一个图的深度优先遍历？
缑石垴安： 我现在这个是用类C语言写的图的深度优先搜索算法,如果有疑问,可以联系我,QQ:444511220 Boolean visited[MAX]; //访问标志数组,定义成全局变量 Status (* VisitFunc)(int v); //函数变量 void DFSTraverse(Graph G, Status (* Visit)(int y)) ...

那坡县13756257256： 求c语言图的深度优先遍历算法 - ？
缑石垴安： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...

那坡县13756257256： 用c语言对给定的图和起点,产生其所有的深度优先遍历序列. - ？
缑石垴安： #include ＂stdio.h＂#include ＂malloc.h＂#define MAX 20int visited[MAX];typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode;typedef int Vertex;typedef struct VNode{ Vertex data; struct ArcNode *firstarc; }VNode;typedef VNode ...

那坡县13756257256： 图的遍历c++语言实现?? - ？
缑石垴安： void PreOrder(BTNode *b) { if(b!=NULL) { countdata; PreOrder(b->lchild); PreOrder(b->rchild); } }