图有关算法题

图的结构

//严蔚敏版数据结构
//邻接表存储结构
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;
    }
}

邻接表转邻接矩阵

MGraph ALToM(ALGraph g){
    MGraph G;
     for(i=0;i<g.vexnum;i++)
        for(j=0;j<g.vexnum;j++)
        	G.arcs[i][j].adj=0;	//邻接矩阵全部赋值为0
    for(i=0;i<g.vexnum;i++)
        G.vexs[i]=g.adjlist[i].data;	//顶点表赋值
    for(i=0;i<g.vexnum;i++){
        p=g.adjlist[i].firstarc;
        while(p){
            G.arcs[i][p->adjvex].adj=1;	//i-->adjvex
            p=p->nextarc;
        }
    }
    G.vexnum=g.vexnum;
    G.arcnum=g.arcnum;
    return G;
}

设无向图 G有 n个顶点，m 条边试编写用邻接表存储该图的算法。(设顶点值用1~n 或0~n-1 编号)

void Creat_Graph(ALGraph &g){
	scanf(&n);	//输入边数和顶点数 cin>>n>>m;
    scanf(&m);
    for(i=0;i<n;i++){
        scanf(&g.adjlist[i].data);	//顶点表赋值
        g.adjlist[i].firstarc=NULL;	//清空边表
    }
    for(k=0;k<m;k++){
        scanf(&v1);	//输入顶点数
        scanf(&v2);
        i=LocateVex(g,v1);	//定位顶点
        j=LocateVex(g,v2);	//定位顶点
        p=(ArcNode*)malloc(sizeof(ArcNode));	//申请边结点
        p->adjvex=j;		//无向图的邻接表存储中边结点需要存储两次
        p->nextarc=g.adjlist[i].firstarc;
        g.adjlist[i].firstarc=p;	//边表采用头插法
        q=(ArcNode*)malloc(sizeof(ArcNode));	//申请新结点 存储另外一条边
        q->adjvex=i;
        q->nextarc=g.adjlist[j].firstarc;
        g.adjlist[i].firstarc=q;
    }
}

无向图删除边结点(邻接表存储)

Status Delete_Arc(ALGraph &G, int v, int w){
	k1=LocateVex(G,v);
    k2=LocateVex(G,v);
    if(!k1||!k2)
        return ERROR;
    p=G.adjlist[k1].firstarc;
    if(p && p->adjvex==k2){	//边表第一个结点是待删除结点
        G.adjlist[k1].firstarc=p->nextarc;
        free(p);
    }
    else{
		while(p && p->adjvex!=k2){
			q = p;	//q是p的前驱结点
			p = p->nextarc;
		}
		if(!p)
			return ERROR;								//欲删除的边不存在
		else{
			q->nextarc = p->nextarc;
			free(p);
		}	 
	}
    
    //无向图删除另一条边
    p = G.adjlist[k2].firstarc;
    if(p && p->adjvex==k1){	//边表第一个结点是待删除结点
        G.adjlist[k2].firstarc=p->nextarc;
        free(p);
    }
    else{
		while(p && p->adjvex!=k1){
			q = p;	//q是p的前驱结点
			p = p->nextarc;
		}
		
		if(!p)
			return ERROR;								//欲删除的边不存在
		else{
			q->nextarc = p->nextarc;
			free(p);
		}	 
	}
    
}

无向图插入边结点(邻接表存储)

Status InsertArc(ALGraph &g, int u, int v){
    i = LocateVex(u);
    j = LocateVex(v);
    if(!i==!j)
        return ERROR;
    
    p=(ArcNode*)malloc(sizeof(ArcNode));	//申请边结点
    p->adjvex=j;		//无向图的邻接表存储中边结点需要存储两次
    p->nextarc=g.adjlist[i].firstarc;
    g.adjlist[i].firstarc=p;	//边表采用头插法
    q=(ArcNode*)malloc(sizeof(ArcNode));	//申请新结点 存储另外一条边
    q->adjvex=i;
    q->nextarc=g.adjlist[j].firstarc;
    g.adjlist[i].firstarc=q;
    
    g.arcnum++;
    
    return OK;
}