C语言 图 邻接矩阵 深度优先遍历 DFS搜索
程序如下，编译环境vs2005和dev-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; /* 下一个顶点 */
}
}
int 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;
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("
"); /* 换行 */
system("pause");
return 0;
}
#include"iostream.h"
const int n=8;
const int e=15;
typedef int elemtype ;
bool visited[n+1];
class link
{
public:
elemtype data;
link *next;
};
class graph
{
public:
link a[n+1];
void creatlink()
{
int i,j,k;
link *s;
for(i=1;i<=n;i++)
{
a[i].data=i;
a[i].next=NULL;
}
for(k=1;k<=e;k++)
{
cout<<"请输入一条边";
cin>>i>>j;
cout<<endl;
s=new link;
s->data=j;
s->next=a[i].next;
a[j].next=s;
}
}
void dfs1(int i)
{
link *p;
cout<<a[i].data<<" ";
visited[i]=true;
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->data])
dfs1(p->data);
p=p->next;
}
}
void bfs1(int i)
{
int q[n+1];
int f,r;
link *p;
f=r=0;
cout<<a[i].data<<" ";
visited[i]=true;
r++;q[r]=i;
while(f<r)
{
f++;i=q[r];
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->data])
{
coutdata].data<<" ";
visited[p->data]=true;
r++;q[r]=p->data;
}
p=p->next;
}
}
}
};
void main()
{
link *p;int yn=1;
graph g;
g.creatlink();
while(yn){
for(int i=1;i<=n;i++)
{
p=g.a[i].next;
cout";
while(p->next!=NULL)
{
coutdata";
p=p->next;
}
coutdata<<endl;
}
for(i=1;i<=n;i++)
visited[i]=false;
cout<<"输入深度优先搜索开始访问的顶点";
cin>>i;
cout<<endl;
cout<<"从"<<i<<"出发的深度优先搜索遍历序列为"<<endl;
g.dfs1(i);
cout<<endl;
for(i=1;i<=n;i++)
visited[i]=false;
cout<<"请输入广度优先搜索开始访问的顶点";
cin>>i;
cout<<endl;
cout<<"从"<<i<<"出发的广度优先搜索遍历序列为"<<endl;
g.bfs1(i);
cout<<endl;
cout<<"继续遍历吗(1/0)?";
cin>>yn;
}
}
/*图为：
1 2 3
5 4
6 7 8*/
DFSL(ga,p->adjvex);
除了上面两句话，其他没什么问题，首先如果图不连通，当你用从某一点遍历的方法，本身就没办法遍历整个图
员乔金嗓： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...
合作市13464873465： c语言图的遍历,邻接表存储,深度,广度优先遍历 - ？
员乔金嗓： (1) 图的建立,按采用邻接表作为存储结构.(2) 从指定顶点出发进行深度优先搜索遍历.(3) 从指定顶点出发进行广度优先搜索遍历.#include＂stdio.h＂#include＂string.h＂#include＂stdlib.h＂#include＂math.h＂#define MAX_INT 1000#define ...
合作市13464873465： 图的邻接表的深度优先搜索 - ？
员乔金嗓： #include ＂iostream.h＂ int *visited; //存放当前结点是否遍历 typedef int **MGraph;//定义一个二维数组存放邻接矩阵,暂不定义矩阵大小,数据元素类型为整型//把矩阵看作数组元素是一维数组的一个一维数组 struct ArcNode{ //定义邻接表中的...
合作市13464873465： 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是【0 1 1 1 1 0 11 0 0 1 0 0 11 0 0 0 1 0 01 1 0 0 1 1 01 0 1 1 0 1 00 0 0 1 1 0 ... - ？
员乔金嗓：[答案] E. 因为是深度优先,找到与顶点0直接相连的结点,由邻接矩阵知道是顶点1(多个相邻节点取第一个找到的未遍历到的结点),然后再在邻接矩阵中找与顶点1直接相连的结点,得到顶点3.相同方法找到后续结点为:顶点4,顶点2.因为顶点2的相连...
合作市13464873465： c/c++图的邻接矩阵存储结构 - ？
员乔金嗓： 关于图的深度优先遍历代码如下: #include <stdio.h> #include <stdlib.h> #define FALSE 0 #define TURE 1 #define OK 1 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef struct ArcCell{int adj; //顶点关系类型...
合作市13464873465： 用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建;图的深度优先遍历、广度优先遍历. - ？
员乔金嗓： /* 程序1:邻接表的dfs,bfs 其中n是点的个数,m是边的个数,你需要输入m条有向边,如果要无向只需要反过来多加一遍即可. */ #include <stdio.h> #include <string.h> #define MAXM 100000 #define MAXN 10000 int next[MAXM],first[MAXN],en...
合作市13464873465： 图的深度优先遍历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...
合作市13464873465： C语言数据结构 - ？
员乔金嗓： #include <iostream.h> #include <stdlib.h>#define INFINITY 0#define MAX_VERTEX_NUM 10 //最大顶点数#define MAX_EDGE_NUM 40 //最大边数typedef enum {DG,DN,UDG,UDN}Graphkind;typedef char VertexType; //顶点数据类型...
合作市13464873465： 邻接表做深度优先遍历和广度优先遍历的代码 - ？
员乔金嗓： 3、广度优先搜索算法 (1)邻接表表示图的广度优先搜索算法 void BFS(ALGraph*G,int k) {// 以vk为源点对用邻接表表示的图G进行广度优先搜索 int i; CirQueue Q; //须将队列定义中DataType改为int EdgeNode *p; InitQueue(&Q);//队列初始化 ...
合作市13464873465： 编程实现以邻接表或邻接矩阵为存储结构,图的广度和深度优先搜索 - ？
员乔金嗓： /******************************************* 图的遍历演示 以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历. 以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集. *****************************************...
