重み付け図への隣接テーブル実装


疎図はこのようにして空間を節約することができますが、隣接表写アルゴリズムの卵が痛くて、私はやはり行列を使うのが好きです.の
// cunzai direction and value de listGraph
#ifndef listGRAPH_H_
#define listGRAPH_H_
#define MAXSIZE 100
#include 
#include 
#include 
#include 
using namespace std;

struct edgeNode
{
    char info;
    int cost;
    edgeNode *next;
};

struct headNode
{
    char info;
    int index;
    edgeNode *firstEdge;
};

class listGraph
{
public:
    listGraph();
    ~listGraph();
    void creatGraph();
    void dfs();
    void bfs();
private:
    int headNum;
    int edgeNum;
    headNode *list;
};

listGraph::listGraph()
{
    cout<>headNum>>edgeNum;
    list = new headNode[headNum];
    cout<>list[i].info;
        list[i].index=i;
        list[i].firstEdge=NULL;
    }
}

void listGraph::creatGraph()
{
    int i,j;
    char head;
    cout<>head>>edge->info>>edge->cost;
        edge->next=NULL;
        for(j=0; jnext=list[j].firstEdge;
                list[j].firstEdge=edge;
            }
        }
    }
}

listGraph::~listGraph()
{
    int i;
    edgeNode *temp;
    for(i=0; inext;
            delete temp;
        }
    }
}

void listGraph::dfs()
{
    bool visited[headNum];
    memset(visited,0,sizeof(visited));
    cout<S;
    S.push(0);
    while(!S.empty())
    {
        int temp=S.top();
        edgeNode*cur=list[temp].firstEdge;
        while(cur)
        {
            int curIndex;//find and stroe the index of current element.
            for(int i=0; iinfo==list[i].info)
                {
                    curIndex=list[i].index;
                    break;
                }
            }
            if(!visited[curIndex])
            {
                cout<info<next;
        }
        if(!cur)S.pop();
    }
}

void listGraph::bfs()
{
    bool visited[headNum];
    int printCount=0;
    memset(visited,0,sizeof(visited));
    queueQ;
    Q.push(0);
    while(!Q.empty())
    {
        int temp=Q.front();
        Q.pop();
        if(!visited[temp])
        {
            cout<info==list[i].info)
                {
                    curIndex=list[i].index;
                    break;
                }
            }
            Q.push(curIndex);
            cur=cur->next;
        }
        //use printCount to deal with the situation if there is a loop in the graph.
        if(printCount==headNum)break;
    }
}
#endif

テスト:
#include 
#include "listGraph.h"
#include 
using namespace std;

int main()
{
    //freopen("in.txt","r",stdin);
    //for input test
    /*
    6 5
    A B C D E F
    A B 0
    A C 0
    A D 0
    B E 0
    B F 0
    */
    listGraph test;
    test.creatGraph();
    cout<