图论

Related

1. 图解俩种遍历

1. 图的基本操作

代码(Others)

#include <iostream>
#include <stdlib.h>
using namespace std;
const int DefaultVertices=100;
const int maxWeight=1000;
typedef int E;
typedef char T;
class Graphmtx{
private:
    T *VerticesList;
    E **Edge;
    int numVertices;
    int maxVertices;
    int numEdge;
public:
    Graphmtx(int sz=DefaultVertices);
    ~Graphmtx(){
        delete []VerticesList;
        delete []Edge;
    }
    T getValue(int i){
        if(i>=0&&i<numVertices){
            return VerticesList[i];
        }
        else{
            cout<<"error"<<endl;
            exit(1);
        }
    }
    int getNumVertices(){
        return numVertices;
    }
    int getVertexPos(T vertex){
        for(int i=0;i<numVertices;i++){
            if(VerticesList[i]==vertex)
                return i;
        }
        return -1;
    }
    E getWeight(int v1,int v2){
        return (v1>-1&&v2>-1)?Edge[v1][v2]:0;
    }
    int getFirstNeighbor(int v);
    int getNextNeighbor(int v,int w);
    bool insertVertex(const T vertex);
    bool removeVertex(int v);
    bool insertEdge(int v1,int v2,E cost);
    bool removeEdge(int v1,int v2);
    void show();
};
Graphmtx::Graphmtx(int sz){
    maxVertices=sz;
    numVertices=0;
    numEdge=0;
    int i,j;
    VerticesList=new T[maxVertices];
    Edge=new E*[maxVertices];
    for(i=0;i<maxVertices;i++){
        Edge[i]=new E[maxVertices];
    }
    for(i=0;i<maxVertices;i++){
        for(j=0;j<maxVertices;j++){
            Edge[i][j]=((i==j)?0:maxWeight);
        }
    }
}
int Graphmtx::getFirstNeighbor(int v){
    if(v>-1){
        for(int col=0;col<numVertices;col++){
            if(Edge[v][col]&&Edge[v][col]<maxWeight)
                return col;
        }
    }
    return -1;
}
int Graphmtx::getNextNeighbor(int v,int w){
    if(v>-1&&w>-1){
        for(int col=w+1;col<numVertices;col++)
            if(Edge[v][col]&&Edge[v][col]<maxWeight)
                return col;
    }
    return -1;
}
bool Graphmtx::insertVertex(const T vertex){
    if(numVertices==maxVertices)
        return false;
    VerticesList[numVertices++]=vertex;
    return true;
}
bool Graphmtx::removeVertex(int v){
    if(v<0||v>=numVertices){
        cout<<"error"<<endl;
        return false;
    }
    if(numVertices==1)
        return false;
    int i,j;
    VerticesList[v]=VerticesList[numVertices-1];
    for(i=0;i<numVertices;i++){
        Edge[i][v]=Edge[i][numVertices-1];
    }
    numVertices--;
    for(j=0;i<numVertices;j++)
        Edge[v][i]=Edge[numVertices][j];
    return true;
}
bool Graphmtx::insertEdge(int v1,int v2,E cost){
    if(v1<0||v1>=numVertices||v2<0||v2>=numVertices){
        cout<<"error"<<endl;
        return false;
    }
    Edge[v1][v2]=cost;
    Edge[v2][v1]=cost;
    return true;
}
bool Graphmtx::removeEdge(int v1,int v2){
    if(v1<0||v1>=numVertices||v2<0||v2>=numVertices){
        cout<<"error"<<endl;
        return false;
    }
    Edge[v1][v2]=maxWeight;
    Edge[v2][v1]=maxWeight;
    numEdge--;
    return true;
}
void Graphmtx::show(){
    for(int i=0;i<numVertices;i++){
        for(int j=i;j<numVertices;j++){
            if(Edge[i][j]>0&&Edge[i][j]<maxWeight)
                cout<<VerticesList[i]<<"-"<<VerticesList[j]<<":"<<Edge[i][j]<<endl;
        }
    }
    cout<<endl;
}
class SeqQueue {
protected:
     int rear, fron;
     int*elements;
     int maxSize;
public:
    SeqQueue(int sz = 20){
        fron=0; rear=0; maxSize=sz;
        elements = new int[maxSize];
    }
    int push(int x){
        elements[rear] = x;
        rear = (rear+1) % maxSize;
        return 1;
    }
    int pop(int& x){
        if (IsEmpty()) return 0;
        x = elements[fron];
        fron = (fron+1) % maxSize;
        return 1;
    }
    int IsEmpty() const { return fron == rear;}
};
void DFS (Graphmtx& G, int v, bool *visited) {
    cout << G.getValue(v) << ' ';
    visited[v] = true;
    int w = G.getFirstNeighbor (v);
    while (w != -1) {
      if ( !visited[w] ) DFS(G, w, visited);
     w = G.getNextNeighbor (v, w);
    }
}
void DFS (Graphmtx& G, const T& v) {
    int i, loc, n = G.getNumVertices();
    bool *visited = new bool[n];
    for (i = 0; i < n; i++) visited [i] = false;
 loc = G.getVertexPos(v);
    DFS(G,loc,visited);
    delete [] visited;
}
void BFS (Graphmtx& G, const T& v) {
    int i, w, n = G.getNumVertices();
    bool *visited = new bool[n];
    for (i = 0; i < n; i++) visited[i] = false;
    int loc = G.getVertexPos (v);
    cout<<G.getValue(loc)<<' ';
    visited[loc]=true;
    SeqQueue Q;Q.push (loc);
    while (!Q.IsEmpty() ) {
    Q.pop (loc);
    w = G.getFirstNeighbor (loc);
            while (w != -1) {
                if (visited[w]==false){
                    cout<<G.getValue(w)<<' ';
                    visited[w]=true;
                    Q.push (w);
                }
                w = G.getNextNeighbor (loc, w);
             }
      }
      delete [] visited;
}


