图

作者: xiaoyanhan | 来源:发表于2016-10-24 09:11 被阅读17次

图图图图图！
视觉图图图图图
haproxy
图图图
图图图
keepalived
软件工程基本术语(一、各种图)
嘻嘻嘻嘻嘻嘻
小学生作品点评，题为“爱岗敬业”
像向日葵一样阳光的你

1、邻接矩阵

#include "stdafx.h"
#include<iostream>
using namespace std;
#define Max 100
typedef struct{
     char vertex[Max];
     int Edge[Max][Max];
     int numVertex,numEdge;
}Graph;

int Locate(Graph *g,char c)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        if(c==g->vertex[i])
            return i;
    }
}
void CreatGraph(Graph *g)
{
    int i,j;
    char p,q;
    int w;
    int m,n;
    cout<<"请输入图的定点数和边数:";
    cin>>g->numVertex>>g->numEdge;
    cout<<"请输入图的顶点:";
    for(i=0;i<g->numVertex;i++)
    {
        cin>>g->vertex[i];
    }
    for(i=0;i<g->numVertex;i++)
        for(j=0;j<g->numVertex;j++)
            g->Edge[i][j]=0;
    for(i=0;i<g->numEdge;i++)
    {
        cout<<"请输入图的边";
        cin>>p>>q;
        m=Locate(g,p);
        n=Locate(g,q);
        g->Edge[m][n]=1;
        g->Edge[n][m]=1;
    }
    
}
void PrintGraph(Graph *g)
{
    int i,j;
    cout<<"顶点:"<<endl;
    for(i=0;i<g->numVertex;i++)
        cout<<g->vertex[i];
    cout<<endl;
    cout<<"边:"<<endl;
    for(i=0;i<g->numVertex;i++)
    {
        for(j=0;j<g->numVertex;j++)
            cout<<g->Edge[i][j];
        cout<<endl;
    }


}
int _tmain(int argc, _TCHAR* argv[])
{
    Graph g;
    CreatGraph(&g);

    PrintGraph(&g);
    system("PAUSE");
    return 0;
}

2、邻接表

#include "stdafx.h"
#include<iostream>
using namespace std;
#define Max 100
typedef struct{
     char vertex[Max];
     int Edge[Max][Max];
     int numVertex,numEdge;
}Graph;
typedef struct EdgeNode{
    int positon;
    struct EdgeNode *next;

}EdgeNode;
typedef struct EdgeVertex{
    char name;
    EdgeNode * first;
}EdgeVertex,AdjList[Max];
typedef struct AdjGraph{
    AdjList adjlist;
    int numVertex,numEdge;
}AdjGraph;
int Locate(AdjGraph *g,char c)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        if(c==g->adjlist[i].name)
            return i;
    }
}

void PrintGraph(AdjGraph *g)
{
    int i;
    EdgeNode * p;
    for(i=0;i<g->numVertex;i++)
    { 
        cout<<g->adjlist[i].name<<":";
        p=g->adjlist[i].first;
        while(p)
        {
            cout<<p->positon;
                p=p->next;
        }
        cout<<endl;
    }


}
void CreatAdjList(AdjGraph *g)
{
    int i;
    char p,q;
    int m,n;
    EdgeNode * edgeNode;
    cout<<"请输入图的定点数和边数:";
    cin>>g->numVertex>>g->numEdge;
    cout<<"请输入图的顶点:";
    for(i=0;i<g->numVertex;i++)
    {
        cin>>g->adjlist[i].name;
        g->adjlist[i].first=NULL;
    }
    for(i=0;i<g->numEdge;i++)
    {
        cout<<"请输入图的边";
        cin>>p>>q;
        edgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        m=Locate(g,p);
        n=Locate(g,q);
        edgeNode->positon=n;
        edgeNode->next=g->adjlist[m].first;
        g->adjlist[m].first=edgeNode;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{

    AdjGraph g;
    CreatAdjList(&g);
    PrintGraph(&g);
    system("PAUSE");
    return 0;
}

3、广度优先遍历

void BFSTravel(AdjGraph *g)
{
    queue<int> q;
    int p;
    EdgeNode *node;
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            q.push(i);
            visited[i]=true;
        while(!q.empty())
        {
            p=q.front();
            cout<<g->adjlist[p].name<<' ';
            node=g->adjlist[p].first;
            q.pop();
            while(node&&!visited[node->positon])
            {
                q.push(node->positon);
                visited[node->positon]=true;
                node=node->next;    
            }
        }
        }
    }

4、深度优先遍历
①递归

void DFS(AdjGraph *g,int i)
{
    EdgeNode *p;
    p=g->adjlist[i].first;
    visited[i]=true;
    cout<<g->adjlist[i].name<<' ';
    while(p)
    {
        if(!visited[p->positon])
        {
            DFS(g,p->positon);
        }
        p=p->next;
    }
}
void DFSTravel(AdjGraph *g)
{
    int i;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            DFS(g,i);
        }
    }
}

