| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1578 人关注过本帖
标题:关节点算法
只看楼主 加入收藏
xiaoqing111
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2008-11-22
收藏
 问题点数:0 回复次数:1 
关节点算法
看严蔚敏的书太郁闷了,公式对的,代码完全不能用,谁能帮改下下面代码哪里错了?
还有当DFS到某个叶子节点n的时候,假如这个叶子节点n没有回边,那么他的low[n]=多少,low[n]=min{visited[n],low[w],low[k]},是n的父节点的值吗,还是等于visited[n]?

#include<iostream>
#include<stdlib.h>
using namespace std;

#define OK 1
#define OVERFLOW -2

typedef int Status;
typedef char VertexType;
typedef enum{DG,DN,UDG,UDM} GraphKind;

typedef struct ArcNode{
        int adjvex;
        struct ArcNode *nextarc;
        }ArcNode;
typedef struct VNode{
       VertexType data;
       ArcNode *firstarc;
       }VNode,*AdjList;
typedef struct {
        AdjList vertices;
        int vexnum,arcnum;
        GraphKind kind;
        }ALGraph;


int LocateVex(ALGraph G,VertexType v)
{
    for(int i=0;i<G.vexnum;i++)
            if(G.vertices[i].data==v) return i;
    return G.vexnum;}
   
Status  CreateUDG(ALGraph &G)
{
        G.kind=UDG;               //无向图
        cin>>G.vexnum>>G.arcnum;
        if(!(G.vertices=new VNode[G.vexnum])) exit(OVERFLOW);
        for(int i=0;i<G.vexnum;i++) {
                cin>>G.vertices[i].data;
                G.vertices[i].firstarc=NULL;}
        VertexType v1,v2;
        ArcNode *p,*q;
        int i,j,k=0;
        for(;k<G.arcnum;k++) {
                do
                {
                      cin>>v1>>v2;
                      i=LocateVex(G,v1);
                      j=LocateVex(G,v2);
                      }while(i==G.vexnum||j==G.vexnum);
                p=new ArcNode;
                q=new ArcNode;
                if(!p||!q) exit(OVERFLOW);
                p->adjvex=j;
                p->nextarc=G.vertices[i].firstarc;
                G.vertices[i].firstarc=p;
                q->adjvex=i;
                q->nextarc=G.vertices[j].firstarc;
                G.vertices[j].firstarc=q;
          }
        return OK;
}

void DFSArticul(ALGraph G,int v,int *visited,int &count,int *low){
     int min,w;
     visited[v]=min=++count;
     for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc){
                 w=p->adjvex;
                 if(!visited[w]){
                    DFSArticul(G,w,visited,count,low);
                    if(low[w]<min) min=low[w];
                    if(low[w]>=visited[v]) cout<<G.vertices[v].data<<" ";}
                 else if(((visited[w]-1)!=visited[v])&&(visited[w]<min)) min=visited[w];}
     low[v]=min;
}

void FindArticul(ALGraph G){
     int i,j,v,count=1,*low,*visited=new int[G.vexnum];
     low=new int[G.vexnum];
     if(!visited||!low) exit(OVERFLOW);
     for(i=0;i<G.vexnum;i++) visited[i]=0;
     visited[0]=1;
     ArcNode *p=G.vertices[0].firstarc;
     if(p){
           v=p->adjvex;
           DFSArticul(G,v,visited,count,low);
           if(count<G.vexnum){
                    cout<<G.vertices[0].data<<" ";
                    for(i=0;i<G.vexnum;i++)
                             if(!visited[i])
                                   DFSArticul(G,i,visited,count,low);}
           }
     cout<<endl;
    // for(i=0;i<G.vexnum;i++) cout<<i<<" "<<visited[i]<<" "<<low[i]<<endl;
}
                              
int main(){
    ALGraph G;
    CreateUDG(G);
    FindArticul(G);
    system("pause");
    return 0;}
搜索更多相关主题的帖子: 关节点 算法 
2008-11-22 17:19
xiaoqing111
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2008-11-22
收藏
得分:0 
顺便给组测试数据
13 17
a b c d e f g h i j k l m
a b
a c
a f
a l
b c
b d
b g
b h
b m
d e
g h
g i
g k
h k
j l
j m
l m
应该输出a b d g
2008-11-22 17:32
快速回复:关节点算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025627 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved