图的深度优先搜索（邻接表）
图的遍历(Traversing Graph)是指从图中某一顶点出发访问图中其余顶点，且使每个顶点仅被访问一次。深度优先搜索(Depth First Search) 深度优先搜索假设初始状态下图中所有顶点都未被访问，尝试优先搜索从图中某个顶点v出去，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点，则另选图中未被访问的某顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到。采用邻接表存储图的具体实现如下：#include <cstdio>#include <cstdlib>
#define VERTEXNUM 100 //顶点个数
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE, TRUE} Boolean;
Boolean visited;
/***************************************
*
* 邻接表存储结构
*
* *************************************/
typedef struct node
{
int adjvex; //顶点位置
struct node *next; //指向下一条边的指针
}EdgeNode;
typedef struct vnode
{
VertexType vertex; //顶点信息
EdgeNode *firstedge; //指向第一条依附该顶点的边的指针
}AdjList;
typedef struct
{
AdjList vertexs; //邻接表
int vernum, edgenum; //图中当前的顶点和边数
}Graph;
/***************************************
*
* 建立图的邻接表
*
* *************************************/
void MakeGraph(Graph *graph)
{
int v1, v2;
int i, j, k;
printf("请输入图的顶点数n和边数e:\n");
scanf("%d%d", &graph->vernum, &graph->edgenum);
printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");
for(i = 0; i < graph->vernum; i++)
{
getchar();
scanf("%c", &graph->vertexs.vertex);
graph->vertexs.firstedge = NULL; //初始第一条边为空
}
printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n");
EdgeNode *p;
for(k = 0; k < graph->edgenum; k++)
{
scanf("%d,%d", &i, &j);//读入边<vi,vj>的序号
p = (node *)malloc(sizeof(node)); //生成新的结点
p->adjvex = j - 1;
p->next = graph->vertexs.firstedge;
graph->vertexs.firstedge = p;
}
}
/***************************************
*
* 深度优先遍历
*
* *************************************/
void DFSTraverse(Graph *graph, int v)
{
visited = TRUE;
printf("深度遍历:结点%c\n", graph->vertexs.vertex);
EdgeNode *p = graph->vertexs.firstedge;
while(p != NULL)
{
if(!visited)
DFSTraverse(graph, p->adjvex);
p = p->next;
}
}
void DFS(Graph *graph)
{
int i;
for(i = 0; i < graph->vernum; i++)
visited = FALSE;
for(i = 0; i < graph->vernum; i++)
if(!visited)
DFSTraverse(graph, i);
}
int main()
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
MakeGraph(graph); //建立图的邻接表
DFS(graph); //深度优先遍历
return 0;
}
对于图一中的图，上述程序运行结果如图二。
http://hi.csdn.net/attachment/201202/11/0_13289310509N5z.gif图一
页:
[1]