int main(){
    Graphmtx g;
    int n1,n2;
    cin>>n1;
    char ch;
    cin>>ch;
    g.insertVertex(ch);
    for(int i=1;i<n1;i++){
        char ch;
        cin>>ch;
        g.insertVertex(ch);
    }
    cin>>n2;
    for(int i=0;i<n2;i++){
        int v1,v2,cost;
        cin>>v1>>v2>>cost;
        g.insertEdge(v1,v2,cost);
    }
    cout<<"DFS:";
    DFS(g,ch);
    cout<<endl;
    cout<<"BFS:";
    BFS(g,ch);cout<<endl;
    cout<<"edges are:"<<endl;
    g.show();
    return 0;
}

代码2

#include "iostream"
#include "cstdlib"
using namespace std;

const int MAXWEIGHT = 1000;
const int DEFAULT_NUM_VER = 100;

typedef char VerTex_Type;
typedef int EdgeType;

int sum = 0;
int visit[MAXWEIGHT] = {0};

class Graph
{
private:
    VerTex_Type *Vertex_List; /* 图的点的集合 */
    EdgeType **EdgeArr;
    int NumVertices;
    int NumEdge;
    int MaxVertices;

public:
    Graph(int sz = DEFAULT_NUM_VER);
    ~Graph()
    {
        delete[] Vertex_List;
        delete[] EdgeArr;
    }
    bool Insert_Vertex(const VerTex_Type v);
    bool Insert_Edge(int v1, int v2, EdgeType weight);
    EdgeType Get_Edge(int i, int j);
    VerTex_Type Get_Ver_Value(int i);
    int GetNumVer();
    int GetFirst_Neighbor(int v);
    int GetNext_Neighbor(int v, int w);

    void show();
};

class Queue
{
protected:
    int rear, front;
    int *data;
    int maxSize;

public:
    Queue(int sz = 20)
    {
        front = 0;
        rear = 0;
        maxSize = sz;
        data = new int[maxSize];
    }
    int push(int x)
    {
        data[rear] = x;
        rear = (rear + 1) % maxSize;
        return 1;
    }
    int pop(int &x)
    {
        if (IsEmpty())
        {
            return 0;
        }
        x = data[front];
        front = (front + 1) % maxSize;
        return 1;
    }
    int IsEmpty() const { return front == rear; }
};

Graph::Graph(int sz)
{
    MaxVertices = sz;
    NumVertices = 0; /* 图的ver个数初始化为0 */
    NumEdge = 0;
    Vertex_List = new VerTex_Type[MaxVertices];
    EdgeArr = new EdgeType *[MaxVertices];
    for (int i = 0; i < MaxVertices; i++)
    {
        EdgeArr[i] = new EdgeType[MaxVertices];
    }
    for (int i = 0; i < MaxVertices; i++)
    {
        for (int j = 0; j < MaxVertices; j++)
        {
            EdgeArr[i][j] = ((i == j) ? 0 : MAXWEIGHT); /* 自己到自己为0 */
        }
    }
}

