数据结构 图的深度遍历算法
题目如下
图的定义如下:
typedf struct{//图的定义
VertexType vexs[MAX_VERTEX_NUM];//顶点信息
AdjMatrix arcs; //邻接矩阵
int vexnum, arcnum; //顶点数,弧数
}MGraph;
请写出上述图的深度优先遍历算法
本人菜鸟,望高手指教,不胜感激
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define MAX_SIZE 100
int visited[MAX_SIZE];
typedef struct ArcNode{
char adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode{
char data;
ArcNode *firstarc;
}VertexNode;
typedef struct{
VertexNode vexs[MAX_SIZE];
int arcnum,vexnum;
}Graph;
void visit(char ch)
{
printf("%c ",ch);
}
int Loc(Graph G,char ch)
{ int i;
for(i=1;i<=G.vexnum;i++)
{
if(ch==G.vexs[i].data)
return i;
}
}
void creatGraph(Graph *h)
{
ArcNode *p;
int i,j;
char n,m;
printf("输入弧数和定点数:\n");
scanf("%d %d%*c",&h->arcnum,&h->vexnum);
printf("输入%d个顶点（A~Z）:\n",h->vexnum);
for(i=1;i<=h->vexnum;i++)
{
scanf("%c%*c",&h->vexs[i].data);
h->vexs[i].firstarc=NULL;
}
printf("%d个弧,输入弧尾和弧头\n",h->arcnum);
for(i=1;i<=h->arcnum;i++)
{
scanf("%c %c",&n,&m);
getchar();
j=Loc(*h,n);
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=m;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p;
p=(ArcNode *)malloc(sizeof(ArcNode));
j=Loc(*h,m);
p->adjvex=n;
p->nextarc=h->vexs[j].firstarc;
h->vexs[j].firstarc=p; //无向图
}
}
void DFS(Graph G,char ch)
{ ArcNode *p;
int i;
i=Loc(G,ch);
visit(ch);
visited[i]=1;
p=G.vexs[i].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex-'A'+1])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
int main()
{
Graph G;
char ch,j;
memset(visited,0,sizeof(visited));
creatGraph(&G);
printf("输入要开始搜索的顶点\n");
scanf("%c",&ch);
printf("深搜:");
DFS(G,ch);
system("pause");
}
这个是邻接表的DFS至于邻接矩阵的DFS，想想我还是写一下吧void dfs(int v0){ visited[v0]=1; printf("%d",v0); for(int i=1;i<=g.vexnum;i++) if(!visited[i]) { printf("%d",i); visited[i]=1; dfs(i); }}
图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1，V2和V3之后，有可能沿着边（V3，V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空
集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
从图G=（V，E）的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
例25.(p194.c)图的深度优先搜索。从图G的顶点V0
发进行深度优先搜索，打印出各个顶点的遍历顺序。
解：图的深度优先搜索法为：
（1）首先访问V0并把V0加到集合visited中；
（2）找到与V0相邻的顶点W，若W未进入
visited中，则以深度优先方法从W开始搜索。
（3）重复过程（2）直到所有于V0相邻的顶点
都被访问过为止。
下面是对用邻接表表示的图G进行深度优先搜索的程序
int rear=0; /*Visit和rear都为全局变量*/
int visit[500];
depth_first_search(g,v0) /*从V0开始对图G进行深度
优先搜索*/
graphptr g[ ]; /*指针数组,为邻接表表头顶点指针
g[vi]...g[vn]*/
int v0; /*这里V0和W都是顶点标号,如V0=0或1*/
{ /*g[v0]是顶点V0的表头指针*/
int w;
graphptr p; /*链表的结点指针*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一个顶点，通过邻接表表头指针
，访问v0的邻接顶点*/
while (p!=NULL)
{
w=p->vertex ;/*这里W是与V0相邻的一个顶点*/
if (!visited(w))/*当V0的相邻结点，W未被访问时，从W开始遍厉*/
depth_first_search(g,w);
p=p->next;/*接着访问另一个相邻顶点*/
}
}
int visited(w) /*检查顶点w是否进入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，说明被访问过*/
return(0); /*W不在visit[]中，说明未被访问过，返回0*/
}
2）图的广度优先搜索
从图G的一个顶点V0出发，依次访问V0的邻接点K1,K2...Kn。然后再顺序访问K1,K2...Kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从V1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
（1）首先把V0放入队列；
（2）若队列为空则结束，否则取出队列的头V；
（3）访问V并把所有与V相邻且未被访问的顶点插入队列；
（4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
广度搜索法的程序如下：
broad_first_search(g,v0) /*从V0开始对图g进行广度优先搜索*/
graphptr g[ ]; /*为邻接表，表头顶点指针*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入队列queue*/
while (front <=tail)/*当队列不为空*/
{
v=queue[front++]; /*取出队列中的顶点*/
printf("%d\n",v); /*访问该顶点*/
p=g[v]; /*从顶点V的链表来考虑与V相邻的顶点*/
while (p!=NULL)
{
v=p->vertex; /*从第一个结点（即边）中找出相邻的顶点*/
if (!visited(queue,tail,v))/*判断顶点是否进入队列，如进入队列
说明已被访问或将要访问*/
queue[++tail]=v;/*如果该顶点未被访问过，将此相邻顶点插入队列*/
p=p-->next;/*再考虑该结点的下一个相邻顶点*/
}
}
}
visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/
int q[ ],tail,v;/*进入队列的顶点，在front之前的顶点已被访问过打印输出，
在front和tail之间的顶点是即将要访问顶点*/
{
int i;
for(i=1;i<=tail;i++)/*扫描队列，确定v是否在队列中，在队列中返回1，否则返回0*
/
if (q[i]==v)return(1);/*队列中的顶点都认为已被访问过*/
return(0);
}
深度优先的非递归算法
/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())
{
p=stackMain.pop();
}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.
{
visit(p);
p.marked=true;
}
}while(!stackMain.isEmpty())
关于数据结构的深度优先遍历和广度优先遍历以及最小生成树 第四大题的...
深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后...
数据结构中出图的二种遍历,写出算法与思想,谢谢
先遍历离起点近的，再到远的，直至全图。先遍历所有与起点距离为1的点，再到所有距离为2的点……具体实现，需要一个队列进行辅助存储。举个例，S为起点，S到A,B,C3个点相邻。A又与A1,A2相邻，B与B1,B2相邻，C没有与其他点相邻。对于遍历A发生的事情，就是“发现”了A1,A2。但是，这是不能...
图遍历算法之DFS\/BFS
深度优先搜索（DFS）是用于遍历或搜索图数据结构的算法，该算法从根节点开始（图搜索时可选择任意节点作为根节点）沿着每个分支进行搜索，分支搜索结束后在进行回溯。在进入下一节点之前，树的搜索尽可能的加深。DFS的搜索算法如下（以二叉树为例）：假定根节点（图的任意节点可作为根节点）标记为 ,(L)...
数据结构选择题,帮忙解释下为什么。谢谢
第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。
大学里写dfs是什么意思
DFS是指深度优先搜索，它是一种经典的图遍历算法。在大学理论课程中，DFS常常被用来解决图论、网络流等相关问题。具体而言，DFS运用了递归的思想，从一个起点开始，不断沿着一条路径向下搜寻，直到不能继续为止。然后回溯到前一个节点，继续沿着未搜索的路径深入探索。因此，DFS也被称作“回溯算法”，其...
DFS是什么意思
深度优先搜索是一种图遍历算法，它从起始节点开始，沿着路径直到达到最深的节点，然后回溯到前一个节点，继续探索其他路径。这种搜索方式类似于探险者在迷宫中沿着一条路走到底，直到无法继续前进时返回上一个路口，选择其他路径继续探索。深度优先搜索的原理是利用栈的数据结构来实现，每次选择一个未被访问...
数据结构当中的图怎么都弄不懂怎么办?
1 理解图的两大存储结构 1-1 邻接矩阵 1-2 邻接表 注意：邻接表中，指针数组里的每一个指针都是一个单链表的头指针 注意：单链表里每个节点里存储的是图中每条边的信息。2 理解图的遍历算法 2-1 深度优先遍历 dfs 注意：花半小时看懂dfs的递归代码。2-2 宽度优先遍历 bfs 注意：又叫广度优先...
什么叫遍历算法(最好有例子)
遍历算法概念延伸：图遍历：图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。举例：遍历二叉树搜索路线：从二叉树的...
图的基本概念和遍历
十字链表是将有向图的正邻接表和逆邻接表结合起来得到的一种链表结构。邻接多重表是无向图的另一种链式存储结构，每条边用一个结点表示。边表存储结构主要关注图中各个边的权值以及所依附的两个顶点。图的遍历算法有深度优先搜索和广度优先搜索。深度优先搜索类似树的先序遍历，广度优先搜索类似树的按...
二叉树的深度遍历和广度遍历
因为深度优先搜索算法是先访问根节点，接着遍历左子树再遍历右子树。为了方便，我们可以引入 堆栈 这个数据结构来帮我们快速解决DFS算法。因为栈是 后进先出 的结构，所以我们可以先将 右子树压栈，再将左子树压栈 ，这样左子树就位于栈顶，可以保证先遍历左子树再遍历右子树。我们通过下面的这个二叉树来...
