本篇文章给大家谈谈图的深度优先遍历c语言，以及c语言图的广度优先遍历对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
1、求大神帮写一个c语言图的深度优先遍历，和广度优先遍历??2、c语言图的深度优先遍历问题3、求c语言图的深度优先遍历算法4、图的深度优先遍历c语言算法5、图的深度/广度优先遍历C语言程序6、用C语言编程实现图的遍历算法
求大神帮写一个c语言图的深度优先遍历，和广度优先遍历??
/*深度优先*/
#includestdio.h
#includestdlib.h
struct node/*图的顶点结构*/
{
int vertex;
int flag;
struct node *nextnode;
};
typedef struct node *graph;
struct node vertex_node[10];
void creat_graph(int *node,int n)
{
graph newnode,p;/*定义一个新结点及指针*/
int start,end,i;
for(i=0;in;i++)
{
start=node[i*2];/*边的起点*/
end=node[i*2+1];/*边的终点*/
newnode=(graph)malloc(sizeof(struct node));
newnode-vertex=end;/*新结点的内容为边终点处顶点的内容*/
newnode-nextnode=NULL;
p=(vertex_node
本篇文章给大家谈谈图的深度优先遍历c语言，以及c语言图的广度优先遍历对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
);/*设置指针位置*/
while(p-nextnode!=NULL)
p=p-nextnode;/*寻找链尾*/
p-nextnode=newnode;/*在链尾处插入新结点*/
}
}
void dfs(int k)
{
graph p;
vertex_node[k].flag=1;/*将标志位置1，证明该结点已访问过*/
printf(“vertex[%d]”,k);
p=vertex_node[k].nextnode;/*指针指向下个结点*/
while(p!=NULL)
{
if(vertex_node[p-vertex].flag==0)/*判断该结点的标志位是否为0*/
dfs(p-vertex);/*继续遍历下个结点*/
p=p-nextnode;/*若已遍历过p指向下一个结点*/
}
}
main()
{
graph p;
int node[100],i,sn,vn;
printf(“please input the number of sides:\n”);
scanf(“%d”,sn);/*输入无向图的边数*/
printf(“please input the number of vertexes\n”);
scanf(“%d”,vn);
printf(“please input the vertexes which connected by the sides:\n”);
for(i=0;i4*sn;i++)
scanf(“%d”,node[i]);/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for(i=1;i=vn;i++)
{
vertex_node[i].vertex=i;/*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode=NULL;
}
creat_graph(node,2*sn);/*调用函数创建邻接表*/
printf(“the result is:\n”);
for(i=1;i=vn;i++)/*将邻接表内容输出*/
{
printf(“vertex%d:”,vertex_node[i].vertex);/*输出顶点内容*/
p=vertex_node[i].nextnode;
while(p!=NULL)
{
printf(“-%3d”,p-vertex);/*输出邻接顶点的内容*/
p=p-nextnode;/*指针指向下个邻接顶点*/
}
printf(“\n”);
}
printf(“the result of depth-first search is:\n”);
dfs(1);/*调用函数进行深度优先遍历*/
printf(“\n”);
}
/***************************广度优先*******************************/
#include stdio.h
#include stdlib.h
struct node
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph;
struct node vertex_node[10];
#define MAXQUEUE 100
int queue[MAXQUEUE];
int front = – 1;
int rear = – 1;
int visited[10];
void creat_graph(int *node, int n)
{
graph newnode, p; /*定义一个新结点及指针*/
int start, end, i;
for (i = 0; i n; i++)
{
start = node[i *2]; /*边的起点*/
end = node[i *2+1]; /*边的终点*/
newnode = (graph)malloc(sizeof(struct node));
newnode-vertex = end; /*新结点的内容为边终点处顶点的内容*/
newnode-nextnode = NULL;
p = (vertex_node
本篇文章给大家谈谈图的深度优先遍历c语言，以及c语言图的广度优先遍历对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
); /*设置指针位置*/
while (p-nextnode != NULL)
p = p-nextnode;
/*寻找链尾*/
p-nextnode = newnode; /*在链尾处插入新结点*/
}
}
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 k) /*广度优先搜索*/
{
graph p;
enqueue(k); /*元素入队*/
visited[k] = 1;
printf(“vertex[%d]”, k);
while (front != rear)
/*判断是否对空*/
{
k = dequeue(); /*元素出队*/
p = vertex_node[k].nextnode;
while (p != NULL)
{
if (visited[p-vertex] == 0)
/*判断其是否被访问过*/
{
enqueue(p-vertex);
visited[p-vertex] = 1; /*访问过的元素置1*/
printf(“vertex[%d]”, p-vertex);
}
p = p-nextnode; /*访问下一个元素*/
}
}
}
main()
{
graph p;
int node[100], i, sn, vn;
printf(“please input the number of sides:\n”);
scanf(“%d”, sn); /*输入无向图的边数*/
printf(“please input the number of vertexes\n”);
scanf(“%d”, vn);
printf(“please input the vertexes which connected by the sides:\n”);
for (i = 0; i 4 *sn; i++)
scanf(“%d”, node[i]);
/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for (i = 1; i = vn; i++)
{
vertex_node[i].vertex = i; /*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode = NULL;
}
creat_graph(node, 2 *sn); /*调用函数创建邻接表*/
printf(“the result is:\n”);
for (i = 1; i = vn; i++)
/*将邻接表内容输出*/
{
printf(“vertex%d:”, vertex_node[i].vertex); /*输出顶点内容*/
p = vertex_node[i].nextnode;
while (p != NULL)
{
printf(“-%3d”, p-vertex); /*输出邻接顶点的内容*/
p = p-nextnode; /*指针指向下个邻接顶点*/
}
printf(“\n”);
}
printf(“the result of breadth-first search is:\n”);
bfs(1); /*调用函数进行深度优先遍历*/
printf(“\n”);
}
c语言图的深度优先遍历问题
帮你修改了一下，但是还是报错，是程序逻辑有问题，你看看吧
#includestdio.h
#includestdlib.h
//#define INFINITY -10;
#define MAX_VERTEX_NUM 20
#define VType int
#define VertexType int
//此程序面向无向图
//typedef enum {DG, DN, UDG, UDN} GraphicKind
int visited[MAX_VERTEX_NUM];
typedef struct ArcCell{
VType adj;//表示两点之间有无边
int *info;//权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum , arcnum;
//GraphicKind kind;
}MGraph;
void DFS(MGraph G,int v);
int LocateVex(MGraph *G,VType v)
{
int i;
for(i=1;iMAX_VERTEX_NUM+1;i++)
{
if(G-vexs[i-1]==v)
return i;
}
return -1;
}
MGraph *CreateUDG(MGraph *G)
{
int i,j,k,v1,v2,w;
printf(“input vexnum:\n”);
scanf(“%d”,G-vexnum);
printf(“input arcnum:\n”);
scanf(“%d”,G-arcnum);
//ptintf(“input IncInfo:\n”);
//scanf(“%d”,G.IncInfo);//有无权值
//构造邻接矩阵：
for(i=0;iG-vexnum;i++)
{
printf(“input the %d th vertex:\n”,i);
scanf(“%d”,G-vexs[i]);
printf(“%d”,G-vexs[i]);
}
//初始化邻接矩阵
for(i=0;iG-vexnum;i++)
for(j=0;jG-vexnum;j++)
{
G-arcs[i][j].adj = 0;
G-arcs[i][j].info = 0;
}
//构造邻接矩阵
for(k=0;kG-arcnum;k++)
{
printf(“input the value of the first node:\n”);
scanf(“%d”,v1);
printf(“input the value of the second node:\n”);
scanf(“%d”,v2);
printf(“input the weight of this arc:\n”);
scanf(“%d”,w);//权值
i= LocateVex(G,v1);
j= LocateVex(G,v2);
//定位函数
G-arcs[i][j].adj = w;
//if(incinfo) Input ( *G.arcs[i][j].info)
G-arcs[j][i] = G-arcs[i][j];
}
return G;
}
void DFSTraverse(MGraph G)
{
int v;
for (v=0;vG.vexnum;++v)
visited[v] = 0;
for (v=0;vG.vexnum;v++)
if(!visited[v]) DFS(G,v);
}
void DFS(MGraph G,int v)
{
int w;
int i;
visited[v] = 1;
printf(“%d”,G.vexs[v]);
for(i=v;iG.vexnum;i++)
if(G.arcs[v][i].adj)
{
w = i;
continue;
}
DFS(G,w);
}
int main(){
MGraph g;
*CreateUDG(g);
DFSTraverse(g);
}
求c语言图的深度优先遍历算法
#define MaxVerNum 100 /* 最大顶点数为*/
typedef enum {False,True} boolean;
#include “stdio.h”
#include “stdlib.h”
boolean visited[MaxVerNum];
typedef struct node /* 表结点*/
{
int adjvex;/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/
char Info; /*与边(或弧)相关的信息*/
struct node * next; /* 指向下一个邻接点的指针域*/
} EdgeNode;
typedef struct vnode /* 顶点结点*/
{
char vertex; /* 顶点域*/
EdgeNode * firstedge; /* 边表头指针*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 邻接表*/
int n,e; /* 顶点数和边数*/
} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/
//建立一个无向图的邻接表存储的算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf(“请输入顶点数和边数：”);
scanf(“%d %d”,G-n,G-e);
printf(“n=%d,e=%d\n\n”,G-n,G-e);
getchar();
for(i=0;iG-n;i++) /* 建立有n个顶点的顶点表*/
{
printf(“请输入第%d个顶点字符信息(共%d个)：”,i+1,G-n);
scanf(“%c”,(G-adjlist[i].vertex)); /* 读入顶点信息*/
getchar();
G-adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/
}
for(k=0;k2*G-e;k++) /* 建立边表*/
{
printf(“请输入边Vi,Vj对应的顶点序号(共%d个)：”,2*G-e);
scanf(“%d %d”,i,j);/* 读入边Vi,Vj的顶点对应序号*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新边表结点p
p-adjvex=j; /* 邻接点序号为j */
p-next=G-adjlist[i].firstedge;/* 将结点p插入到顶点Vi的链表头部*/
G-adjlist[i].firstedge=p;
}
printf(“\n图已成功创建!对应的邻接表如下：\n”);
for(i=0;iG-n;i++)
{
p=G-adjlist[i].firstedge;
printf(“%c-“,G-adjlist[i].vertex);
while(p!=NULL)
{
printf(“[ %c ]”,G-adjlist[p-adjvex].vertex);
p=p-next;
}
printf(“\n”);
}
printf(“\n”);
} /*CreateALGraph*/
int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点
{
if(g-adjlist[v].firstedge!=NULL) return (g-adjlist[v].firstedge)-adjvex;
else return 0;
}
int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点
{
EdgeNode *p;
p=g-adjlist[vi].firstedge;
while( p!=NULL p-adjvex!=vj) p=p-next;
if(p!=NULL p-next!=NULL) return p-next-adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */
{
int w;
printf(“%c “,G-adjlist[v].vertex);
visited[v]=True; /* 访问第v个顶点，并把访问标志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w);/* 对v尚未访问的邻接顶点w递归调用DFS */
}
void DFStraverse(ALGraph *G)
/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/
{ int i,v;
for(v=0;vG-n;v++)
visited[v]=False;/*标志向量初始化*/
//for(i=0;iG-n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/
void main()
{
ALGraph G;
CreateALGraph(G);
printf(“该无向图的深度优先搜索序列为：”);
DFStraverse(G);
printf(“\nSuccess!\n”);
}
图的深度优先遍历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;jn;j++)
if(w[i][j] !visited[j])
dfs(j);
}
int main(){
scanf(“%d%d”,m,n);
int a,b;
for(int i = 0;im;i++){
scanf(“%d%d,a,b);
w[a][b] = w[b][a] = true;
}
for(int i = 0;in;i++)
if(!visited[i])
dfs(i);
return 0;
}
图的深度/广度优先遍历C语言程序
这是我们老师给我们上数据结构课的课件
#include “stdio.h”
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;
/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L-num=0;
}
/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L-num);
}
/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf(“请输入顶点数目：”);
scanf(“%d”,L-num);
printf(“请输入各顶点的信息(单个符号）：”);
for(i=0;iL-num;i++)
{
fflush(stdin);
scanf(“%c”,L-vexs[i]);
}
printf(“请输入边权矩阵的信息：”);
for(i=0;iL-num;i++)
{
for(j=0;jL-num;j++)
{
scanf(“%f”,L-arcs[i][j]);
}
}
printf(“图已经创建完毕！”);
}
/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf(“\n图的顶点数目为：%d”,L.num);
printf(“\n图的各顶点的信息为：\n”);
for(i=0;iL.num;i++)
printf(“%c “,L.vexs[i]);
printf(“\n图的边权矩阵的信息为：\n”);
for(i=0;iL.num;i++)
{
for(j=0;jL.num;j++)
{
printf(“%6.2f “,L.arcs[i][j]);
}
printf(“\n”);
}
printf(“图已经输出完毕！”);
}
/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf(“%c “,g.vexs[qidian]);
for(v1=0;v1g.num;v1++)
{
if(g.arcs[qidian][v1]!=0mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf(“\n深度周游：”);
printf(“\n请输入起点的下标：”);
scanf(“%d”,qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
//printf(“v=%d “,v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq-front=0;
sq-rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))
{ printf(“queue is empty!\n”);return 0;}
else
{ *e=sq.data[(sq.front)]; return 1;}
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq-front==(sq-rear+1)%maxsize)
{
printf(“queue is full!\n”);
return 0;
}
else
{
sq-data[sq-rear]=x;
sq-rear=(sq-rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf(“queue is empty!\n”);
return 0;
}
else
{
sq-front=(sq-front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(q);
QueueIn(q,v);
mark[v]=1;
printf(“%c “,g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,v1);
QueueOut(q);
for(v2=0;v2g.num;v2++)
{
if(g.arcs[v1][v2]!=0mark[v2]==0)
{
QueueIn(q,v2);
mark[v2]=1;
printf(“%c “,g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf(“\n广度周游：”);
printf(“\n请输入起点的下标：”);
scanf(“%d”,qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函数**********************/
void main()
{
GRAPH tu;
GraphCreate(tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
用C语言编程实现图的遍历算法
图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，最近阿杰做了关于图的遍历的算法，下面是图的遍历深度优先的算法（C语言程序）：
#includestdio.h
#includemalloc.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;iG-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;iG-n;i++)
visited[i]=0;
for(i=0;iG-n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf(“下面以临接表存储一个图；\n”);
creat(G);
printf(“下面以深度优先遍历该图 \n”);
DFSTraverse(G);
getchar();
}
关于图的深度优先遍历c语言和c语言图的广度优先遍历的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
微信扫一扫 
支付宝扫一扫 
