拓撲化編程
typedef struct node
{
int adjvex;
struct node *next;
}edgenode;
typedef struct
{
int vertex;
int id;
edgenode *link;
}vexnode;
vexnode dig[n];
void topsort(vexnode dig[])
{
int i,j,k,m=0,top=-1;
edgenode *p;
for(i=0;i<n;i++)
if(dig[i].id==0)
{
dig[i].id=top;
top=i;
}
while(top!=-1)
{
j=top;
top=dig[top].id;
cout<<dig[j].vertex+1<<"\t";
m++;
p=dig[j].link;
while(p)
{
k=p->adjvex;
dig[k].id--;
if(dig[k].id==0)
{
dig[k].id=top;
top=k;
}
p=p->next;
}
}
if(m<n)
cout<<"The network has a cycle.."<<endl;
}
這個是用棧實現的一個演算法，你看下吧
❷ 拓撲排序 編程
*/
#include <stdio.h>
#include <malloc.h>
// 輸出有向圖的一個拓撲序列。實現演算法7.12的程序
// 圖的鄰接表存儲表示
#define MAX_NAME 3 // 頂點字元串的最大長度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType; // 存放網的權值
typedef char VertexType[MAX_NAME]; // 字元串類型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向圖,有向網,無向圖,無向網}
typedef struct ArcNode
{
int adjvex; // 該弧所指向的頂點的位置
struct ArcNode *nextarc; // 指向下一條弧的指針
InfoType *info; // 網的權值指針）
}ArcNode; // 表結點
typedef struct VNode
{
VertexType data; // 頂點信息
ArcNode *firstarc; // 第一個表結點的地址,指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];// 頭結點
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 圖的當前頂點數和弧數
int kind; // 圖的種類標志
}ALGraph;
// 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 採用鄰接表存儲結構,構造沒有相關信息的圖G(用一個函數構造4種圖)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; // 權值
VertexType va,vb;
ArcNode *p;
printf("請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(*G).kind);
printf("請輸入圖的頂點數和邊數:（空格）\n");
scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
printf("請輸入%d個頂點的值(<%d個字元):\n",(*G).vexnum,MAX_NAME);
for(i = 0; i < (*G).vexnum; ++i) // 構造頂點向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 網
printf("請順序輸入每條弧(邊)的權值、弧尾和弧頭(以空格作為間隔):\n");
else // 圖
printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k = 0;k < (*G).arcnum; ++k) // 構造表結點鏈表
{
if((*G).kind==1||(*G).kind==3) // 網
scanf("%d%s%s",&w,va,vb);
else // 圖
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧頭
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 網
{
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 圖
p->nextarc = (*G).vertices[i].firstarc; // 插在表頭
(*G).vertices[i].firstarc = p;
if((*G).kind >= 2) // 無向圖或網,產生第二個表結點
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
if((*G).kind == 3) // 無向網
{
p->info = (int*)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 無向圖
p->nextarc = (*G).vertices[j].firstarc; // 插在表頭
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// 輸出圖的鄰接表G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向圖\n");
break;
case DN: printf("有向網\n");
break;
case AG: printf("無向圖\n");
break;
case AN: printf("無向網\n");
}
printf("%d個頂點：\n",G.vexnum);
for(i = 0; i < G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("\n%d條弧(邊):\n", G.arcnum);
for(i = 0; i < G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind <= 1) // 有向
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == DN) // 網
printf(":%d ", *(p->info));
}
else // 無向(避免輸出兩次)
{
if(i < p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == AN) // 網
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
// 求頂點的入度，演算法7.12、7.13調用
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; // 賦初值
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; // 棧類型
#define STACK_INIT_SIZE 10 // 存儲空間初始分配量
#define STACKINCREMENT 2 // 存儲空間分配增量
// 棧的順序存儲表示 P46
typedef struct SqStack
{
SElemType *base; // 在棧構造之前和銷毀之後，base的值為NULL
SElemType *top; // 棧頂指針
int stacksize; // 當前已分配的存儲空間，以元素為單位
}SqStack; // 順序棧
// 構造一個空棧S。
int InitStack(SqStack *S)
{
// 為棧底分配一個指定大小的存儲空間
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base; // 棧底與棧頂相同表示一個空棧
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// 插入元素e為新的棧頂元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base >= (*S).stacksize) // 棧滿，追加存儲空間
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 若棧不空，則刪除S的棧頂元素，用e返回其值，並返回1；否則返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 演算法7.12 P182
// 有向圖G採用鄰接表存儲結構。若G無迴路,則輸出G的頂點的一個拓撲序
// 列並返回1, 否則返回0。
int TopologicalSort(ALGraph G)
{
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); // 對各頂點求入度indegree[0..vernum-1]
InitStack(&S); // 初始化棧
for(i=0;i<G.vexnum;++i) // 建零入度頂點棧S
if(!indegree[i])
Push(&S,i); // 入度為0者進棧
count=0; // 對輸出頂點計數
while(!StackEmpty(S))
{
// 棧不空
Pop(&S,&i);
printf("%s ",G.vertices[i].data); // 輸出i號頂點並計數
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
// 對i號頂點的每個鄰接點的入度減1
k=p->adjvex;
if(!(--indegree[k])) // 若入度減為0,則入棧
Push(&S,k);
}
}
if(count<G.vexnum)
{
printf("此有向圖有迴路\n");
return 0;
}
else
{
printf("為一個拓撲序列。\n");
return 1;
}
}
int main()
{
ALGraph f;
printf("請選擇有向圖\n");
CreateGraph(&f);
Display(f);
TopologicalSort(f);
system("pause");
return 0;
}
/*
輸出效果：
請選擇有向圖
請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): 0
請輸入圖的頂點數和邊數:（空格）
4 4
請輸入4個頂點的值(<3個字元):
a
b
c
d
請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):
a b
a c
b d
c d
有向圖
4個頂點：
a b c d
4條弧(邊):
a→c a→b
b→d
c→d
a b c d 為一個拓撲序列。
請按任意鍵繼續. . .
*/
❸ c語言 Socket編程，如何定義網路拓撲結構和路由表
原理是 Telnet 路由器IP,進入路由器,然後再進入特權用戶模式,敲命令show cdp neighbor detail,可以查看與之相連的,同理,查出後再進去查另一台跟它相連的 整個拓撲圖就出來了
❹ 怎樣通過編程實現拓撲排序
實現的基本方法
拓撲排序方法如下:
(1)從有向圖中選擇一個沒有前驅(即入度為0)的頂點並且輸出它.
(2)從網中刪去該頂點,並且刪去從該頂點發出的全部有向邊.
(3)重復上述兩步,直到剩餘的網中不再存在沒有前驅的頂點為止.
拓撲序列
C++核心代碼
bool
TopologicalSort(int
a[][101])
//可以完成拓撲排序則返回True
{
int
n
=
a[0][0],
i,
j;
int
into[101],
ans[101];
memset(into,
0,
sizeof(into));
memset(ans,
0,
sizeof(ans));
for
(i
=
1;
i
<=
n;
i++)
{
for
(j
=
1;
j
<=
n;
j++)
{
if
(a[i][j]
>
0)
into[j]++;
}
}
into[0]
=
1;
for
(i
=
1;
i
<=
n;
i++)
{
j
=
0;
while
(into[j]
!=
0)
{
j++;
if
(j
>
n)
return
false;
}
ans[i]
=
j;
into[j]
=
-1;
for
(int
k
=
1;
k
<=
n;
k++)
{
if
(a[j][k]
>
0)
into[k]--;
}
}
for
(i
=
1;
i
<=
n;
i++)
{
cout
<<
ans[i]
<<
"
";
}
cout
<<
endl;
return
true;
}
❺ 拓撲關系怎樣在編程中表示
要選擇數據結構哦，
用樹或者圖儲存，各個點的坐標就可以，參考書上有例子的
❻ 數據結構編程題目(使用拓撲排序編寫）
這個題目應該用圖的深度優先搜索來實現
❼ c語言編程 拓撲演算法
i=0
A[1...n]為一個新數組
循環
尋找入度為零的點，將該點放到位置A[i]中
i=i+1
將該點出邊刪除
輸出A
❽ 利用拓撲排序,編程實現一個偏序關系的全序關系
拓撲排序的代碼
http://blog.csdn.net/peerslee/article/details/50058245
不懂可以留言哈，希望採納阿
❾ c# 畫拓撲圖
自己定義工具欄就好了。
方法一：粗俗畫法，先PS直接把圖片背景抽掉，然後放在自定義控制項作為背景，然後imagelayout屬性給成布滿就好了，這樣他就一個圖片控制項。
方法二：精細做法，選中你的工具欄按鈕，GDI+畫圖，在panel裡面用e.Graphic畫圖，計算坐標，其實也不是很難，只要你熟悉Drawing類，至少比C++、Android方法簡單多了。簡單演示一下原理：
//方法一按鈕畫圖事件，當按下去滑鼠形狀改變成畫筆，Mousedown後創建新控制項：
privatevoidbuttonC_Click(Objectsender,MouseEvente)
{
//選中顏色變化
buttonC.backColor=color...;
}
privatevoidpanel1_MouseDown(Objectsender,MouseEvente)
{
//如果控制項編輯狀態顏色變化，那麼就可以編輯
if(buttonC.BackColor=Color....)
{
UserControl1us=newUserControl1();
us.Width=...;
us.Height=...;
//...
us.Left=...;
us.Top=...;
panel1.Controls.Add(us);
//完成後顏色恢復
buttonC.BackColor=Color.White;
}
}
方法二：
//一樣的道理，不過他不是創建控制項，而是畫圖
publicintx1,x2,y1,y2;
privatevoidpanel1_MouseDown(Objectsender,MouseEvente)
{
if(buttonC.backColor==Color...)
{
x1=e.X;
y1=e.Y;
}
}
privatevoidpanel1_MouseUp(Objectsender,MouseEvente)
{
if(buttonC.backColor==Color...)
{
x2=e.X;
y2=e.Y;
//當滑鼠彈起，結束畫線
Graphicsg=e.Graphics;
g.DrawLine(Pens.Blue,newPoint(x1,y1),newPoint(x2,y2));
buttonC.backColor=Color.White;//恢復初始狀態
}
}
//這里還要寫改變線條坐標事件，方便你去改動
//其他的圖形也可以這么畫，是不是沒你想的復雜？
❿ c++ 編程 拓撲結構
網狀結構最簡單的可以使用二維數組實現。比如：
int g[5][5];可以表示一個有5個節點的圖。其中，g[i][j]可以表示節點i和節點j之間的距離（或者從i到j的費用，節點i到j之間斷路的概率，等等）