graph.cpp

对图的深度优先遍历 基于堆栈 非堆栈 两种实现

#include<stdio.h>
#include<stdlib.h>
#define NODE_NUM 5
int GraphNode[NODE_NUM][3] = {{1,'A',3},{2,'B',3},{3,'C',4},{4,'D',4},{5,'E',2}};
int ConnectTable[] = {1,2,3,0,2,3,0,1,3,4,0,1,2,4,2,3};

//邻接表中图各顶点结构类型定义
typedef struct graphNode
{
    int    order;               
    int    data;               
    struct graphNode *link;       
}graphNode;
//邻接表中图各顶点的遍历头节点结构类型定义
typedef struct tableNode
{
    int    vertexSum;               
    int    data;         
    graphNode *firstnode;   
}tableNode;

void  CreateGraph(tableNode HeadNode[],int max,int fromhead)
{
    graphNode *p,*tail;   
    int    i,j,k;    
    for(i=0;i<max;i++)
    {
        HeadNode[i].vertexSum = GraphNode[i][2];
        HeadNode[i].data = GraphNode[i][1];
        HeadNode[i].firstnode = NULL;
        printf("顶点%c有%d个邻接点!\n",HeadNode[i].data,HeadNode[i].vertexSum);
    }
    for(i=0,k=0;i<max;i++)
    {
        for(j=0;j<HeadNode[i].vertexSum;j++)
        {
            
            p = (graphNode *)malloc(sizeof(graphNode));
            if(p==NULL)
            {
                exit(1);
            }
            else
            {
                p->order = GraphNode[ConnectTable[k+j]][0];
                p->data  = GraphNode[ConnectTable[k+j]][1];
                p->link  = NULL;
                if(fromhead)
                {
                    p->link = HeadNode[i].firstnode;
                    HeadNode[i].firstnode = p;
                }
                else
                {
                    if(HeadNode[i].firstnode == NULL)
                    {
                        HeadNode[i].firstnode = p;
                        tail = p;
                    }
                    else
                    {
                        tail->link = p;
                        tail = p;
                    }
                }

            }
        }
       
        k = k + HeadNode[i].vertexSum;
    }
}

void    DFS_Stack(tableNode HeadNode[],int max)
{
    graphNode *p;       
    graphNode *vstack[NODE_NUM+1]; 
    int    visited[NODE_NUM+1];    
    int    i,top;
	printf("\n");
    printf("图的深度优先遍历结果<堆栈实现>为: \n");
    for(i=0;i<=max;i++)        
        visited[i] = 0;
    for(i=0;i<max;i++)
    {
        top = 1;
        vstack[top] = HeadNode[i].firstnode;
        while(top != 0)   
        {
            p = vstack[top];   
            while((p != NULL) && (visited[p->order] == 1))   
                p = p->link;
            if(p == NULL)   
                top--;    
            else
            {
                printf("顶点[%d][%c] ",p->order,p->data);
                visited[p->order] = 1;
                vstack[++top] = p;    //访问顶点进栈
            }
        }
    }
}
int main(int argc, char* argv[])
{
    tableNode HeadNodeArray[NODE_NUM];
    int InsertMode = -1;
	printf("基于邻接表的图的深度优先遍历程序!\n");
    while(InsertMode != 0 && InsertMode != 1)
    {   
        printf("顶点的插入方式有0:头插法,1:尾插法.请选择!");
        scanf("%d",&InsertMode);
    }
    CreateGraph(HeadNodeArray,NODE_NUM,InsertMode);
    DFS_Stack(HeadNodeArray,NODE_NUM);
	printf("\n");
    printf("遍历完成！\n ");
    return 0;
}