②非递归

void DFSTravel(AdjGraph *g)
{
    int i;
    stack<int> s;
    EdgeNode *node;
    int p;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=false;;
    }
    for(i=0;i<g->numVertex;i++)
    {
        if(!visited[i])
        {
            visited[i]=true;
            cout<<g->adjlist[i].name<<' ';
            s.push(i);
            p=s.top();
            node=g->adjlist[p].first;
            while(node||!s.empty())
            {   
                while(node)
                {
                    if(!visited[node->positon])
                    {
                      visited[node->positon]=true;
                      cout<<g->adjlist[node->positon].name<<' ';
                      s.push(node->positon);
                      node=g->adjlist[node->positon].first;
                    }
                    else
                        node=node->next;    
                }
                if(s.top())
                    node=g->adjlist[s.top()].first;
                s.pop();
            }
        }
    }

}

Dijkstra算法

void ShortPath(Graph *g)
{
    int * visited=new int[g->numVertex];
    int * path=new int[g->numVertex];
    int * p=new int[g->numVertex];
    int min;
    int i,j,m;
    int k;
    for(i=0;i<g->numVertex;i++)
    {
        visited[i]=0;
        path[i]=g->Edge[0][i];
        p[0]=0;
    }
    visited[0]=1;
    for(i=1;i<g->numVertex;i++)
    {
        min=inf;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j])
            {
                if(path[j]<min)
                {
                    min=path[j];
                    k=j;
                }
            }
        }
        visited[k]=1;
        for(m=0;m<g->numVertex;m++)
        {
            if(!visited[m]&&min+g->Edge[k][m]<path[m])
            {
                path[m]=min+g->Edge[k][m];
                p[m]=k;
            }
        }

    }
    for(i=0;i<g->numVertex;i++)
    {
         cout<<path[i]<<' ';
    }

}

Floyd-Warshall算法

void Floyd(Graph *g)
{
    int i,j,k;
    int A[20][20];
    int Path[20][20];
    stack<int> s;
    for(i=0;i<g->numVertex;i++)
        for(j=0;j<g->numVertex;j++)
        {
          A[i][j]=g->Edge[i][j];
          Path[i][j]=-1;
         }
      for(k=0;k<g->numVertex;k++)
          for(i=0;i<g->numVertex;i++)
              for(j=0;j<g->numVertex;j++)
              {
                  if(A[i][k]+A[k][j]<A[i][j])
                  {
                      A[i][j]=A[i][k]+A[k][j];
                      Path[i][j]=k;
                  }
              }

     for(i=0;i<g->numVertex;i++)
     {
         cout<<g->vertex[0]<<"-"<<g->vertex[i]<<":";
         cout<<g->vertex[0]<<"->";
         k=Path[0][i];
         while(k!=-1)
         {
             s.push(k);
             k=Path[0][k];

         }
         while(!s.empty())
            {
                cout<<g->vertex[s.top()]<<"->";
             s.pop();
            }
         cout<<g->vertex[i]<<' ';
         cout<<"Cost："<<A[0][i];
         cout<<endl;
     }

}

最小生成树Prime算法

void Prime(Graph *g)
{
    int *visited=new int[g->numVertex];
    int *dist=new int[g->numVertex];
    int i,j,k,sum;
    int min;
    for(i=0;i<g->numVertex;i++)
    {
        dist[i]=g->Edge[0][i];
        visited[i]=0;
    }
    visited[0]=1;
    sum=0;
    for(i=0;i<g->numVertex;i++)
    {
        min=9999;
        k=-1;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
     if(k!=-1)
     {
        sum=sum+min;
        visited[k]=1;
        for(j=0;j<g->numVertex;j++)
        {
            if(!visited[j]&&g->Edge[k][j]<dist[j])
            {
                dist[j]=g->Edge[k][j];
            }
        }
     }
    }
 cout<<"Cost:"<<sum<<endl;
}