图有关算法题(1)

图的结构

//严蔚敏版数据结构
//邻接表存储结构
typedef struct ArcNode{
    int adjvex;//该弧所指向的顶点的位置
    struct ArcNode *nextarc;//下一个边结点
}ArcNode;

typedef struct VNode{
    VertexType data;//顶点信息
    struct ArcNode *firstarc;//第一个邻接点
}VNode, AdjList;

typedef struct{
    AdjList vertexs[MAX_VERTEX_NUM];	//邻接表AdjList adjlist[MAX_VERTEX_NUM];
    int vexnum,arcnum;
}ALGraph;

//邻接矩阵存储结构
typedef struct ArcCell{
    VRtype adj;//顶点关系
    InfoType *info;
}ArcCell, AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
    VertexType vexs[MAX_VERTEX_NUM];//顶点向量表
    AdjMaritx arcs; //邻接矩阵
}MGraph;

BFS广度优先算法

Status (*Visit)(int v);//函数指针
Boolean visited[MAX];

void BFSTraverse(Graph G)
{
    int u,v,w;
    for(v=0;v<G.vexnum;v++)
        visited[v]=FLASE;//初始化visited数组
    InitQueue(Q);//初始化队列
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])
        {
            Visit(v);visited[v]=TRUE;
            EnQueue(Q,v);
            while(!QueueEmpty(Q))
            {
                DeQueue(Q,u);
                for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                {
                    if(!visited[w])
                    {
                        Visit(w);
                        visited[w]=TRUE;
            			EnQueue(Q,w);
                    }
                }
            }
        }
    }
}

DFS深度优先算法(邻接矩阵)

void DFSTraverse(Graph G){
    for(i=0;i<G.vexnum;i++)
        visited[i]=false;	//初始化标记数组
    for(i=0;i<G.vexnum;i++){
        if(!visited[i])
            DFS(G,i);
    }
}

void DFS(Graph G, int v){
    visited[v]=true;	//true表示顶点v已经访问过了
    Visit(v);	//访问顶点
    for(w=FirstAdjvex(G,u);w>=0;w=NextAdjvex(G,u,w)){
        if(!visited[w]){
            DFS(G,w);
        }
    }
}

DFS深度优先算法非递归算法(邻接矩阵存储)

void DFS(Graph G,int v){
    InitStack(S);//初始化栈
    for(i=0;i<G.vexnum;i++)
        visited[i]=false;	//初始化标记数组
    Push(S,v);	//顶点v入栈
    visted[v]=true;
    while(!StackEmpty(S)){
        Pop(S,k);	//出栈
        Visit(k);
        for(w=FiristAdjVex(G,k);w>=0;w=NextAdjVex(G,k,w)){
			if(!visited[w]){
                Push(S,w);
                visited[w]=true;
            }
        }      
    }
}

图采用邻接表存储，设计算法判断vi和vj结点之间是否有路径

//基于DFS算法
bool visited[maxsize];
bool Pathi_j(ALGraph g, int vi, int vj){
    for(i=0;i<g.vexnum;i++)
        visited[i]=false;
    DFS(g,vi);
    if(visited[vj])	//如果vj被访问过则说明vi,vj之间有路径
        return true;
    else
        return false;
}

void DFS(ALGraph g, int v){
    visited[v]=true;
    p=g.adjlist[v].firstarc;
    while(p){
        if(!visited[p->adjvex]){
            DFS(p->adjvex);
        }
        p=p->nextarc;
    }
}

设计算法判断无向图是否是一棵树(图采用邻接表存储)

/*
树其实是一种特殊的图。树的特点就是，有n结点，有n-1条边。并且连通。
对一个图进行遍历，使用一次深度优先遍历算法(DFS)。
	如果边数为n-1
	结点数为n
那么，就说明这个图可以称之为一棵树。
*/
//基于DFS算法
bool visited[maxsize];
bool IsTree(ALGraph g){
    for(i=0;i<g.vexnum;i++)
        visited[i]=false;
    for(i=0;i<g.vexnum;i++){
        if(!visited[i])
            DFS(g,i,vexnum,arcnum);
    }
    if(g.vexnum==vexnum&&2*(g.arcnum-1)==arcnum)	//无向图中边结点要存储两次，遍历完之后结点有2(n-1)
    	return true;
    else
        return false;
}

void DFS(ALGraph g, int v, int &vexnum, int &arcnum){
    visited[v]=true;
    vexnum++;
    p=g.adjlist[v].firstarc;
    while(p){
        arcnum++;
        if(!visited[p->adjvex]){
            DFS(g,p->adjvex,vexnum,arcnum);
        }
        p=p->nextarc;
    }
}