图的遍历：深度优先搜索（邻接矩阵存放）

显示全部楼层 · 2020-3-7 05:59:09

程序如下，编译环境vs2005和dev-c++，将图中顶点数和边线数组改为实际值。/*图的深度优先遍历*/#include#includestructnode/*图顶点结构定义*/{intvertex;/*顶点数据信息*/structnode*nextnode;/*指下一顶点的指标*/};typedefstructnode*graph;/*图形的结构新型态*/structnodehead[9];/*图形顶点数组*/intvisited[9];/*遍历标记数组*//*根据已有的信息建立邻接表*/voidcreategraph(intnode[20][2],intnum)/*num指的是图的边数*/{graphnewnode;/*指向新节点的指针定义*/graphptr;intfrom;/*边的起点*/intto;/*边的终点*/inti;for(i=0;ivertex=to;/*建立顶点内容*/newnode->nextnode=NULL;/*设定指标初值*/ptr=&(head[from]);/*顶点位置*/while(ptr->nextnode!=NULL)/*遍历至链表尾*/ptr=ptr->nextnode;/*下一个顶点*/ptr->nextnode=newnode;/*插入节点*/}}/*图的深度优先搜寻法*/voiddfs(intcurrent){graphptr;visited[current]=1;/*记录已遍历过*/printf("vertex[%d]\n",current);/*输出遍历顶点值*/ptr=head[current].nextnode;/*顶点位置*/while(ptr!=NULL)/*遍历至链表尾*/{if(visited[ptr->vertex]==0)/*如过没遍历过*/dfs(ptr->vertex);/*递回遍历呼叫*/ptr=ptr->nextnode;/*下一个顶点*/}}intmain(){graphptr;/*边线数组*/intnode[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}};inti;for(i=1;i",head.vertex);/*顶点值*/ptr=head.nextnode;/*顶点位置*/while(ptr!=NULL)/*遍历至链表尾*/{printf("%d",ptr->vertex);/*印出顶点内容*/ptr=ptr->nextnode;/*下一个顶点*/}printf("\n");/*换行*/}printf("\nTheendofthedfsare:\n");dfs(1);/*打印输出遍历过程*/printf("\n");/*换行*/system("pause");return0;}

千问 · 2020-3-7 05:59:09

程序如下，编译环境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 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]\n",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 ",head.vertex); /* 顶点值
*/
ptr = head.nextnode;
/* 顶点位置 */
while ( ptr != NULL )
/* 遍历至链表尾
*/
{
printf(" %d ",ptr->vertex);/* 印出顶点内容 */
ptr = ptr->nextnode;
/* 下一个顶点
*/
}
printf("\n");
/* 换行
*/ } printf("\nThe end of the dfs are:\n"); dfs(1);
/* 打印输出遍历过程 */ printf("\n");
/* 换行
*/ system("pause"); return 0;}