void Graph::show()
{
    for (int i = 0; i < NumVertices; i++)
    {
        for (int j = i; j < NumVertices; j++)
        {
            if (EdgeArr[i][j] > 0 && EdgeArr[i][j] < MAXWEIGHT)
            {
                cout<< Vertex_List[i]<<"-"<<Vertex_List[j]<<":"<<EdgeArr[i][j]<<endl;
            }

        }

    }
}

int Graph::GetNext_Neighbor(int v, int w)
{
    if (v > -1 && w > -1)
    {
        for (int col = w + 1; col < NumVertices; col++) /* 细节w+1, 因为此时w是v的第一个邻居(比如第一个邻居), 开始找w之后的下一个邻居 */
        {
            if (EdgeArr[v][col] > 0 && EdgeArr[v][col] < MAXWEIGHT)
            {
                return col;
            }
        }
    }
    return -1;
}

int Graph::GetFirst_Neighbor(int i)
{
    if (i > -1)
    {
        for (int j = 0; j < NumVertices; j++)
        {
            if (EdgeArr[i][j] > 0 && EdgeArr[i][j] < MAXWEIGHT)
            {
                return j;
            }
        }
    }
    return -1; /* 顶点i没有邻居 */
}

int Graph::GetNumVer()
{
    return NumVertices;
}

VerTex_Type Graph::Get_Ver_Value(int i)
{
    if (i >= 0 && i < NumVertices)
    {
        return Vertex_List[i];
    }
    else
    {
        cout << "Error!" << endl;
        exit(1);
    }
}

EdgeType Graph::Get_Edge(int i, int j)
{
    if (i < 0 || j < 0)
    {
        cout << "Error!" << endl;
        exit(1);
    }
    return EdgeArr[i][j];
}

bool Graph::Insert_Vertex(const VerTex_Type v)
{
    if (NumVertices == MaxVertices)
    {
        return false;
    }

    Vertex_List[NumVertices++] = v;
    return true;
}

bool Graph::Insert_Edge(int v1, int v2, EdgeType weight)
{
    if (v1 < 0 || v1 > NumVertices || v2 < 0 || v2 > NumVertices)
    {
        cout << "error" << endl;
        return false;
    }

    EdgeArr[v1][v2] = weight;
    EdgeArr[v2][v1] = weight; /* 无向图 */
    return true;
}

void DFS(Graph &G, const int &cur)
{
    cout << G.Get_Ver_Value(cur) << " ";
    sum++; /* 每访问一个vertex, sum++ */

    if (sum == G.GetNumVer())
    {
        return;
    } /* 所有ver都访问过则直接退出 */
    for (int i = 0; i < G.GetNumVer(); i++)
    {
        if (G.Get_Edge(cur, i) != MAXWEIGHT && visit[i] == 0 && G.Get_Edge(cur, i) != 0)
        {
            visit[i] = 1;
            DFS(G,i);
        }
    }
    return;
}

void BFS(Graph &G, int &v)
{
    for (int i = 0; i < G.GetNumVer(); i++)
    {
        visit[i] = 0;
    }

    cout << G.Get_Ver_Value(v) << " ";
    visit[v] = 1;
    Queue que;
    que.push(v); /* 从顶点v开始遍历,  */

    int w;
    while (!que.IsEmpty())
    {
        que.pop(v); /* 弹出队列首元素, 并且把队列首元素赋值给v */
        w = G.GetFirst_Neighbor(v);
        while (w != -1) /* 顶点i有邻居的情况下 */
        {
            if (visit[w] == 0)
            {
                cout<<G.Get_Ver_Value(w)<<" ";
                visit[w] = 1;
                que.push(w);
            }
            w = G.GetNext_Neighbor(v,w); /* v和w在调用这个函数之前, 已经是邻居了, 而且w还是v的第一个邻居 */
        }                                /* w这个时候变成了v的下一个邻居(如果此时v还有邻居的情况下) */

    }

}

int main()
{
    Graph G;
    int n;
    cin >> n;

    char ch;
    for (int i = 0; i < n; i++)
    {
        cin >> ch;
        G.Insert_Vertex(ch);
    }

    int m;
    cin >> m;

    int t1, t2;
    EdgeType val;
    for (int i = 0; i < m; i++)
    {
        cin >> t1 >> t2 >> val;
        G.Insert_Edge(t1, t2, val);
    }
    cout << "DFS:";
    visit[0] = 1;
    DFS(G, 0);
    cout<<endl;

    cout<<"BFS:";
    int ii=0;
    BFS(G,ii);
    cout<<endl;

    cout << "edges are:" << endl;
    G.show();


}